使用 C++ 的排列和/组合

Question

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

这不是任何人的家庭作业，我的一个关键项目需要它，想知道 boost 或其他任何可用的预定义算法。

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

// 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 到列表的大小。

我自己的算法适用于特定的可变长度和特定的大小，当它们都发生变化时，我需要编写大量代码。所以，寻找一个通用的。

我什至不确定这是否称为排列，或者这种 math/logic 有不同的名称。

提前致谢。马斯克的

Answer 1

形式上，您想生成集合 [0;n-1] 的所有 m-combinations。

#include <iostream>
#include <vector>

bool first_combination (std::vector<int> &v, int m, int n)
{
    if ((m < 0) || (m > n)) {
        return false;
    }

    v.clear ();
    v.resize (m);
    for (int i = 0; i < m; i++) {
        v[i] = i;
    }

    return true;
}

bool next_combination (std::vector<int> &v, int m, int n)
{
    for (int i = m - 1; i >= 0; i--) {
        if (v[i] + m - i < n) {
            v[i]++;
            for (int j = i + 1; j < m; j++) {
                v[j] = v[j - 1] + 1;
            }
            return true;
        }
    }

    return false;
}

void print_combination (const std::vector<int> &v)
{
    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v[i] << ' ';
    }
    std::cout << '\n';
}

int main ()
{
    const int m = 3;
    const int n = 5;

    std::vector<int> v;

    if (first_combination (v, m, n)) {
        do {
            print_combination (v);
        } while (next_combination (v, m, n));
    }
}

您可以使用此代码和链接的文章作为灵感。

Answer 2

这个任务可以用一个简单的迭代算法来完成。只需递增第一个可以递增的元素并重新缩放它之前的元素，直到没有要递增的元素。

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

输出：

使用 C++ 的排列和/组合

Permutations &/ Combinations using c++

c++

algorithm

math

combinations

permutation