สร้างชุดของการเรียงลำดับก่อนผนวก - ผนวกเรียงตามลำดับ lexicographically

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

กำหนด prepend-append sequence ความยาว n เป็นการเปลี่ยนแปลงของตัวเลข 1, 2, ..., n ที่สามารถสร้างขึ้นได้ตามขั้นตอนต่อไปนี้:

  • เริ่มต้นด้วยหมายเลข 1

  • สำหรับแต่ละหมายเลขตั้งแต่ 2 ถึง n ให้วางหมายเลขนี้ไว้ที่จุดเริ่มต้นหรือจุดสิ้นสุดของลำดับ ( append หรือ append จึงเป็นชื่อของลำดับ)

ตัวอย่างเช่นนี่เป็นวิธีที่ถูกต้องในการสร้างลำดับของส่วนท้ายล่วงหน้า - ยาว 4:

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

งานของคุณคือการสร้างโปรแกรมหรือฟังก์ชันที่จะใช้ตัวเลข n ตั้งแต่ 3 ถึง 30 เป็น input และพิมพ์หรือส่งคืนลำดับทั้งหมดที่เพิ่มไว้ในลำดับความยาว n ตามลำดับตัวอักษร (ถ้าคุณกำลังพิมพ์สตริงและไม่ใช่รายการตัวเลขข้างต้น 9 จะแสดงเป็นตัวอักษร a-u เพื่อรักษาความยาวของสตริง) ตัวอย่างเช่นนี่คือลำดับสำหรับ n = 4 :

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

โดยทั่วไปมี 2 n-1 บวก - ผนวก permutations ของความยาว n

คุณไม่สามารถใช้ฟังก์ชันการจัดเรียงที่มีอยู่ภายในภาษาของคุณในโค้ดของคุณ โปรแกรมที่สั้นที่สุดในการทำเช่นนี้ในภาษาใดก็ได้

5 Comments
xnor 03/06/2015
ฉันไม่ได้เป็นแฟนของความต้องการรูปแบบเอาต์พุตโดยเฉพาะอย่างยิ่งการแปลงเป็นตัวอักษร a-u เราสามารถแสดงผลลัพธ์ของตัวเลขได้หรือไม่?
3 Optimizer 03/06/2015
คุณอาจต้องการยอมรับคำตอบหลังจากบางเวลาเนื่องจากบางคนมักไม่ตอบคำถามหากมีคำตอบที่ยอมรับ
1 Optimizer 03/06/2015
ดังนั้นคุณจึงมีคำตอบที่ยอมรับผิด
2 Joe Z. 03/06/2015
FryAmTheEggman โพสต์คำตอบของเขา 21 นาทีก่อนที่คุณจะแก้ไข
2 Joe Z. 03/06/2015
@ Optimizer ฉันไม่ค่อนข้างคิดว่ามันเป็นวิธีแปลกประหลาด - คำตอบของ FryAmTheEggman คือ 19 byte 21 นาทีก่อนที่คุณจะเป็น ที่ทำให้คำตอบสั้นที่สุดที่โพสต์ไว้

10 Answers


Optimizer 03/06/2015.

CJam, 22 20 19 17 ไบต์

]]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 :

นี่คือโค้ดการแก้ปัญหาของโค้ด:

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

ลองดูวิธีการทำงานสำหรับการป้อนข้อมูล 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>|}/"; 

ลองใช้แบบออนไลน์ได้ที่นี่


alephalpha 03/06/2015.

Haskell, 47 ไบต์

f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1 
3 comments
1 nimi 03/06/2015
การสลับไปยังรายการความเข้าใจจะบันทึกไม่กี่ไบต์: f n=[[n:x,x++[n]]|x<-f$n-1]>>=id (ใช้ฟังก์ชันรหัสนักกอล์ฟ <concat >>=id )
1 proud haskeller 03/07/2015
@ nimi แต่อยู่ในลำดับที่ไม่ถูกต้อง r
nimi 03/08/2015
@proudhaskeller: โอ้ที่รักไม่ได้อ่านข้อมูลจำเพาะอย่างละเอียดพอ ฉันพยายามที่จะแก้ไขปัญหานี้และพบวิธีที่ต่างกันเล็กน้อยสี่แบบซึ่งมีความยาวเช่นเดียวกับเวอร์ชันของ @ alephalpha ดังนั้นฉันจึงไม่สามารถปรับปรุงได้ 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.

งูใหญ่ 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)] 

แสดงรายการลิสต์ของตัวเลข

วิธีแก้ปัญหาแบบเวียนเกิด สำหรับ n==1 ให้ผลลัพธ์ [[1]] มิฉะนั้นให้เพิ่ม n ไปที่จุดเริ่มต้นหรือสิ้นสุดของทั้งหมด (n-1) -permutations Prepending ทำให้การแปลงค่า lexicographically ภายหลังกว่า appending ดังนั้นการเรียงสับเปลี่ยนยังคงเรียงลำดับ

"บูลีน" b encodes ว่าจะใส่ [n] ที่เริ่มต้นหรือสิ้นสุด จริงๆแล้วเราย้ายส่วนที่เหลือของรายการ x ในนิพจน์ x*b+[n]+x*-b การวาง b เป็น -1 หรือ 1 ให้ใช้พลิกโดยการลบล้างเนื่องจากรายการคูณด้วย -1 คือรายการที่ว่างเปล่า


FryAmTheEggman 03/06/2015.

Pyth, 19

usCm,+dH+HdGr2hQ]]1 

