Bangun Permuter

9

Untuk tantangan ini, Anda akan membuat fungsi (fungsi Anda mungkin merupakan program lengkap) yang mengambil daftar sebagai input dan mengembalikan permutasi daftar itu. Fungsi Anda harus mematuhi persyaratan berikut.

  • Itu harus deterministik.

  • Menyusun fungsi Anda dengan dirinya sendiri beberapa kali variabel harus mampu mendapatkan daftar ke permutasi apa pun.

Ini adalah pertanyaan kode-golf sehingga jawaban akan dinilai dalam byte, dengan lebih sedikit byte yang lebih baik.

Aturan lebih lanjut

  • Anda dapat mengambil jenis daftar, ( [Integer], [String], [[Integer]]) asalkan

    • Bisa tidak kosong
    • Dapat berisi objek yang berbeda dengan setidaknya 16 nilai yang mungkin. (Anda tidak dapat menggunakan Haskell [()]dan mengklaim fungsi Anda adalah id)
    • Dapat berisi objek duplikat (tanpa set)
  • Anda dapat menulis program atau fungsi, tetapi harus mematuhi standar IO.

Ad Hoc Garf Hunter
sumber
Tetapi S_nhanya siklus untukn<3
Leaky Nun
@ LeakyNun, itu tidak meminta permutasi tunggal yang menghasilkan grup simetris: itu meminta next_permutationfungsi.
Peter Taylor
Apakah cukup dengan hanya mengubah daftar 0 dan 1?
xnor
Saya tidak yakin saya mengerti maksud dari pembatasan ini. Jika Anda mengizinkan daftar Boolean, apa gunanya tidak membolehkan iterables atas dua item berbeda?
Dennis
@ Dennis Anda membuat poin yang bagus. Saya akan melarang daftar boolean. Atau tipe yang memiliki kurang dari 16 nilai yang memungkinkan.
Ad Hoc Garf Hunter

Jawaban:

4

CJam (11 byte)

