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

Question

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

这不是任何人的家庭作业，我的一个关键项目需要它，想知道 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 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

但我的要求是:- 假设我有 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 到列表的大小。

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

我什至不确定这是否称为排列，或者这种数学/逻辑是否有不同的名称。

提前致谢。麝香的

Answer 1

正式地，你想要生成所有m-combinations集合[0;n-1]。

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

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