20

我正在寻找一种有效的方法来实现这一目标：

  • 您有一个数字列表 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'quick 算法？

谢谢！

4

3 回答 3

41

不是我的代码，但您正在寻找 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

于 2010-07-23T15:30:02.567 回答
39

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

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

这将产生有序排列。也就是说，只会{1, 2, 3}生成。不{1, 3, 2}或{2, 1, 3}或{2, 3, 1}等。

于 2010-07-23T15:21:59.063 回答
12

这是我过去为了完成这样的任务而写的。

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 等。

于 2010-07-23T15:26:37.110 回答