Menjana set permutasi tambahan yang disediakan dalam susunan yang disusun mengikut leksikal

Joe Z. 03/06/2015. 10 answers, 658 views
code-golf combinatorics

Tentukan prepend-append sequence panjang n untuk menjadi permutasi nombor 1, 2, ..., n yang boleh dihasilkan oleh prosedur berikut:

  • Mulakan dengan nombor 1 .

  • Untuk setiap nombor dari 2 ke n , letakkan nombor ini pada permulaan atau hujung jujukan (sama ada untuk prepend atau append , maka nama urutan itu).

Sebagai contoh, ini adalah cara yang sah untuk menjana urutan pra-tambah tambahan 4:

1
21     [beginning]
213    [end]
2134   [end] 

Tugas anda adalah untuk membina program atau fungsi yang akan mengambil nombor n dari 3 hingga 30 sebagai input, dan mencetak atau mengembalikan semua urutan prepend-append panjang n dalam susunan leksikografik (jika anda mengeluarkan rentetan dan bukan senarai, nombor di atas 9 akan diwakili sebagai huruf a-u , untuk mengekalkan panjang rentetan). Sebagai contoh, inilah pesanan untuk n = 4 :

1234  [RRR]
2134  [LRR]
3124  [RLR]
3214  [LLR]
4123  [RRL]
4213  [LRL]
4312  [RLL]
4321  [LLL] 

Secara umum, terdapat 2 n-1 prepend-append permutasi panjang n .

Anda tidak boleh menggunakan fungsi menyusun terbina dalam bahasa anda dalam kod anda. Program terpendek untuk melakukan ini dalam mana-mana bahasa menang.

5 Comments
xnor 03/06/2015
Saya bukan penggemar keperluan format output, khususnya penukaran kepada huruf a-u . Bolehkah kita hanya mengeluarkan senarai nombor?
3 Optimizer 03/06/2015
Anda mungkin mahu menerima jawapan selepas beberapa ketika sesetengah orang cenderung untuk tidak menjawab soalan jika ia mempunyai jawapan yang diterima.
1 Optimizer 03/06/2015
Jadi anda mendapat jawapan yang salah diterima ..
2 Joe Z. 03/06/2015
FryAmTheEggman menyiarkan jawapannya 21 minit sebelum anda menyuntingnya.
2 Joe Z. 03/06/2015
@Optimizer Saya tidak fikir ia adalah cara yang paling aneh - Jawapan FryAmTheEggman adalah 19 bait lama 21 minit sebelum anda berada. Yang menjadikannya jawapan yang paling awal-diposting.

10 Answers


Optimizer 03/06/2015.

CJam, 22 20 19 17 bait

]]l~{)f+_1fm>|}/p 

Code expansion :

]]                   "Put [[]] onto stack. What we will do with this array of array is";
                     "that in each iteration below, we will first append the next";
                     "number to all present arrays, then copy all the arrays and";
                     "move the last element to first in the copy";
  l~                 "Read input number. Lets call it N";
    {         }/     "Run this code block N times ranging from 0 to N - 1";
     )f+             "Since the number on stack starts from 0, add 1 to it and append";
                     "it to all arrays in the array of array beginning with [[]]";
        _1fm>        "Copy the array of array and move last element from all arrays";
                     "to their beginning";
             |       "Take set union of the two arrays, thus joining them and eliminating";
                     "duplicates. Since we started with and empty array and started adding";
                     "numbers from 1 instead of 2, [1] would have appeared twice if we had";
                     "simply done a concat";
                p    "Print the array of arrays"; 

How it works :

Ini adalah versi debug kod:

]]l~ed{)edf+ed_ed1fm>ed|ed}/edp 

Mari lihat bagaimana ia berfungsi untuk input 3 :

[[[]] 3]                                 "]]l~"            "Empty array of array and input";
[[[]] 1]                                 "{)"              "First iteration, increment 0";
[[[1]]]                                  "{)f+"            "Append it to all sub arrays";
[[[1]] [[1]]]                            "{)f+_"           "Copy the final array of array";
[[[1]] [[1]]]                            "{)f+_1fm>"       "shift last element of each";
                                                           "sub array to the beginning";
