繰り返しを使った組み合わせ

Question

私はMathematica 7とcombinatoricaのパッケージ関数を使用しています。順序は関係ありません。繰り返しはありません：

in: KSubsets[{a, b, c, d}, 3] 
out: {{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}} 

注文番号と関係のない要素のリストから特定の番号のすべての組み合わせを得る関数が見つかりません。はです。上記の例では、出力に{a、a、b}、{a、a、a}、{b、b、b} ...などの要素が含まれています。

カスタム機能が必要な場合があります。私が1つを思いつくことができるなら、私は答えを掲示するだろうが、今のところ明らかな解決策は見当たらない。

編集： 出力には組み合わせの重複が含まれないことが理想的です。 タプル[{a、b、c、d}、3] は、{a、a、b}と{b、a、a}のような2つの要素を含むリストを返します。 同じ。

Answer 1

DeleteDuplicates[Map[Sort, Tuples[{a, b, c, d}, 3]]] 

Answer 2

{na,nb,nc,nd}のように各組み合わせをエンコードすることができます。ここで、naは、aの番号が表示されます。次に、3までの4つの非負整数の可能な組み合わせをすべて見つけることです。IntegerPartitionは、順序が重要でないような組み合わせをすべて高速に生成し、異なる注文を考慮してPermutationsに従います

vars = {a, b, c, d}; 
len = 3; 
coef2vars[lst_] := 
Join @@ (MapIndexed[Table[vars[[#2[[1]]]], {#1}] &, lst]) 
coefs = Permutations /@ 
    IntegerPartitions[len, {Length[vars]}, Range[0, len]]; 
coef2vars /@ Flatten[coefs, 1] 

楽しみのためだけに、ここでは、このタスクのためにIntegerPartitionsとタプルの間の比較のタイミングのログ-秒で

approach1[numTypes_, len_] := 
    Union[Sort /@ Tuples[Range[numTypes], len]]; 
approach2[numTypes_, len_] := 
    Flatten[Permutations /@ 
    IntegerPartitions[len, {numTypes}, Range[0, len]], 1]; 

plot1 = ListLinePlot[(AbsoluteTiming[approach1[3, #];] // First // 
     Log) & /@ Range[13], PlotStyle -> Red]; 
plot2 = ListLinePlot[(AbsoluteTiming[approach2[3, #];] // First // 
     Log) & /@ Range[13]]; 
Show[plot1, plot2] 

http://yaroslavvb.com/upload/save/tuples-vs-partitions.png

Answer 3

高性能マークによって与えられたエレガントな方法に若干のバリエーション：

Select[Tuples[{a, b, c, d}, 3], OrderedQ] 

順列はもう少し汎用性があります（ただし、あなたが探している？）例えば

：

Select[Permutations[ 
    Sort@Flatten@ConstantArray[{a, b, c, d}, {3}], {2, 3}], OrderedQ] 

は次のようになります。

編集：もちろん

Select[Tuples[Sort@{a, b, d, c}, 3], OrderedQ] 

は、おそらく優れている

編集-2

、ケースを使用することもできます。たとえば、

Cases[Permutations[ 
    Sort@Flatten@ConstantArray[{a, b, d, c}, {3}], {2, 3}], _?OrderedQ] 

Edit-3

リストに繰り返し要素が含まれる場合、2つの方法が異なります。 からの出力、例えば、（または所望されなくてもよい）重複を含むであろう（アプローチ2）以下：

Select[Tuples[{a, b, c, d, a}, 3], OrderedQ] 

それらは容易に処分したことができる

：

Union@Select[Tuples[{a, b, c, d, a}, 3], OrderedQ] 

ザ「真」と評価されたが、次の（1アプローチ（ハイパフォーマンスマーク法）によって生成されるリスト2に近づくために提示されたリストから重複要素を削除、および並べ替え：

lst = RandomInteger[9, 50]; 
Select[Union@Sort@Tuples[lst, 3], OrderedQ] == 
Sort@DeleteDuplicates[Map[Sort, Tuples[lst, 3]]] 

トンがそうであるように彼は従う（アプローチ2の出力から重複を取り除き、アプローチ1の出力をソートする）：

lst = RandomInteger[9, 50]; 
Union@Select[Sort@Tuples[lst, 3], OrderedQ] == 
Sort@DeleteDuplicates[Map[Sort, Tuples[lst, 3]]] 

ごめんなさい！

Answer 4

ここでは、Mathetmaticaの組み込み関数サブセットを利用する単純なソリューションがあり、シンプルさとパフォーマンスのバランスがとれています。 [n + k-1]のkサブセットと[n]のk組み合わせの間に反復を伴う単純な双投射が存在する。この関数は、サブセットを繰り返しの組み合わせに変更します。

CombWithRep[n_, k_] := #-(Range[k]-1)&/@Subsets[Range[n+k-1],{k}] 

ので

CombWithRep[4,2] 

利回り

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