C# 列出 1...n 之间 k 个整数的所有可能组合（n 选择 k）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/548402/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
List all possible combinations of k integers between 1...n (n choose k)
提问by Asaf R
Out of no particular reason I decided to look for an algorithm that produces all possible choices of k integers between 1...n, where the order amongst the k integer doesn't matter (the n choose k thingy).
出于没有特别的原因，我决定寻找一种算法，该算法可以生成 1...n 之间 k 个整数的所有可能选择，其中 k 个整数之间的顺序无关紧要（n 选择 k 个事物）。
From the exact same reason, which is no reason at all, I also implemented it in C#. My question is:
出于完全相同的原因，完全没有理由，我也在 C# 中实现了它。我的问题是：
Do you see any mistake in my algorithm or code? And, more importantly, can you suggest a better algorithm?
你在我的算法或代码中看到任何错误吗？而且，更重要的是，你能提出一个更好的算法吗？
Please pay more attention to the algorithm than the code itself. It's not the prettiest code I've ever written, although do tell if you see an error.
请更多地关注算法而不是代码本身。这不是我写过的最漂亮的代码，但如果您看到错误，请告诉我。
EDIT:Alogirthm explained -
编辑：算法解释 -
- We hold k indices.
- This creates k nested forloops, where loop i's index is indices[i].
- It simulates k forloops where indices[i+1] belongs to a loop nested within the loop of indices[i].
- indices[i] runs from indices[i - 1] + 1 to n - k + i + 1.
- 我们持有 k 个指数。
- 这将创建 k 个嵌套的for循环，其中循环 i 的索引是索引 [i]。
- 它模拟 k 个for循环，其中索引 [i+1] 属于嵌套在索引 [i] 循环中的循环。
- 索引[i] 从索引[i - 1] + 1 到 n - k + i + 1。
CODE:
代码：
public class AllPossibleCombination
{
int n, k;
int[] indices;
List<int[]> combinations = null;
public AllPossibleCombination(int n_, int k_)
{
if (n_ <= 0)
{
throw new ArgumentException("n_ must be in N+");
}
if (k_ <= 0)
{
throw new ArgumentException("k_ must be in N+");
}
if (k_ > n_)
{
throw new ArgumentException("k_ can be at most n_");
}
n = n_;
k = k_;
indices = new int[k];
indices[0] = 1;
}
/// <summary>
/// Returns all possible k combination of 0..n-1
/// </summary>
/// <returns></returns>
public List<int[]> GetCombinations()
{
if (combinations == null)
{
combinations = new List<int[]>();
Iterate(0);
}
return combinations;
}
private void Iterate(int ii)
{
//
// Initialize
//
if (ii > 0)
{
indices[ii] = indices[ii - 1] + 1;
}
for (; indices[ii] <= (n - k + ii + 1); indices[ii]++)
{
if (ii < k - 1)
{
Iterate(ii + 1);
}
else
{
int[] combination = new int[k];
indices.CopyTo(combination, 0);
combinations.Add(combination);
}
}
}
}
I apologize for the long question, it might be fit for a blog post, but I do want the community's opinion here.
对于这么长的问题，我深表歉意，它可能适合写一篇博文，但我确实需要社区的意见。
Thanks,
Asaf
谢谢，
阿萨夫
回答by strager
Here's a relatively simple/efficient nCr program I wrote a while ago in C:
这是我不久前用 C 编写的一个相对简单/高效的 nCr 程序：
main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++<k;r*=(1+n-t)/t);printf("%.0f\n",r);}
Okay ... readable version. =] (Not sure if this is 1:1 corresponding with the above.)
好的...可读版本。=] （不确定这是否与上述1：1对应。）
void nCr(int n, int k) {
float curK = 0, r = 1;
while(curK < k) {
++curK;
printf("%.0f\n", r);
r *= (1 + n - curK) / curK;
}
}
Instead of printing, you could yieldor whatever (I don't know C#) into your list.
除了打印之外，您还可以将yield其他任何内容（我不懂 C#）添加到您的列表中。
回答by Die in Sente
Asaf,
阿萨夫，
You are asking us to evaluate your algorithm, but you don't explain your algorithm -- not even in code comments. So you want everyone to spend an hour or more reverse engineering the algorithm from the code, just so we can understand your question before we answer it?
您要求我们评估您的算法，但您没有解释您的算法——甚至在代码注释中也没有。所以你希望每个人都花一个小时或更长时间从代码中对算法进行逆向工程，以便我们在回答之前理解你的问题？
Please edit your question to explain your algorithm.
请编辑您的问题以解释您的算法。
One thing is obvious -- the memory footprint of your code is horrendous. For even modest values of n, the number of combinatations will easily be in the billions, which will require more memory than most computers have. Plus you are using dynamically grown arrays, which keep reallocating and copying themselves as they grow. Plus your program generates subsets in different arrays and merges them. All in all, your program will require many times the amount of memory that would be ideally needed to store the list, and it will spend most of it's time just copying data back and forth.
一件事很明显——你的代码的内存占用是可怕的。即使是适度的 n 值，组合的数量也很容易达到数十亿，这将需要比大多数计算机更多的内存。此外，您正在使用动态增长的数组，它们会随着增长而不断重新分配和复制自身。另外，您的程序会在不同的数组中生成子集并合并它们。总而言之，您的程序需要的内存量是存储列表理想情况下所需的内存量的许多倍，并且大部分时间只是来回复制数据。
If you musthave all the values in an array at once, at least start off by computing the size of the array you need -- n! / (n-k)! / k! -- and then just filling it in.
如果您必须一次拥有一个数组中的所有值，至少首先要计算您需要的数组的大小——n！/ (nk)！/k！- 然后只是填写它。
Even better would be code that "lazily" just computed each member of the sequence as it was needed. See this question from the related questions sidebar
回答by Die in Sente
In C++ given the following routine:
在 C++ 中给出以下例程：
template <typename Iterator>
inline bool next_combination(const Iterator first, Iterator k, const Iterator last)
{
/* Credits: Thomas Draper */
if ((first == last) || (first == k) || (last == k))
return false;
Iterator itr1 = first;
Iterator itr2 = last;
++itr1;
if (last == itr1)
return false;
itr1 = last;
--itr1;
itr1 = k;
--itr2;
while (first != itr1)
{
if (*--itr1 < *itr2)
{
Iterator j = k;
while (!(*itr1 < *j)) ++j;
std::iter_swap(itr1,j);
++itr1;
++j;
itr2 = k;
std::rotate(itr1,j,last);
while (last != j)
{
++j;
++itr2;
}
std::rotate(k,itr2,last);
return true;
}
}
std::rotate(first,k,last);
return false;
}
You can then proceed to do the following:
然后，您可以继续执行以下操作：
std::string s = "123456789";
std::size_t k = 3;
do
{
std::cout << std::string(s.begin(),s.begin() + k) << std::endl;
}
while(next_combination(s.begin(),s.begin() + k,s.end()));
回答by Ohad Schneider
This guy seems to have done serious work in combinatorics using C# (CodeProject) :
这家伙似乎在使用 C# (CodeProject) 的组合学方面做了认真的工作：
Permutations, Combinations, and Variations using C# Generics
