k个元素的全部组合n

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

感谢

2011-02-23 Bob

“我不需要计算n选择k，我需要列出大小为k的数字的所有向量。”意思？无论如何，编写'next_combination'函数[直接]（http://stackoverflow.com/questions/2211915/combination-and-permutation-in-c/2616837#2616837）。 – 2011-02-23 18:36:49

你有没有试图自己做到这一点呢？听起来像你要求我们做你的功课。 – prolink007 2011-02-23 18:37:07

我建议把它移到http://programmers.stackexchange.com/ – 2011-02-23 18:39:44

在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; 
}

然后您可以继续执行以下操作：

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

还是诚信部的一个std ::向量：

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

来源

2011-02-23 21:05:59

你能提供一些关于你的代码如何工作的直觉吗？我试图遵循逻辑，但我确实没有任何理由相信它的工作原理。 – templatetypedef 2011-02-23 21:20:04

@templatetypedef：如果您在第一个示例中打印出整个字符串，则可能会看到该算法的运行方式。该字符串随时包含两个排序的半部分。 – UncleBens 2011-02-24 11:03:19

可能值得注意的是，当k等于零时，do ... while是不正确的，因为当时不应该生成组合。 – 2013-05-14 19:27:23

你可以使用std::next_permutation，但它为n！而不是选择k。您可以在创建它们后对其进行过滤。但是这个解决方案是O（n！），并不是很完美。这里是试错的解决方案：

int factorial(int value) 
{ 
    int result = 1; 

    for(int i = 1; i <= value; i++) 
    { 
     result *= i; 
    } 

    return result; 
} 

std::set<std::set<int>> binomial_coefficient(std::vector<int> input, int k) 
{ 
    std::set<std::set<int>> solutions; 

    for(unsigned int i = 0; i < factorial(input.size()); i++) 
    { 
     std::next_permutation(input.begin(), input.end()); 

     solutions.insert(std::set<int>(input.begin(), input.begin() + k)); 
    } 

    return solutions; 
}

来源

2011-02-23 18:36:52 Fox32

将算法降低一个因子“n！”比“不完美”更糟。对于任何合理的“n”值，这意味着它不会在宇宙死亡之前结束。尽管在这种情况下，“factorial”函数将会简单地溢出“int”的范围并产生垃圾。 – 2011-02-23 23:39:45

这里是伪代码可以完成这项工作的懒惰例子...

void nChooseK(array[n],k){ 
    recurse("",array[n],k);  
} 

void recurse(initialString,array[n],k){ 
    if(k == 0){ 
     print initialString; 
     return; 
    } 
    for(i=0;i<n;i++){ 
     tmpArray = array[0...i-1]+array[i+1...];//the array without the object to remove 
     recurse(initialString + array[i], tmpArray,k-1) 
    }   
}

来源

2011-02-23 20:02:34 nosirrahcd

从技术上讲，您正在生成每个子集k！倍。如果'tmpArray'创建为'array [i + 1，...]'，那么您只能生成一次可能的集合。 – Pablo 2011-02-23 21:09:19

好主意巴勃罗，那是真的。 – nosirrahcd 2011-02-23 21:21:54

创建具有n个辅助载体 - K零后面跟着K的。零表示不包含原始容器中的元素，而表示包含该元素。

现在在辅助矢量上使用std :: next_permutation来获得下一个组合。

来源

2011-02-23 22:37:26 user515430