列出ķ整数的所有可能的组合，1间... N（N选K）

本文介绍了列出ķ整数的所有可能的组合，1间... N（N选K）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

出于没有特别的原因，我决定去寻找产生1第K整数的所有可能的选择算法... n，其中之中k个整数的顺序并不重要（第n选择k啄）。

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).

这是完全一样的道理，这是毫无道理可言，我也是用C＃实现了它。我的问题是：

From the exact same reason, which is no reason at all, I also implemented it in C#. My question is:

你能看到我的算法或code任何错误？而且，更重要的是，您能否提供一个更好的算法？的

Do you see any mistake in my algorithm or code? And, more importantly, can you suggest a better algorithm?

请更注重算法比C本身$ C $。这不是prettiest code我曾经写过，虽然看告诉你，如果看到一个错误。

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.

编辑： Alogirthm解释 -

Alogirthm explained -

• 我们举行ķ指数。
• 创建ķ嵌套的在的循环，在循环我的指数是指数[1]。
• 在它模拟氏EM>的的回路，其中指数[I + 1]属于嵌套指数的环[I]内循环。
• 在指数[I]往返指数[我 - 1] + 1到n - K + I + 1

• We hold k indices.
• This creates k nested for loops, where loop i's index is indices[i].
• It simulates k for loops 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.

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

推荐答案

在C ++中给出了下面的程序：

In C++ given the following routine:

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()));