Kombinationen mit Wiederholung

Question

Ich bin mit Mathematica 7 und mit einem combinatorica Paket Funktion kann ich alle Kombinationen einer bestimmten Nummer aus einer Liste von Elementen, wo die Reihenfolge keine Rolle spielt und es gibt keine repetition.eg:

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

Ich kann keine Funktion finden, die mir alle Kombinationen einer bestimmten Nummer aus einer Liste von Elementen gibt, wo die Reihenfolge keine Rolle spielt und ist Wiederholung. , d.h. das obige Beispiel würde Elemente wie {a, a, b}, {a, a, a}, {b, b, b} ... etc in der Ausgabe enthalten.

Es kann eine benutzerdefinierte Funktion erfordern. Wenn ich mir eine ausdenken kann, werde ich eine Antwort schreiben, aber im Moment sehe ich keine offensichtliche Lösung.

Edit: Idealerweise enthält die Ausgabe keine Verdoppelung einer Kombination, z. Tupel [{a, b, c, d}, 3] werden eine Liste zurückgeben, die zwei Elemente wie {a, a, b} und {b, a, a} enthält, die aus einer Kombination Sicht sind gleich.

Answer 1

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

Answer 2

Sie können jede Kombination als {na,nb,nc,nd} codieren, wobei na angibt, wie oft a angezeigt wird. Die Aufgabe ist dann, alle möglichen Kombinationen von 4 nichtnegativen ganzen Zahlen zu finden, die sich zu 3 addieren. IntegerPartition gibt einen schnellen Weg, all solche Kombinationen zu erzeugen, wo die Reihenfolge keine Rolle spielt, und Sie folgen ihm mit Permutations, um verschiedene Aufträge zu berücksichtigen

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] 

Just for fun, hier ist Timing-Vergleich zwischen IntegerPartitions und Tupeln für diese Aufgabe, in Log-Sekunden

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

Eine leichte Variante der elegante Methode von High Performance Mark gegeben:

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

Permutationen etwas vielseitiger ist (aber nicht das, was Sie suchen?)

Zum Beispiel:

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

ergibt folgende

Edit:

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

ist wahrscheinlich besser

Bearbeiten-2

Natürlich Fälle können auch verwendet werden. Zum Beispiel

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

Edit-3.

Die beiden Ansätze unterscheiden sich, wenn die Liste ein wiederholtes Element enthält.Die Ausgabe von nach dem (Ansatz 2), zum Beispiel, werden Duplikate enthalten (die erwünscht sein können oder auch nicht):

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

Sie leicht losgeworden werden können:

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

Die folgende auswertet auf ‚True‘ (um doppelte Elemente aus der Liste dargestellt 2 zu nähern, und Sortieren der durch Ansatz hergestellt Liste 1 (High Performance Mark-Methode):

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

wie t tut er folgende (Duplikate entfernen vom Ausgang des Ansatzes 2, Sortierleistung von Ansatz 1):

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

Traurig über das!

Answer 4

Hier ist eine einfache Lösung, die die in Mathetmatica integrierten Funktions-Subsets nutzt und somit ein gutes Gleichgewicht zwischen Einfachheit und Leistung bietet. Es gibt eine einfache Bijektion zwischen k-Teilmengen von [n + k-1] und k-Kombinationen von [n] mit Wiederholung. Diese Funktion ändert Teilmengen in Kombinationen mit Wiederholungen.

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

So

CombWithRep[4,2] 

ergibt

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