题描述:有n个不同的数,现在要从中选取m个,需要按升序输出所有排列,比如从0到9中选出2个的所有无重复组合为
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
1 2
1 3
1 4
1 5
...
7 8
7 9
8 9
一共45个,
c++代码为
#include<cassert>
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
struct Combination {const int m; //解的位数vector<int> answer; //目前的答案,是一个长度为m的升序序列const int max_value; //可能的最大值Combination(const vector<int>& values, int m) : m(m), answer(m),max_value(values.back()){//把s中的前m个元素复制到answer中,作为初始解for (int i = 0; i < m; ++i) {int x = values[i];answer[i] = values[i];}}void print()const {for (auto e : answer)cout << e << " ";cout << endl;}//把第index的值+1,右边各位等于左边的+1void inc(int index) { int x = answer[index];for (int i = index; i < m; ++i)answer[i] = ++x;assert(answer.back() <= max_value);}bool next() //输出下一个组合,如果已经到头,则返回false{/*从右边开始找到第一个可以加1的位,即本位+1之后,这个值到最大值的距离>=右边的位数*/for (int i = m - 1,j=0; i >= 0; --i,++j) {int x = answer[i];if (max_value - x > j) //本位+1之后,右边的j位仍然有可能组成一个升序序列{/*新的子序列为x+1,x+2,x+(j+1)<=max*///从本位开始构造一个连续的升序子序列inc(i);return true;}}return false;}
};int main() {vector<int> values(10);for (int i = 0; i < 10; ++i)values[i] = i;Combination c1(values, 2);do {c1.print();} while (c1.next());return 0;
}