[[[1]]]                                  "{)f+_1fm>|}"     "Take set based union";
[[[1]] 2]                                "{)"              "2nd iteration. Repeat";
[[[1 2]]]                                "{)f+"
[[[1 2]] [[1 2]]]                        "{)f+_";
[[[1 2]] [[2 1]]]                        "{)f+_1fm>";
[[[1 2] [2 1]]]                          "{)f+_1fm>|}";
[[[1 2] [2 1]] 3]                        "{)";
[[[1 2 3] [2 1 3]]]                      "{)f+"
[[[1 2 3] [2 1 3]] [[1 2 3] [2 1 3]]]    "{)f+_";
[[[1 2 3] [2 1 3]] [[3 1 2] [3 2 1]]]    "{)f+_1fm>";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}";
[[[1 2 3] [2 1 3] [3 1 2] [3 2 1]]]      "{)f+_1fm>|}/"; 

Cuba dalam talian sini


alephalpha 03/06/2015.

Haskell, 47 bait

f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1 
3 comments
1 nimi 03/06/2015
Beralih kepada pemahaman senarai menjimatkan beberapa bait: f n=[[n:x,x++[n]]|x<-f$n-1]>>=id (menggunakan kod-pemain golf fungsi concat >>=id ).
1 proud haskeller 03/07/2015
@nimi tetapi dalam perintah yang salah r
nimi 03/08/2015
@proudhaskeller: Oh sayang, tidak membaca spek dengan cukup hati-hati. Saya cuba membetulkannya dan mendapati empat cara yang sedikit berbeza dengan panjang sama dengan versi @ alephalpha, jadi saya tidak boleh menawarkan peningkatan. f n=[x++[n]|x<-f$n-1]++[n:x|x<-f$n-1] , f n=map(++[n])(f$n-1)++[n:x|x<-f$n-1] f n=map(++[n])(f$n-1)++map(n:)(f$n-1) f n=(++[n])#n++(n:)#n;p#i=map p$f$i-1

xnor 03/06/2015.

Python 2, 68

 f=lambda n:[[1]]*(n<2)or[x*b+[n]+x*-b for b in[1,-1]for x in f(n-1)] 

Output senarai senarai nombor.

Penyelesaian rekursif. Untuk n==1 , output [[1]] . Jika tidak, tambahkan n kepada permulaan atau hujung semua (n-1) -permutasi. Penyediaan membuat permutasi secara leksikografik kemudian daripada menambah, jadi permutasi tetap disusun.

"Boolean" b encode sama ada untuk meletakkan [n] pada permulaan atau akhir. Sebenarnya, kita memindahkan seluruh senarai x dalam ungkapan x*b+[n]+x*-b . Meletakkan b sebagai -1 atau 1 membolehkan penggunaan flip dengan menafikan, kerana senarai yang didarab dengan -1 adalah senarai kosong.


FryAmTheEggman 03/06/2015.

Pyth, 19

usCm,+dH+HdGr2hQ]]1 

Cuba dalam talian sini

Ini adalah program penuh yang mengambil input dari stdin.

Ini berfungsi dengan cara yang sama dengan penyelesaian xnor, tetapi menghasilkan nilai-nilai yang sedikit daripada perintah, sehingga mereka harus disusun ulang. Apa yang berlaku di setiap peringkat ialah setiap senarai nilai terdahulu mempunyai nilai baru yang ditambahkan pada akhir dan ke permulaan dan semuanya dibungkus dalam 2-tupel yang dibungkus bersama dalam senarai. Contohnya, langkah pertama ialah:

[[1]]
[([1,2], [2,1])] 

Kemudian, senarai tupel ini telah zip (dan kemudian disimpulkan untuk mengeluarkan senarai terluar). Dalam kes pertama ini hanya memberikan nilai yang dibungkus dari atas, kerana terdapat hanya satu nilai dalam senarai.

Langkah-langkah menunjukkan 2-> 3:

([1,2], [2,1])
[([1,2,3],[3,1,2]),([2,1,3],[3,2,1])]
([1,2,3],[2,1,3],[3,1,2],[3,2,1]) 

alephalpha 03/06/2015.

Mathematica, 57 54 49 bytes

f@1=NO 

Contoh:

f[4] 

{{1, 2, 3, 4}, {2, 1, 3, 4}, {3, 1, 2, 4}, {3, 2, 1, 4}, {4, 1, 2, 3} , {4, 2, 1, 3}, {4, 3, 1, 2}, {4, 3, 2, 1}}


randomra 04/13/2017.

J, 26 bait

0|:<:((,,.,~)1+#)@[&0,.@1:

   (0|:<:((,,.,~)1+#)@[&0,.@1:) 3
1 2 3
2 1 3
3 1 2
3 2 1 

Peningkatan 1-bait terima kasih kepada FUZxxl .

1 comments
FUZxxl 03/06/2015
Pengganti,. untuk ,"1 untuk satu aksara.

Pietu1998 04/13/2017.

Pyth, 343331 29

Pada asasnya terjemahan jawapan Python xnor . Saya masih tidak hebat dengan Pyth, jadi cadangan peningkatan adalah dialu-alukan.

Mendefinisikan fungsi y untuk mengembalikan senarai senarai integer.

L?]]1 

Update: Disimpan 2 bait terima kasih kepada FryAmTheEggman .

Penjelasan:

L                                  define a function y with argument b that returns
 ?*]]1 
