Semua Xenodrom

15

pengantar

Xenodrome di basis n adalah bilangan bulat di mana semua digit di basis n berbeda. Berikut adalah beberapa urutan xenodrom OEIS.

Sebagai contoh, dalam basis 16, FACE, 42dan FEDCBA9876543210beberapa xenodromes (mana yang 64206, 66dan 18364758544493064720dalam basis 10), tetapi 11dan DEFACEDtidak.

Tantangan

Dengan basis input, n , mengeluarkan semua xenodrom untuk basis itu di basis 10 .

Outputnya harus dalam urutan paling sedikit hingga terbesar. Harus jelas di mana istilah dalam urutan berakhir dan yang baru dimulai (misalnya [0, 1, 2]jelas di mana 012tidak.)

n akan menjadi bilangan bulat lebih besar dari 0.

Klarifikasi

Tantangan ini tidak IO khusus dalam basis 10 untuk menghindari penanganan bilangan bulat dan basis mereka sebagai string. Tantangannya adalah secara abstrak menangani basis apa pun. Karena itu, saya menambahkan aturan tambahan ini:

Integer tidak dapat disimpan sebagai string dalam basis selain basis 10.

Program Anda harus dapat secara teoritis menangani cukup tinggi n jika tidak ada waktu, memori, presisi atau batasan teknis lainnya dalam pelaksanaan bahasa.

Ini adalah , jadi program terpendek, dalam byte, menang.

Contoh Input dan Output

1  # Input
0  # Output
2
0, 1, 2
3
0, 1, 2, 3, 5, 6, 7, 11, 15, 19, 21
4
0, 1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 18, 19, 24, 27, 28, 30, 33, 35, 36, 39, 44, 45, 49, 50, 52, 54, 56, 57, 75, 78, 99, 108, 114, 120, 135, 141, 147, 156, 177, 180, 198, 201, 210, 216, 225, 228
Artyer
sumber
1
apakah ada batasan untuk n?
FlipTack
@ Flp.Tkc Tidak. Itu harus bisa menangani cukup tinggi n. Saya tidak ingin tantangan dibatasi oleh seberapa tinggi basis konversi bahasa builtin dasar dapat menangani.
Artyer
@Artyer Itu seharusnya menjadi bagian dari teks tantangan, lalu. Tampaknya beberapa jawaban sudah melakukan itu
Luis Mendo
Saya tahu konversi basis di Pyth dapat menangani nilai yang lebih besar dari 36 , tetapi karena ini menginginkan semua xenodromes, python yang mendasari rusak ketika daftar menjadi terlalu besar, mengatakan itu tidak dapat memuat nilai dalam a ssize_t. Apakah melanggar dengan cara ini dapat diterima?
FryAmTheEggman
2
Seseorang tampaknya telah menurunkan semua jawaban yang tidak dapat menangani basis yang lebih besar karena batas presisi bawaan, yang juga tampak seperti implementasi dan bukan masalah algoritma. Bisakah Anda mengklarifikasi?
Dennis

Jawaban:

10

Pyth , 8 byte

