列出1 … n之间k个整数的所有可能组合（n选择k）
出于没有特别的原因，我决定寻找一种算法，该算法产生1 … n之间k个整数的所有可能选择，其中k整数之间的顺序无关紧要（n选择k thingy）。
从完全相同的原因，这完全没有理由，我也用C＃实现了它。 我的问题是：
你在我的算法或代码中看到任何错误吗？ 而且，更重要的是， 你能建议一个更好的算法吗？
请注意算法而不是代码本身。 这不是我写过的最漂亮的代码，虽然可以告诉你是否看到了错误。
编辑： Alogirthm解释 –
- 我们持有k指数。
- 这会创建k个嵌套for循环，其中循环i的索引是indices [i]。
- 它模拟k for for循环，其中indices [i + 1]属于嵌套在indices [i]循环中的循环。
- indices [i]从索引[i-1] + 1到n-k + i + 1运行。
码：
public class AllPossibleCombination { int n, k; int[] indices; List combinations = null; public AllPossibleCombination(int n_, int k_) { if (n_ <= 0) { throw new ArgumentException("n_ 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; } /// /// Returns all possible k combination of 0..n-1 /// /// public List GetCombinations() { if (combinations == null) { combinations = new List(); 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); } } } } 我为长期问题道歉，它可能适合博客文章，但我确实想要社区的意见。
谢谢，
阿萨夫
在C ++中给出以下例程：
template 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; }
然后，您可以继续执行以下操作：
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()));
阿萨夫，
您要求我们评估您的算法，但您不解释您的算法 – 即使在代码注释中也是如此。 所以你希望每个人花一个小时或更长时间从代码中反向设计算法，这样我们才能在回答之前理解你的问题？
请编辑您的问题以解释您的算法。
有一件事是显而易见的 – 你的代码的内存占用是可怕的。 对于n的适度值，组合的数量很容易达到数十亿，这将需要比大多数计算机更多的内存。 此外，您正在使用动态增长的arrays，这些arrays随着它们的增长不断重新分配和复制。 此外，您的程序会在不同的数组中生成子集并合并它们。 总而言之，您的程序将需要许多次存储列表所需的内存量，并且它将花费大部分时间来回复制数据。
如果你必须同时拥有一个数组中的所有值，至少从计算所需数组的大小开始 – n！ /（nk）！ / k！ – 然后填写它。
更好的是“懒惰地”只是根据需要计算序列的每个成员的代码。 从相关问题边栏中查看此问题
这家伙似乎已经使用C＃（CodeProject）在组合学方面做了认真的工作：
使用C＃generics的排列，组合和变体
这是我之前在C中写过的一个相对简单/高效的nCr程序：
main(n,k){float t=0,r=1;for(scanf("%d, %d",&n,&k);t++
好的...可读的版本。 =] （不确定这是否与上述相对应的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; } }
而不是打印，你可以yield或任何（我不知道C＃）进入你的列表。