Генеруйте набір перекладок prepend-add у лексикографічно відсортованому порядку

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

Визначте prepend-append sequence до довжини n щоб бути перестановкою цифр 1, 2, ..., n яка може бути згенерована наступною процедурою:

  • Почніть з числа 1 .

  • Для кожного числа від 2 до n , помістіть цей номер на початок або кінець послідовності (або prepend або append його, отже, назву послідовності).

Наприклад, це правильний спосіб створити послідовність prepend-add до довжини 4:

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

Ваше завдання полягає в тому, щоб побудувати програму або функцію, яка займає число n від 3 до 30 як вхідний, і друкувати або повертати всі prepend-додавати послідовності довжини 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 prepend-append перестановок довжини 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 байтів за 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 функція code-golfers >>=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.

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

Виводить список списків номерів.

Рекурсивне рішення. Для n==1 , вихід [[1]] . В іншому випадку додайте n до початку або закінчення всіх (n-1) -перестановок. Приєднання робить перестановку лексикографічно пізніше додавання, тому перестановки залишаються відсортованими.

"Булево" b кодує, чи слід розміщувати [n] на початку або в кінці. Насправді ми переміщаємо решту списку x у виразі x*b+[n]+x*-b . Встановлення b як -1 або 1 дозволяє використовувати фліп за допомогою заперечення, оскільки список, помножений на -1 є порожнім.


FryAmTheEggman 03/06/2015.

Піт, 19

usCm,+dH+HdGr2hQ]]1 

Спробуйте онлайн тут

Це повна програма, яка приймає дані від stdin.

Це працює так само, як і рішення xnor, але генерує значення трохи поза порядку, тому їх треба перевпорядковувати. Те, що відбувається на кожному рівні, полягає в тому, що кожен попередній список значень має нове значення, додане до кінця і до початку, і кожен з них обертається двотавровим, який обертається разом у списку. Наприклад, перший крок робить це:

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

Потім цей список кортежів стискається (а потім підсумовується, щоб видалити найдальший список). У першому випадку це просто дає розгорнуте значення згори, оскільки в списку є лише одне значення.

Кроки, що показують 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 байт

f@1=NO 

Приклад:

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 байт

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

В основному переклад з xnor 's Python відповідь . Я все ще не відмінно співпрацюю з Pyth, тому бажано вдосконалити пропозиції.

Визначає функцію y щоб повернути список списків цілих чисел.

L?]]1 

Update: Збережено 2 байти завдяки FryAmTheEggman .

Пояснення:

L                                  define a function y with argument b that returns
 ?*]]1 
4 comments
FryAmTheEggman 03/06/2015
Деякі п'ять елементів: -b1 може бути tb , [1_1) може бути ,1_1 (однак ви можете просто скинути закриті кронштейни, оскільки потрібно лише підрахувати байти, необхідні для виконання функції, навіть якщо ви не зможете зателефонувати це, не закриваючи його), і вам не потрібно обертати b у списку, оскільки pyth автоматично перетворює його в список при додаванні списку до int.
FryAmTheEggman 03/06/2015
Я придумав спосіб зберегти кілька байтів, вручну здійснивши другу карту [1,-1] . Я можу зберегти байтів до жорсткого коду щось коротке, особливо, коли ви спрощуєте логіку. Я отримую L?]]1
Pietu1998 03/06/2015
@FryAmTheEggman Можливо, ви хочете додати цей варіант як власну відповідь. Це просто чудово.
FryAmTheEggman 03/06/2015
Гаразд, я хотів спробувати побити CJam перед публікацією, але я думаю, що блискавка є досить цікавою, щоб заслужити публікацію. Удачи з Pyth;)

edc65 03/07/2015.

JavaScript (ES6) 73 80

JavaScript реалізація приємного рішення @ Optimizer.

Рекурсивний (73):

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

Ітеративний (74):

 F=n=>(i=>NO 

Test в консолі 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.

Чистий Баш, 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