私は C++ を使用して組み合わせを生成するソース コードを探していました。このための高度なコードをいくつか見つけましたが、それは特定の数値の定義済みデータにしか適していません。組み合わせを生成するためのヒントやアイデアを教えていただけませんか?
例として、セットS = { 1, 2, 3, ...., n}
とを考えて、そこから を取り出しますr= 2
。入力はn
と になりますr
。この場合、プログラムは長さ 2 の配列を生成します。したがって、 の入力は5 2
を出力します1 2, 1 3
。
アルゴリズムの構築に苦労しました。これについて考えるのに1か月かかりました。
ベストアンサー1
簡単な方法std::next_permutation
:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
int n, r;
std::cin >> n;
std::cin >> r;
std::vector<bool> v(n);
std::fill(v.end() - r, v.end(), true);
do {
for (int i = 0; i < n; ++i) {
if (v[i]) {
std::cout << (i + 1) << " ";
}
}
std::cout << "\n";
} while (std::next_permutation(v.begin(), v.end()));
return 0;
}
または、結果をよりわかりやすい順序で出力するわずかなバリエーション:
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
int n, r;
std::cin >> n;
std::cin >> r;
std::vector<bool> v(n);
std::fill(v.begin(), v.begin() + r, true);
do {
for (int i = 0; i < n; ++i) {
if (v[i]) {
std::cout << (i + 1) << " ";
}
}
std::cout << "\n";
} while (std::prev_permutation(v.begin(), v.end()));
return 0;
}
少し説明します:
v
これは、セレクタを配置する「選択配列」( )を作成しr
、これらのセレクタのすべての順列を作成し、 の現在の順列で で選択されている場合は、対応するセット メンバーを出力しますv
。