辞書順にソートされた順序でプリペンド・アペンド・パーミュテーションの集合を生成する

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

長さn prepend-append sequenceを、次の手順で生成できる数字1, 2, ..., n順列として定義します。

  • 番号1始めましょう。

  • 2からnまでの各番号n 、この番号をシーケンスの先頭または末尾にprepend appendprependまたはappendに付けるか、シーケンスの名前にする)。

たとえば、これは長さ4のプリペンド・アペンド・シーケンスを生成する有効な方法です。

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

あなたの仕事は、入力として3から30までのnを取るプログラムまたは関数を構築し、長さnすべてのプリペンド・アペンド・シーケンスを辞書順に返します(文字列を出力し、 9は文字列a-uとして表され、文字列の長さを保持します)。 たとえば、これはn = 4順序です。

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

一般に、長さn 2 n-1個の前置詞付加順列が存在する。

あなたのコードではあなたの言語で組み込みのソート関数を使うことはできません。 あらゆる言語でこれを行うための最短のプログラムが勝利します。

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の答えはあなたの21分前に19バイトの長さだった。 それはそれを最も早く投稿した最短の答えにします。

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.

ハスケル、47バイト

f 1=[[1]]
f n=(\x->map(++[n])x++map(n:)x)$f$n-1 
3 comments
1 nimi 03/06/2015
list comprehensionに切り替えると、 f n=[[n:x,x++[n]]|x<-f$n-1]>>=id (code-golfer concat関数>>=id )が保存されます。
1 proud haskeller 03/07/2015
@ニミが間違った順序で
nimi 03/08/2015
@proudhaskeller:ああああ、慎重に十分に仕様を読んでいない。 私はそれを修正しようとし、@ alephalphaのバージョンと同じ長さの4つのやや異なる方法を見つけましたので、改善はできません。 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=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-1)回の完全修飾の開始または終了にnを追加します。 Prependingは、置換よりも後で置換を辞書的に行うので、置換はソートされたままになります。

「ブール値」 bは、 [n]を開始または終了のどちらに入れるのかをエンコードします。 実際には、リストx残りを式x*b+[n]+x*-bます。 -1 1すると、 -1掛けたリストが空のリストに-1ので、 b-1または1すると、反転で反転が使用されます。


FryAmTheEggman 03/06/2015.

Pyth、19

usCm,+dH+HdGr2hQ]]1 

オンラインで試してみてください

これはstdinから入力を受け取る完全なプログラムです。

これはxnorのソリューションと同様に動作しますが、値が少し乱れるので、並べ替えが必要です。 各レベルで何が起こるかは、以前の各値のリストに新しい値が最後と最初に追加され、2つのタプルがそれぞれリストにまとめられてラップされます。 たとえば、最初の手順ではこれを行います。

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

次に、このタプルのリストが圧縮されます(そして、最も外側のリストを削除するために合計されます)。 最初のケースでは、リストの値が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,3,1}、{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 

FUZxxlのおかげで1バイトの改善。

1 comments
FUZxxl 03/06/2015
代理人,. for ,"1つの文字に対して1。

Pietu1998 04/13/2017.

Pyth、 343331 29

基本的にxnorPythonの解答です。 私はまだPythと偉大ではないので、改善の提案は大歓迎です。

整数のリストのリストを返す関数yを定義します。

L?]]1 

Update: FryAmTheEggmanのおかげで2バイト節約できました

説明:

L                                  define a function y with argument b that returns
 ?*]]1 
4 comments
FryAmTheEggman 03/06/2015
いくつかのpythもの: -b1tb[1_1)でも可能です(ただし、呼び出すことはできませんが、関数を作成するために必要なバイト数を数えればよいので、リストをintに追加するときにpythがリストに自動的に変換するので、リスト内でbをラップする必要はありません。
FryAmTheEggman 03/06/2015
私は手動で[1,-1]上の2番目のマップを実行することによっていくつかのバイトを節約する方法を考え出しました。 特にロジックを単純化すると、バイトを節約してハードコードすることができます。 私はL?]]1を得るL?]]1
Pietu1998 03/06/2015
@FryAmTheEggman実際にあなた自身の答えとしてそれを追加したいかもしれません。 それはちょうど素晴らしいです。
FryAmTheEggman 03/06/2015
OK、私はポストする前にCJamを打ち負かそうとしたかったが、私はzipトリックがそれをポストする価値があるほど面白いと思う。 ピースと幸運を祈る;)

edc65 03/07/2015.

JavaScript(ES6)73 80

オプティマイザの素晴らしいソリューションのJavaScript実装。

再帰的(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 

Firefox / FireBugコンソールでTest

 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不要な空白を削除し、1文字の変数名を使用することでコードを大幅に短縮できます。 false5<4ように置き換えることもできます。
1 Brett Ryan 03/08/2015
みんなありがとう。 コードチャレンジに参加する私の最初の試みでした。 私はちょうどいくつかのプログラミングの課題を探していて、目標が最短の解決策を得ることではないことを認識していませんでした。 :)参加してくれてありがとう。

Related questions

Hot questions

Language

Popular Tags