Получение всех возможных комбинаций из списка номеров

Question

Я ищу эффективный способ добиться этого:

• у вас есть список чисел 1 ..... n (обычно: 1..5 или 1..7 или около того - достаточно мало, но может варьироваться от случая к случаю)

• вам нужны все комбинации всех длин для этих чисел, например, все комбинации только одного числа ({1}, {2}, .... {n}), затем все комбинации двух разных чисел ({1,2}, {1,3}, {1,4} ..... {n-1, n}), затем все комбинации для трех из этих чисел ({1,2,3}, {1,2,4}) и т. д.

По существу, внутри группыпорядок не имеет значения, поэтому {1,2,3} эквивалентен {1,3,2} - это просто вопрос получения всех групп чисел x из этого списка

Похоже, что должно бытьпростой алгоритм для этого - но я тщетно искал до сих пор.Большинство комбинаторных и перестановочных алгоритмов, кажется, а) принимают во внимание порядок (например, 123 не равен 132), и они всегда, кажется, работают с одной строкой символов или чисел ....

У любогоотличный, хороший и быстрый алгоритм в рукаве ??

Спасибо!

Answer 1

Просто увеличьте двоичное число и возьмите элементы, соответствующие установленным битам.

Например, 00101101 будет означать, что элементы взяты с индексами 0, 2, 3 и 5. Поскольку ваш списокпросто 1..n, элемент просто индекс + 1.

Это будет генерировать перестановки в порядке.Другими словами, будет сгенерировано только {1, 2, 3}.Не {1, 3, 2} или {2, 1, 3} или {2, 3, 1} и т. Д.

Answer 2

Не мой код, но вы ищете блок питания. 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];
}

Источник: http://rosettacode.org/wiki/Power_set#C.23

Answer 3

Это то, что я написал в прошлом для выполнения такой задачи.

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; 
}

Это универсальный тип, поэтому он будет работать с целыми числами, long, строками, Foos и т.д.