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

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

有人掌握了伟大、快捷的算法吗？

谢谢!

- marc_s

---

你基本上是在寻找你列表的幂集（如果它的所有项都是唯一的，从数学上讲实际上是一个集合）。 - Justin L.

请参见此处：https://dev59.com/mWsz5IYBdhLWcg3wlYwn#41642733 - RenniePet

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

- Henri

---

为了澄清，这是我的答案，使用LINQ实现。我必须承认，这非常聪明。 - jdmichal

LINQ的威力，值得我们停下脚步感叹一下。 - Rev

可以运行，但仅适用于具有不到32个元素的列表，因为Enumerable.Range将第二个参数限制为类型"int"。 - Kyle Ross

Answer 2

只需将二进制数字递增，并取出对应于已设置位的位元素。

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

这将生成有序排列。换句话说，只会生成{1,2,3}，而不是{1,3,2}、{2,1,3}或{2,3,1}等其他排列。

- jdmichal

---

@Henri的解决方案基本上是使用LINQ实现这个想法。 - Nate Kohl

@Nate Kohl，是的，我刚才评论了那个。非常聪明！我点了一个赞。 - jdmichal

+1：一个很好的证明，即给定大小为N的集合的子集数量是2^N。 - Eyal Schneider

这是一个很棒的答案！ - Radmation

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

这是一个通用的函数，适用于整数、长整型、字符串、Foo等类型。

- Anthony Pegram

---

例如，对于 List<int>，您可以将其称为 var newList = CreateSubsets<int>(sourceList.ToArray())。 - PeterJ