Получение всех возможных комбинаций из списка чисел
Я ищу эффективный способ достигнуть этого:
у Вас есть список чисел 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), и они всегда, кажется, воздействуют на единственную строку символов или чисел....
У кого-либо есть великое, nice'n'quick алгоритм их рукав??
Спасибо!
3 ответа
Просто увеличьте двоичное число и возьмите элементы, соответствующие установленным битам.
Например, 00101101 будет означать брать элементы с индексами 0, 2, 3 и 5. Поскольку ваш список просто 1..n, элемент - это просто индекс + 1.
Это сгенерирует перестановки по порядку. Другими словами, будет сгенерировано только {1, 2, 3} . Не {1, 3, 2} или {2, 1, 3} или {2, 3, 1} и т. Д.
Это то, что я писал в прошлом, чтобы достичь такого задача.
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;
}
Это общий параметр, поэтому он будет работать с целыми числами, длинными, строками, символами Foo и т. Д.
Это не мой код, но вы ищете powerset. 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];
}