从数字列表中获取所有可能的组合

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 的所有组的问题该列表中的数字

似乎应该有一个简单的算法 - 但到目前为止我的搜索是徒劳的。大多数组合和排列算法似乎 a) 考虑顺序（例如 123 不等于 132），并且它们似乎总是对单个字符或数字字符串进行操作......

任何人都有一个伟大的，nice'n'他们的快速算法？

谢谢！

Answer 1

不是我的代码，但您正在寻找电源集。谷歌给了我这个解决方案，这似乎不起作用：

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 2

只需增加一个二进制数并获取与所设置的位相对应的元素即可。

例如，00101101 表示获取索引 0、2、3 和 5 处的元素。由于您的列表只是 1..n，因此该元素只是索引 + 1。

这将生成- 顺序排列。换句话说，只会生成 {1, 2, 3}。不是 {1, 3, 2} 或 {2, 1, 3} 或 {2, 3, 1} 等。

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

它是通用的，因此适用于整数、长整型、字符串、Foos 等。