1からまで番号が付けられた n 人がいnます。kこれらから人々のすべての異なる組み合わせを生成して出力するコードを書かなければなりませんn。そのために使用されるアルゴリズムを説明してください。
176480 次
13 に答える
76
組み合わせの意味での組み合わせについて質問していると思います（つまり、要素の順序は関係ないので[1 2 3]、 と同じ[2 1 3]です）。誘導/再帰を理解していれば、アイデアは非常に単純です。すべてKの要素の組み合わせを取得するには、最初に既存の人々のセットから組み合わせの最初の要素を選択し、次にこの最初の要素を可能なすべての組み合わせで「連結」しますK-1初期要素を引き継ぐ要素から生み出された人々。
例として、5 人のセットから 3 人のすべての組み合わせを取得したいとします。次に、3 人のすべての可能な組み合わせは、2 人の可能なすべての組み合わせで表現できます。
comb({ 1 2 3 4 5 }, 3) =
{ 1, comb({ 2 3 4 5 }, 2) } and
{ 2, comb({ 3 4 5 }, 2) } and
{ 3, comb({ 4 5 }, 2) }
このアイデアを実装する C++ コードを次に示します。
#include <iostream>
#include <vector>
using namespace std;
vector<int> people;
vector<int> combination;
void pretty_print(const vector<int>& v) {
static int count = 0;
cout << "combination no " << (++count) << ": [ ";
for (int i = 0; i < v.size(); ++i) { cout << v[i] << " "; }
cout << "] " << endl;
}
void go(int offset, int k) {
if (k == 0) {
pretty_print(combination);
return;
}
for (int i = offset; i <= people.size() - k; ++i) {
combination.push_back(people[i]);
go(i+1, k-1);
combination.pop_back();
}
}
int main() {
int n = 5, k = 3;
for (int i = 0; i < n; ++i) { people.push_back(i+1); }
go(0, k);
return 0;
}
そして、ここに出力がありN = 5, K = 3ます：
combination no 1: [ 1 2 3 ]
combination no 2: [ 1 2 4 ]
combination no 3: [ 1 2 5 ]
combination no 4: [ 1 3 4 ]
combination no 5: [ 1 3 5 ]
combination no 6: [ 1 4 5 ]
combination no 7: [ 2 3 4 ]
combination no 8: [ 2 3 5 ]
combination no 9: [ 2 4 5 ]
combination no 10: [ 3 4 5 ]
于 2012-10-20T20:45:35.967 に答える
67
#include <algorithm>
#include <iostream>
#include <string>
void comb(int N, int K)
{
std::string bitmask(K, 1); // K leading 1's
bitmask.resize(N, 0); // N-K trailing 0's
// print integers and permute bitmask
do {
for (int i = 0; i < N; ++i) // [0..N-1] integers
{
if (bitmask[i]) std::cout << " " << i;
}
std::cout << std::endl;
} while (std::prev_permutation(bitmask.begin(), bitmask.end()));
}
int main()
{
comb(5, 3);
}
出力
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
分析とアイデア
全体のポイントは、数値のバイナリ表現で遊ぶことです。たとえば、バイナリの7は0111です
したがって、このバイナリ表現は、割り当てリストそのものとしても見ることができます。
各ビットiについて、ビットが設定されている (つまり1である) 場合、i番目の項目が割り当てられていることを意味します。
次に、連続する 2 進数のリストを単純に計算し、2 進数表現 (非常に高速な場合があります) を利用することで、 kを超えるNのすべての組み合わせを計算するアルゴリズムが得られます。
(一部の実装では) 最後の並べ替えは必要ありません。これは、決定論的に結果を正規化する方法にすぎません。つまり、同じ数 (N、K) と同じアルゴリズムに対して、同じ順序の組み合わせが返されます。
数値表現と、それらの組み合わせ、順列、ベキ集合 (およびその他の興味深いもの) との関係についてさらに読むには、Combinatorial number system、Factorial number systemをご覧ください。
PS:多くの種類の組み合わせオブジェクトを効率的に計算し、そのルーチン (元は JavaScript) を他の多くの言語に簡単に適用できる私の組み合わせフレームワーク Abacusをチェックしてみてください。
于 2015-02-24T14:41:13.417 に答える
7
Python では、これは itertools.combinations として実装されます。
https://docs.python.org/2/library/itertools.html#itertools.combinations
C++ では、このような組み合わせ関数は順列関数に基づいて実装できます。
基本的な考え方は、サイズ n のベクトルを使用し、内部で k 個のアイテムのみを 1 に設定すると、各順列で k 個のアイテムを収集することによって nchoosek のすべての組み合わせを取得できます。組み合わせは通常非常に大きな数になるため、大きなスペースを必要とする最も効率的な方法ではないかもしれません。ジェネレーターとして実装するか、作業コードを do_sth() に入れることをお勧めします。
コードサンプル:
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
int main(void) {
int n=5, k=3;
// vector<vector<int> > combinations;
vector<int> selected;
vector<int> selector(n);
fill(selector.begin(), selector.begin() + k, 1);
do {
for (int i = 0; i < n; i++) {
if (selector[i]) {
selected.push_back(i);
}
}
// combinations.push_back(selected);
do_sth(selected);
copy(selected.begin(), selected.end(), ostream_iterator<int>(cout, " "));
cout << endl;
selected.clear();
}
while (prev_permutation(selector.begin(), selector.end()));
return 0;
}
そして出力は
0 1 2
0 1 3
0 1 4
0 2 3
0 2 4
0 3 4
1 2 3
1 2 4
1 3 4
2 3 4
このソリューションは、実際には C++ での組み合わせの生成と重複してい ます
于 2014-05-14T19:22:24.310 に答える
2
これは、この問題を解決するために私が思いついたアルゴリズムです。コードで動作するように変更できるはずです。
void r_nCr(const unsigned int &startNum, const unsigned int &bitVal, const unsigned int &testNum) // Should be called with arguments (2^r)-1, 2^(r-1), 2^(n-1)
{
unsigned int n = (startNum - bitVal) << 1;
n += bitVal ? 1 : 0;
for (unsigned int i = log2(testNum) + 1; i > 0; i--) // Prints combination as a series of 1s and 0s
cout << (n >> (i - 1) & 1);
cout << endl;
if (!(n & testNum) && n != startNum)
r_nCr(n, bitVal, testNum);
if (bitVal && bitVal < testNum)
r_nCr(startNum, bitVal >> 1, testNum);
}
仕組みの説明はこちらでご覧いただけます。
于 2015-02-03T20:02:21.000 に答える
1
于 2012-10-20T19:44:29.927 に答える
0
以下のリンクの後ろには、この問題に対する一般的な C# の回答があります: オブジェクトのリストからすべての組み合わせをフォーマットする方法。結果を非常に簡単に k の長さに制限することができます。
于 2016-11-04T10:27:24.920 に答える
0
訪問した配列を維持することにより、バックトラッキングを使用して実行することもできます。
void foo(vector<vector<int> > &s,vector<int> &data,int go,int k,vector<int> &vis,int tot)
{
vis[go]=1;
data.push_back(go);
if(data.size()==k)
{
s.push_back(data);
vis[go]=0;
data.pop_back();
return;
}
for(int i=go+1;i<=tot;++i)
{
if(!vis[i])
{
foo(s,data,i,k,vis,tot);
}
}
vis[go]=0;
data.pop_back();
}
vector<vector<int> > Solution::combine(int n, int k) {
vector<int> data;
vector<int> vis(n+1,0);
vector<vector<int> > sol;
for(int i=1;i<=n;++i)
{
for(int i=1;i<=n;++i) vis[i]=0;
foo(sol,data,i,k,vis,n);
}
return sol;
}
于 2018-06-11T08:20:11.810 に答える
0
より完全にするために、次の回答は、データセットに重複した値が含まれている場合をカバーしています。この関数は、フォローアップしやすいように std::next_permutation() のスタイルに近い形で記述されています。
template< class RandomIt >
bool next_combination(RandomIt first, RandomIt n_first, RandomIt last)
{
if (first == last || n_first == first || n_first == last)
{
return false;
}
RandomIt it_left = n_first;
--it_left;
RandomIt it_right = n_first;
bool reset = false;
while (true)
{
auto it = std::upper_bound(it_right, last, *it_left);
if (it != last)
{
std::iter_swap(it_left, it);
if (reset)
{
++it_left;
it_right = it;
++it_right;
std::size_t left_len = std::distance(it_left, n_first);
std::size_t right_len = std::distance(it_right, last);
if (left_len < right_len)
{
std::swap_ranges(it_left, n_first, it_right);
std::rotate(it_right, it_right+left_len, last);
}
else
{
std::swap_ranges(it_right, last, it_left);
std::rotate(it_left, it_left+right_len, n_first);
}
}
return true;
}
else
{
reset = true;
if (it_left == first)
{
break;
}
--it_left;
it_right = n_first;
}
}
return false;
}
完全なデータ セットは [first, last) の範囲で表されます。現在の組み合わせは範囲 [first, n_first) で表され、範囲 [n_first, last) は現在の組み合わせの補集合を保持します。
組み合わせはその順序とは無関係であるため、[first, n_first) と [n_first, last) は重複を避けるために昇順のままです。
このアルゴリズムは、A よりも大きい右側の最初の値 B と交換することにより、左側の最後の値 A を増やすことによって機能します。交換後、両側はまだ順序付けられています。右側にそのような値 B が存在しない場合は、左側のすべての値が右側より小さくなくなるまで、左側の最後から 2 番目の値を増やすことを検討し始めます。
次のコードでセットから 2 つの要素を描画する例:
std::vector<int> seq = {1, 1, 2, 2, 3, 4, 5};
do
{
for (int x : seq)
{
std::cout << x << " ";
}
std::cout << "\n";
} while (next_combination(seq.begin(), seq.begin()+2, seq.end()));
与えます：
1 1 2 2 3 4 5
1 2 1 2 3 4 5
1 3 1 2 2 4 5
1 4 1 2 2 3 5
1 5 1 2 2 3 4
2 2 1 1 3 4 5
2 3 1 1 2 4 5
2 4 1 1 2 3 5
2 5 1 1 2 3 4
3 4 1 1 2 2 5
3 5 1 1 2 2 4
4 5 1 1 2 2 3
必要に応じて、結合結果として最初の 2 つの要素を取得するのは簡単です。
于 2020-07-17T12:21:28.823 に答える