ลองใช้แบบออนไลน์ได้ที่นี่

นี้เป็นโปรแกรมที่เต็มรูปแบบที่จะนำเข้าจาก stdin

วิธีนี้ทำงานในรูปแบบเดียวกับโซลูชันของ xnor แต่จะสร้างค่าไม่มากจนเกินไปดังนั้นต้องเรียงลำดับใหม่ สิ่งที่เกิดขึ้นในแต่ละระดับคือแต่ละรายการก่อนหน้าของค่ามีค่าใหม่เพิ่มไปยังจุดสิ้นสุดและจุดเริ่มต้นและแต่ละส่วนเหล่านี้ถูกห่อไว้ใน 2-tuple ซึ่งห่อไว้ในรายการ ตัวอย่างเช่นขั้นตอนแรกทำเช่นนี้:

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

จากนั้นรายการนี้ของ tuples จะถูกบีบอัด (และสรุปเพื่อลบรายการที่อยู่นอกสุด) ในกรณีแรกนี่เป็นการให้ค่าที่ยังไม่ได้แกะสลักจากด้านบนเนื่องจากมีเพียงค่าเดียวในรายการเท่านั้น

ขั้นตอนที่แสดง 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 

ตัวอย่าง:

f[4] 

{1, 2, 3, 4}, {3, 2, 3, 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 ไบต์

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

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

การปรับปรุง 1 ไบต์ด้วย FUZxxl

1 comments
FUZxxl 03/06/2015
ทดแทน ,. สำหรับ ,"1 สำหรับอักขระหนึ่งตัว

Pietu1998 04/13/2017.

Pyth, 343331 29

โดยทั่วไปการแปล คำตอบ Python ของ xnor ฉันยังคงไม่ดีกับ Pyth ดังนั้นข้อเสนอแนะในการปรับปรุงจึงน่ายินดี

กำหนดฟังก์ชัน y เพื่อแสดงรายการของจำนวนเต็ม

L?]]1 

Update: บันทึก 2 bytes ขอบคุณ FryAmTheEggman

คำอธิบาย:

L                                  define a function y with argument b that returns
 ?*]]1 
4 comments
FryAmTheEggman 03/06/2015
บางสิ่งที่ pyth: -b1 สามารถ tb , [1_1) สามารถเป็นได้ ,1_1 (แต่คุณสามารถวางวงเล็บใกล้ได้เนื่องจากคุณจำเป็นต้องนับไบต์ที่จำเป็นเพื่อให้ฟังก์ชันถึงแม้ว่าคุณจะไม่สามารถโทรออกได้ โดยไม่ต้องปิด) และคุณไม่จำเป็นต้องห่อ b ในรายการเนื่องจาก pyth จะแปลงเป็นรายการโดยอัตโนมัติเมื่อเพิ่มรายการลงใน int
FryAmTheEggman 03/06/2015
ฉันได้วิธีการบันทึกหลายไบต์ด้วยการทำแผนที่ที่สองด้วยตนเอง [1,-1] ฉันสามารถบันทึกไบต์เพื่อ hardcode บางอย่างที่สั้นโดยเฉพาะอย่างยิ่งเมื่อคุณลดความซับซ้อนของตรรกะ ฉันได้รับ L?]]1
Pietu1998 03/06/2015
@FryAmTheEggman คุณอาจต้องการเพิ่มว่าเป็นคำตอบของคุณเอง น่ากลัวจริงๆ
FryAmTheEggman 03/06/2015
ตกลงฉันต้องการพยายามเอาชนะ CJam ก่อนโพสต์ แต่ฉันเดาเคล็ดลับซิปที่น่าสนใจพอที่จะทำบุญโพสต์ได้ ขอให้โชคดีกับ Pyth;)

edc65 03/07/2015.

JavaScript (ES6) 73 80

การใช้งาน JavaScript ของ @ Optimizer's solution ที่ดี

recursive (73):

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

Iterative (74):

 F=n=>(i=>NO 

Test ใน Firefox / FireBug console

 R(4) 

[1, 2, 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

นานกว่าที่ฉันหวังไว้:

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.

โซลูชัน Java ของฉัน:

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
ตอนนี้หลังจากได้เห็นคำตอบอื่นแล้วฉันเห็นว่าคุณหมายถึงอะไรเกี่ยวกับคำตอบที่สั้นที่สุด
2 Joe Z. 03/08/2015
ในขณะที่โซลูชันของคุณมีความน่าเชื่อถือรัดกุมและนำเสนอด้วยความคิดเห็นของตนเองคุณจะแก้ไขได้ว่าไม่ใช่ปัญหาที่เกิดขึ้นในมือ
1 ProgramFOX 03/08/2015
@BrettRyan คุณสามารถทำให้โค้ดของคุณสั้นลงโดยลบช่องว่างที่ไม่จำเป็นและใช้ชื่อตัวแปรแบบหนึ่งอักขระ นอกจากนี้คุณยังสามารถแทนที่ false โดยสิ่งที่ต้องการ 5<4
1 Brett Ryan 03/08/2015
ขอบคุณเพื่อน. นี่เป็นความพยายามครั้งแรกของฉันที่มีส่วนร่วมในการท้าทายโค้ด ฉันเพิ่งมองหาความท้าทายในการเขียนโปรแกรมบางส่วนและไม่ตระหนักว่าเป้าหมายคือเพื่อให้ได้โซลูชันที่สั้นที่สุด ขอบคุณที่ให้ฉันเข้าร่วม

Related questions

Hot questions

Language

Popular Tags