f{IjTQU^

Memfilter angka dalam [0, n ^ n - 1] karena tidak memiliki elemen duplikat di pangkalan n . Konversi basis di Pyth akan bekerja dengan basis apa pun, tetapi karena ini terlihat pada daftar angka yang meningkat sangat cepat, akhirnya tidak akan dapat menyimpan nilai dalam memori.

Cobalah online!

Penjelasan:

f{IjTQU^QQ    - Auto-fill variables
      U^QQ    - [0, n^n-1]
f             - keep only those that ...
 {I           - do not change when deduplicated
   jTQ        - are converted into base n
FryAmTheEggman
sumber
Wow, solusi yang lebih pendek daripada solusi Jelly yang dibuat Dennis! : 'P
HyperNeutrino
3
Tidak ada yang mengalahkan Jelly. ¶:
Roman Gräf
5

Python 2, 87 byte

n=input()
for x in range(n**n):
 s={n};a=x
 while{a%n}|s>s:s|={a%n};a/=n
 print-~-a*`x`

Mencetak garis kosong ekstra untuk non-xenodromes:

golf % python2.7 xenodromes.py <<<3
0
1
2
3

5
6
7



11



15



19

21
Lynn
sumber
5

Jelly , 9 8 byte

ð*ḶbQ€Qḅ

Terima kasih kepada @JonathanAllan untuk bermain golf 1 byte!

Cobalah online! atau verifikasi semua kasus uji .

Bagaimana itu bekerja

ð*ḶbQ€Qḅ  Main link. Argument: n

ð         Make the chain dyadic, setting both left and right argument to n.
          This prevents us from having to reference n explicitly in the chain.
 *        Compute nⁿ.
  Ḷ       Unlength; yield A := [0, ..., nⁿ - 1].
   b      Convert each k in A to base n.
    Q€    Unique each; remove duplicate digits.
      Q   Unique; remove duplicate digit lists.
       ḅ  Convert each digit list from base n to integer.
Dennis
sumber
4

Jelly , 12 byte

*`ḶbµQ⁼$Ðfḅ³

TryItOnline!

Akan bekerja untuk apa saja n , mengingat memori yang cukup, konversi basis Jelly tidak membatasi.

Bagaimana?

*`ḶbµQ⁼$Ðfḅ³ - Main link: n
    µ        - monadic chain separation
*            - exponentiation with
 `           - repeated argument, i.e. n^n
  Ḷ          - lowered range, i.e. [0,1,2,...,n^n-1]
   b         - covert to base n (vectorises)
        Ðf   - filter keep:
       $     -     last two links as a monad
     Q       -         unique elements
      ⁼      -         equals input (no vectorisation)
           ³ - first program argument (n)
          ḅ  - convert from base (vectorises)
Jonathan Allan
sumber
3

JavaScript (ES7), 86 byte

n=>{a=[];for(i=n**n;i--;j||a.unshift(i))for(j=i,b=0;(b^=f=1<<j%n)&f;j=j/n|0);return a}
Neil
sumber
Gagal untuk 1(Haruskah keluaran [0], tetapi RangeErrors.)
Artyer
Persis seperti yang saya miliki, tetapi ini secara teoritis akan gagal karena 37jika presisi tidak menjadi masalah, yang saya pikir membuatnya tidak valid ...
ETHproduksi
@Artyer Aku sudah porting versi Batch saya, jadi sekarang ini akan bekerja untuk ndari 1ke 13sebelum floating-point presisi membunuh itu.
Neil
Saya suka bagaimana solusinya dimulai sangat singkat, dan kemudian tiba-tiba melompat urutan besarnya.
Nissa
2

Perl 6 , 47 byte

{(0..$_**$_).grep: !*.polymod($_ xx*).repeated}

Mengembalikan Seq . ( Seq adalah pembungkus Iterable dasar untuk Iterator s)

Dengan input 16dibutuhkan 20 detik untuk menghitung elemen 53905 dari Seq ( 87887).

Diperluas:

{       # bare block lambda with implicit parameter 「$_」

  ( 0 .. ($_ ** $_) )    # Range of values to be tested

  .grep:                 # return only those values

    !\                   # Where the following isn't true
    *\                   # the value
    .polymod( $_ xx * )  # when put into the base being tested
    .repeated            # has repeated values
  }
}
Brad Gilbert b2gills
sumber
2

Batch, 204 200 byte

@set/an=%1,m=1
@for /l %%i in (1,1,%1)do @set/am*=n
@for /l %%i in (0,1,%m%)do @set/ab=0,j=i=%%i&call:l
@exit/b
:l
@set/a"f&=b^=f=1<<j%%n,j/=n"
@if %f%==0 exit/b
@if %j% gtr 0 goto l
@echo %i%

Tidak akan berfungsi untuk n> 9 karena Batch hanya memiliki aritmatika 32-bit. Mudah, Batch mengevaluasi f &= b ^= f = 1 << j % nsebagai f = 1 << j % n, b = b ^ f, f = f & bbukan f = f & (b = b ^ (f = 1 << j % n)).

Neil
sumber
2

Mathematica, 59 48 byte

Select[Range[#^#]-1,xMax[x~DigitCount~#]==1]&

Berisi karakter U + F4A1 "Penggunaan Pribadi"

Penjelasan

Range[#^#]-1

Hasilkan {1, 2, ..., n^n}. Kurangi 1. (hasil {0, 1, ..., n^n - 1})

xMax[x~DigitCount~#]==1

Fungsi Boolean: Truejika setiap digit muncul paling banyak satu kali di basis n.

Select[ ... ]

Dari daftar {0, 1, ..., n^n - 1} , pilih yang memberiTrue ketika fungsi Boolean di atas diterapkan.

Versi 59 byte

Select[Range[#^#]-1,xDuplicateFreeQ[x~IntegerDigits~#]]&
JungHwan Min
sumber
2

Mathematica, 48 55 byte

Union[(x   x~FromDigits~#)/@Permutations[Range@#-1,#]]&

(Ruang triple antara x s perlu diganti dengan karakter 3-byte \ uF4A1 untuk membuat kode berfungsi.)

Fungsi argumen tunggal yang tidak disebutkan namanya. Alih-alih menguji bilangan bulat untuk xenodromicity, ia hanya menghasilkan semua permutasi yang mungkin dari himpunan bagian dari angka yang diizinkan (yang secara otomatis menghindari pengulangan) dan mengubah bilangan bulat yang sesuai ke basis 10. Setiap xenodrome dihasilkan dua kali, baik dengan dan tanpa 0 yang memimpin; Unionmenghapus duplikat dan mengurutkan daftar untuk boot.

Greg Martin
sumber
1
Gagal untuk 2. Fungsi memberi {0, 1}. Saya percaya Anda perlu, Permutations[Range@#-1, #]bukan Subsets[Range@#-1].
JungHwan Min
Gah, kesalahan yang bodoh. Terima kasih telah mengamatinya, dan telah menyarankan perbaikan yang sempurna!
Greg Martin