使用c ++的排列和/或组合

musk's 发表于 Dev

麝香

我的代码需要其他版本的排列。我可以实现我想要的功能，但是它不够通用。我的算法随着我的要求不断扩大。但这不应该。

对于任何人来说，这都不是一项家庭工作，对于我的关键项目，我需要它，想知道是否可以从boost或任何其他工具获得任何预定义的算法。

以下是使用c ++的next_permutation的标准版本。

// next_permutation example
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation

int main () 
{
  int myints[] = {1,2,3};
  do 
  {
    std::cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n';
  } while ( std::next_permutation(myints,myints+3) );


  return 0;
}

给出以下输出：

但我的要求是：-假设我有1到9个数字：1、2、3、4、5、6、7、8、9

我需要可变长度的排列，并且仅按升序排列，并且没有重复。

假设我需要3位数的排列长度，然后需要如下输出。

123
124
125
.
.
.
128
129
134   // After 129 next one should be exactly 134
135      // ascending order mandatory
136
.
.
.
148
149
156   // exactly 156 after 149, ascending order mandatory
.
.
.
489   // exactly 567 after 489, because after 3rd digit 9, 2nd digit
567   // will be increased to 49? , so there is no possibility for
.     // 3rd digit, so first digit gets incremented to 5 then 6 then
.     // 7, in ascending order.
.     
.
.
789   // and this should be the last set I need.

我的列表最多可以包含数百个数字，并且可变长度可以是1到最大列表的大小。

我自己的算法适用于特定的可变长度和特定的大小，当它们都改变时，我需要编写大量代码。因此，寻找一种通用的。

我什至不知道这是否称为置换（Permutations）或这种数学/逻辑有不同的名称。

提前致谢。麝香

赛义德

可以使用简单的迭代算法完成此任务。只需增加第一个可以增加的元素，然后在其之前重新缩放元素，直到没有要增加的元素。

int a[] = {0,1,2,3,4,5,6,7,8,9}; // elements: must be ascending in this case
int n = sizeof(a)/sizeof(int);
int digits = 7; // number of elements you want to choose
vector<int> indexes; // creating the first combination
for ( int i=digits-1;i>=0;--i ){
    indexes.push_back(i);
}

while (1){
    /// printing the current combination
    for ( int i=indexes.size()-1;i>=0;--i ){
        cout << a[indexes[i]] ;
    } cout << endl;
    ///
    int i = 0;
    while ( i < indexes.size() && indexes[i] == n-1-i ) // finding the first element
        ++i;                                            // that can be incremented
    if ( i==indexes.size() ) // if no element can be incremented, we are done
        break;
    indexes[i]++; // increment the first element
    for ( int j=0;j<i;++j ){ // rescale elements before it to first combination
        indexes[j] = indexes[i]+(i-j);
    }
}

输出：