4 comments
FryAmTheEggman 03/06/2015
Sesetengah barangan -b1 : -b1 boleh menjadi tb , [1_1) boleh ,1_1 (namun anda hanya boleh menggugurkan pendakap yang dekat kerana anda hanya perlu mengira bait yang diperlukan untuk membuat fungsi itu, walaupun anda tidak dapat memanggil ia tanpa menutupnya), dan anda tidak perlu membungkus b dalam senarai sebagai pyth secara automatik menukar kepada senarai apabila menambah senarai ke int.
FryAmTheEggman 03/06/2015
Saya datang dengan cara untuk menyimpan beberapa bait dengan melakukan peta kedua secara manual ke atas [1,-1] . Saya boleh menyimpan bait untuk hardcode sesuatu yang pendek, terutamanya apabila anda memudahkan logik. Saya mendapatkan L?]]1
Pietu1998 03/06/2015
@FryAmTheEggman Anda sebenarnya mungkin mahu menambah itu sebagai jawapan anda sendiri. Itu hanya hebat.
FryAmTheEggman 03/06/2015
OK, saya mahu cuba mengalahkan CJam sebelum menyiarkannya tetapi saya rasa tipuan zip cukup menarik untuk merakamkannya. Nasib baik dengan Pyth;)

edc65 03/07/2015.

JavaScript (ES6) 73 80

Pelaksanaan JavaScript penyelesaian bagus @ Optimizer.

Rekursif (73):

 R=(n,i=1,r=[[1]])=>++i>n?r:r.map(e=>r.push([i,...e])+e.push(i))&&R(n,i,r) 

Iteratif (74):

 F=n=>(i=>NO 

Test Dalam konsol Firefox / FireBug

 R(4) 

[[1, 2, 3, 4], [2, 1, 3, 4], [3, 1, 2, 4], [3, 2, 1, 4], [4, 1, 2, 3] , [4, 2, 1, 3], [4, 3, 1, 2], [4, 3, 2, 1]]


Digital Trauma 03/06/2015.

Pure Bash, 103

Lebih lama daripada yang saya harapkan:

a=1..1
for i in {2..9} {a..u};{
((++c<$1))||break
a={${a// /,}}
a=`eval echo $a$i $i$a`
}
echo ${a%%.*} 

Brett Ryan 03/08/2015.

Penyelesaian Java saya:

public static void main(String[] args) {
    listPrependAppend(4);
}

private static void listPrependAppend(int n) {
    int total = (int) Math.pow(2, n - 1);
    int ps;
    boolean append;
    String sequence;
    String pattern;

    for (int num = 0; num < total; num++) {
        sequence = "";
        pattern = "";
        append = false;
        ps = num;
        for (int pos = 1; pos < n + 1; pos++) {
            sequence = append ? (pos + sequence) : (sequence + pos);
            append = (ps & 0x01) == 0x01;
            ps = ps >> 1;
            if (pos < n) {
                pattern += append ? "L" : "R";
            }
        }
        System.out.format("%s\t[%s]%n", sequence, pattern);
    }
} 
4 comments
Brett Ryan 03/08/2015
Oh, sekarang, setelah melihat jawapan yang lain, saya dapat melihat apa yang anda maksudkan mengenai jawapan yang paling singkat.
2 Joe Z. 03/08/2015
Walaupun penyelesaian anda adalah dihormati, ringkas, dan dibentangkan dengan betul sendiri, anda betul bahawa ia tidak cukup calon untuk masalah yang dihadapi.
1 ProgramFOX 03/08/2015
@BrettRyan Anda boleh membuat kod anda jauh lebih pendek dengan mengeluarkan ruang kosong yang tidak perlu dan menggunakan nama pemboleh ubah one-char. Anda juga boleh menggantikan false dengan sesuatu seperti 5<4 .
1 Brett Ryan 03/08/2015
Terima kasih. Ia adalah cubaan pertama saya untuk menyertai cabaran kod. Saya hanya mencari beberapa cabaran pengaturcaraan dan tidak menyedari sasarannya adalah untuk mendapatkan penyelesaian terpendek. :) Terima kasih kerana membiarkan saya mengambil bahagian.

Related questions

Hot questions

Language

Popular Tags