n个中的k个元素的所有组合

本文介绍了n个中的k个元素的所有组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

有人可以为我提供一个函数的链接或伪代码，以找到n个元素中的所有k个元素的组合？可能在STL。我不需要计算n选择k，我需要列出大小k的所有数字向量。

Can somebody provide me a link or pseudocode of a function for finding all combinations of k elements out of n? possibly in STL. I don't need to compute n choose k, I need to list all vectors of numbers of size k.

感谢

推荐答案

在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:

// 9-choose-3 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()));

或者对于int的std :: vector：

Or for a std::vector of int's:

// 5-choose-3 std::size_t n = 5; std::size_t k = 3; std::vector<int> ints; for (int i = 0; i < n; ints.push_back(i++)); do { for (int i = 0; i < k; ++i) { std::cout << ints[i]; } std::cout << "\n"; } while(next_combination(ints.begin(),ints.begin() + k,ints.end()));