从数字列表中获取所有可能的组合
从数字列表中获取所有可能的组合
提问于 2010-07-23 23:20:40
我正在寻找一种有效的方法来实现这一点：
- 您有一个数字列表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)，并且它们似乎总是对单个字符串或数字进行操作。
有没有人有一个很棒，很好的快速算法？
谢谢!
回答 3
Stack Overflow用户
回答已采纳
发布于 2010-07-23 23:21:59
只需递增一个二进制数，并获取与所设置的位相对应的元素。
例如，00101101表示取索引0、2、3和5处的元素，因为您的列表只有1..n，所以元素就是索引+1。
这将生成有序排列。换句话说，只会生成{1, 2, 3}。而不是{1, 3, 2}、{2, 1, 3}或{2, 3, 1}等。
Stack Overflow用户
发布于 2010-07-23 23:30:03
不是我的代码，但你要找的是动力装置。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];
}Stack Overflow用户
发布于 2010-07-23 23:26:37
这是我在过去为完成这样的任务而编写的东西。
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等。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3319586
复制相关文章
相似问题