Комбинации с повторением

Вы можете кодировать каждую комбинацию как {na,nb,nc,nd}, где na указывает количество появлений a. Затем задача состоит в том, чтобы найти все возможные комбинации из 4 неотрицательных целых чисел, которые в сумме дают 3. 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 и Tuples для этой задачи в лог-секундах.

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]

_{(источник: yaroslavvb .com)}

Вот простое решение, которое использует преимущества встроенных функций Mathetmatica Subsets и, таким образом, обеспечивает хороший баланс между простотой и производительностью. Существует простая биекция между k-подмножествами [n + k-1] и k-комбинациями [n] с повторением. Эта функция преобразует подмножества в комбинации с повторением.

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

So

CombWithRep[4,2]

дает

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

Небольшой вариант элегантного метода, данного High Performance Mark:

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]

Редактировать-3.

Два подхода будут отличаться, если список содержит повторяющийся элемент. Например, результат следующего (подход 2) будет содержать дубликаты (которые могут быть, а могут и не быть желательными):

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

От них легко избавиться:

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

Следующее оценивается как «Истина» (удалить повторяющиеся элементы из списка, представленного для подхода 2, и отсортировать список, созданный для подхода 1 (метод High Performance Mark):

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

Извини за это!