{_e!_@a#(=}

Demo online menunjukkan siklus penuh untuk daftar empat elemen dengan satu elemen duplikat.

Pembedahan

{      e# Define a block
  _e!  e#   Find all permutations of the input. Note that if there are duplicate
       e#   elements in the input then only distinct permutations are produced.
       e#   Note also that the permutations are always generated in lexicographic
       e#   order, so the order is independent of the input.
  _@a# e#   Find the index of the input in the list
  (=   e#   Decrement and get the corresponding element of the list
       e#   Incrementing would also have worked, but indexing by -1 feels less
       e#   wrong than indexing by the length, and makes this more portable to
       e#   GolfScript if it ever adds a "permutations" built-in
}
Peter Taylor
sumber
2

Mathematica + Combinatorica (Paket Bawaan) 34 Bytes

19 byte untuk memuat paket dan 15 untuk fungsi.

<<"Combinatorica`";NextPermutation

Pemakaian:

%@{c, b, a}

Tanpa built-in, 61 Bytes

Extract[s=Permutations[Sort@#],Mod[s~Position~#+1,Length@s]]&

Combinatorica seharusnya sepenuhnya dimasukkan ke dalam Mathematica, tapi saya pikir fungsi NextPermutation diabaikan.

Kelly Lowder
sumber
2

C ++, 42 byte

#include <algorithm>
std::next_permutation

Operasi yang tepat ini adalah bawaan di C ++.

orlp
sumber
2
Mengapa ruang setelahnya #include?
Yytsi
2

JavaScript (ES6), 145 139 137 134 108 byte

Menyimpan 25 byte kekalahan berkat @Neil!

Mengambil input sebagai array karakter alfabet. Mengembalikan permutasi berikutnya sebagai array lain.

a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,a.concat(a.splice(x+1).sort()))

Bagaimana?

Ini adalah generasi dalam urutan leksikografis yang memproses 4 langkah berikut di setiap iterasi:

  1. Temukan indeks X terbesar sehingga [X] <a [X + 1]

    a.map((v, i) => v < a[i + 1] ? (t = v, x = i) : ...)
  2. Temukan indeks Y terbesar lebih besar dari X sehingga [Y]> a [X]

    a.map((v, i) => v < a[i + 1] ? ... : y = i > x & v > t ? i : y)
  3. Tukar nilai [X] dengan nilai [Y]

    a[x] = a[y], a[y] = t
  4. Urutkan urutan dari [X + 1] hingga dan termasuk elemen terakhir, dalam urutan leksikografis naik

    a.concat(a.splice(x + 1).sort())

Contoh:

Langkah

Demo

Arnauld
sumber
Tidak bisakah Anda menyortir daripada membalik? Saya pikir juga v<a[i+1]&&(t=v,x=i)menghemat satu byte, dan Anda mungkin dapat melakukan lebih banyak penghematan dengan menggunakan splicedua slices.
Neil
@Neil Tangkapan bagus!
Arnauld
Saya pikir saya bisa menggabungkan keduanya mapjuga, untuk 112 byte:a=>(t=x=y=-1,a.map((v,i)=>v<a[i+1]?(t=v,x=i):y=i>x&v>t?i:y),a[x]=a[y],a[y]=t,t=a.splice(++x).sort(),a.concat(t))
Neil
Saya harus mengakui bahwa saya tidak berpikir a.concat(a.splice(++x).sort())akan berhasil kalau tidak saya akan mencobanya ...
Neil
@Neil Terima kasih! Diperbarui. (Dengan 4 byte lebih disimpan karena kita tidak perlu t untuk concat () ).
Arnauld
1

Jelly , 6 byte

Œ¿’œ?Ṣ

Siklus melalui permutasi dalam urutan leksikografis menurun.

Cobalah online!

Bagaimana itu bekerja

Œ¿’œ?Ṣ  Main link. Argument: A (array)

Œ¿      Compute the permutation index n of A, i.e., the index of A in the
        lexicographically sorted list of permutations of A.
  ’     Decrement the index by 1, yielding n-1.
     Ṣ  Sort A.
   œ?   Getthe (n-1)-th permutation of sorted A.
Dennis
sumber
1

C, 161 byte

Algoritma O (n) aktual.

#define S(x,y){t=x;x=y;y=t;}
P(a,n,i,j,t)int*a;{for(i=n;--i&&a[i-1]>a[i];);for(j=n;i&&a[--j]<=a[i-1];);if(i)S(a[i-1],a[j])for(j=0;j++<n-i>>1;)S(a[i+j-1],a[n-j])}

Contoh penggunaan:

int main(int argc, char** argv) {
    int i;
    int a[] = {1, 2, 3, 4};

    for (i = 0; i < 25; ++i) {
        printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
        P(a, 4);
    }

    return 0;
}
orlp
sumber
1

Python 2 , 154 byte

x=input()
try:exec'%s=max(k for k in range(%s,len(x))if x[%s-1]<x[k]);'*2%tuple('i1kjii');x[i-1],x[j]=x[j],x[i-1];x[i:]=x[:i-1:-1]
except:x.sort()
print x

Cobalah online!

Dennis
sumber
Saya pikir ini lebih pendek sebagai fungsi yang memungkinkan daftar di tempat.
orlp
Saya mencobanya, tetapi execmemberi saya semua jenis kesalahan dalam suatu fungsi
Dennis
0

Jelly , 10 byte

ṢŒ!Q©i⁸‘ị®

Cobalah online!

Sortir> semua permutasi> temukan input> tambahkan 1> indeks ke dalam "semua permutasi

Biarawati Bocor
sumber
@ PeterTaylor saya sudah memperbaikinya.
Leaky Nun
Ada builtin spesifik untuk permutasi (yaitu Anda bisa melakukannya Œ¿‘œ?Ṣ). Saya tidak merasa ingin mencuri karena, yah, algo yang sama.
Erik the Outgolfer
@EriktheOutgolfer mungkin agak berantakan untuk input yang berisi duplikat.
Leaky Nun
Hmm ... Saya kira begitu, saya punya versi yang bekerja sebelumnya, tetapi Anda tampaknya menggunakan Qthingy. Anda masih bisa bermain golf ṢŒ!Qµi³‘ị.
Erik the Outgolfer
0

PHP , 117 byte

Mengambil input / output sebagai daftar string huruf yang lebih rendah

$a=str_split($s=$argn);rsort($a);if(join($a)!=$s)for($n=$s;($c=count_chars)(++$n)!=$c($s););else$n=strrev($s);echo$n;

Cobalah online!

Jörg Hülsermann
sumber