指定の条件での0と1の組み合わせの作成

質問

0と1の組み合わせを指定の条件で作成するのにつまづいています。
(visual studio 2008 express C++)

n桁の0と1の組み合わせを、
(A)1の数が少ないほうから大きいほうへ
(B)1の位置が左から右へ
(C)指定した数の組み合わせを作る
というルールで作成するプログラムを作っています。

n=4桁で10の組み合わせをつくるとすると
0000　　(1)
1000 (2)
0100 (3)
0010 (4)
0001 5)
1100 (6)
1010 (7)
1001 (8)
0110 (9)
0101 (10)

という組み合わせをベクターのベクター　もしくはstringのベクターという形でつくりたいのですがどうやればいいのかわからないでいます。

for ( int i = 0 ; i < 5; ++i){ }
ループで　0 / 1　の　網羅的な組み合わせを作りはしましたが、そうすると　（A） (B)の条件が満たせなくなってしまいます。
STL の　next_permutation()　はざっと見た限りでは今回のような条件を指定した組み合わせというのはできない（？）ようです。
解決法が分かる方がいらっしゃればなにか教えていただけたらありがたいです（できればコードも一緒に。。。）
よろしくお願いします。

回答No.2

akayoroshi · ベストアンサー

プログラムを作ってみました。
// Programmed by Akayoroshi on 2013-05-04.
#include <iostream>
#include <string>
using std::string;
void show( string bp, int c ) {
std::cout << bp << "(" << c << ")" << "\n";

}
void gen( string bp, int n, int count, int &c, int m, int k ) {
// n は show() に渡すためのパラメーター
// count は生成したいパターンの数、c はカウンター
// m と k は再帰を制御するためのパラメーター
if ( c>=count ) return;
if ( k==0 ) {
c++;
show( bp, c );
}
else {
for ( int i=n-m; i<=n-k; i++ ) {
bp[i]='1';
gen( bp, n, count, c, n-i-1, k-1 );
bp[i]='0';
}
}
}
void patterns( int n, int count ) {
string bp( n,'0' ); // 長さ n すべて '0' の文字列
int c=0;
for ( int k=0; k<=n; k++ ) gen( bp, n, count, c, n, k );
}
int main(void) {
patterns( 6, 30 );
}
できあがったパターンを vedtor<string> の要素に追加するよう、関数showを作り変えれば実用に耐えるでしょう。

お礼

丁寧な解説付きのコードありがとうございました！こちらでもコンパイルして希望の通りに動くのを確認できました。正直再帰の制御が全く不慣れで完全にコードを理解したとは言えないのですが実用としてはまさにそのまま使えます！
C++は独学でやってるのですが再帰制御などは難しそうで敬遠してましたが、これを気に勉強してみようと思います。

本当にありがとうございました。

回答No.1

fresh_homepie

初めから条件(A)(B)(C)のすべてを満たすように生成するのではなく、いったん順序に関係なく全パターンを作ってから、条件(A)(B)を満たすような比較を使ってソートするというのも１つの手だと思います。

まあ、nの値を大きくしたときのパフォーマンスの問題もありそうですが、nがそんなに大きくないなら問題ないのでは。そもそも全パターンをvectorに格納しようとしてる時点でnが大きいとメモリが足りなくなりそうですし。

お礼

アドバイスありがとうございます。いったん網羅的に作って後からソートするというのもありですね。ソートの仕方がややトリッキーにはなりそうですが、検討してみる価値はありそうです。