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

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),并且它们似乎总是在单个字符串或数字上运行....

任何人都有一个伟大的,漂亮的'快速算法？

谢谢!

Answer 1

只需递增二进制数并获取与设置的位对应的元素.

例如,00101101意味着获取索引0,2,3和5处的元素.因为您的列表只是1..n,所以元素只是索引+ 1.

这将生成有序的permuatations.换句话说,只会{1, 2, 3}生成.没有{1, 3, 2}或{2, 1, 3}或{2, 3, 1}等

Answer 2

不是我的代码,但你正在寻找powerset.谷歌给了我这个解决方案,这似乎工作:

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

它是通用的,因此它适用于整数,长整数,字符串,Foos等.