Я ищу эффективный способ добиться этого:
у вас есть список чисел 1..... n (обычно: 1..5 или 1..7 или около того - достаточно маленький, но может варьироваться от случая к случаю)
вам нужны все комбинации всех длин для этих чисел, например. все комбинации одного числа ({1}, {2},.... {n}), затем все комбинации двух различных чисел ({1,2}, {1,3}, {1,4}..... {n-1, n}), то все комбинации fo трех из этих чисел ({1,2,3}, {1,2,4}) и т.д.
В принципе, внутри группы порядок не имеет значения, поэтому {1,2,3} эквивалентен {1,3,2} - это просто вопрос получения всех групп из x чисел из этого списка
Похоже, для этого должен быть простой алгоритм, но до сих пор я тщетно искал. Большинство комбинаторика и алгоритмы перестановок, по-видимому, a) учитывают порядок (например, 123 не равно 132), и они всегда работают на одной строке символов или чисел....
У кого-нибудь есть отличный, хороший алгоритм с их рукавом?
Спасибо!
Просто увеличьте двоичное число и возьмите элементы, соответствующие установленным битам.
Например, 00101101 означало бы брать элементы в индексах 0, 2, 3 и 5. Так как ваш список равен просто 1..n, этот элемент - это просто индекс + 1.
Это приведет к появлению перестановок в порядке. Другими словами, будет генерироваться только {1, 2, 3}. Не {1, 3, 2} или {2, 1, 3} или {2, 3, 1} и т.д.
Не мой код, но вы ищете poweret. Google дал мне это решение, которое, похоже, работает:
public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
return from m in Enumerable.Range(0, 1 << list.Count)
select
from i in Enumerable.Range(0, list.Count)
where (m & (1 << i)) != 0
select list[i];
}
Это то, что я написал в прошлом, чтобы выполнить такую задачу.
List<T[]> CreateSubsets<T>(T[] originalArray)
{
List<T[]> subsets = new List<T[]>();
for (int i = 0; i < originalArray.Length; i++)
{
int subsetCount = subsets.Count;
subsets.Add(new T[] { originalArray[i] });
for (int j = 0; j < subsetCount; j++)
{
T[] newSubset = new T[subsets[j].Length + 1];
subsets[j].CopyTo(newSubset, 0);
newSubset[newSubset.Length - 1] = originalArray[i];
subsets.Add(newSubset);
}
}
return subsets;
}
Он общий, поэтому он будет работать для ints, longs, string, Foos и т.д.