組合せのアリゴリズム

例えば1,2,3を一列に並べるという順列の問題(1→2→3、1→3→2、2→1→3、2→3→1、3→1→2、3→2→1の3!=6通り)
は再帰などを使って解けますが、

千の位(3,2)、百の位(1,4,7)、十の位(6)、一の位(2,6)
のような各位の組合せの問題を解くにはどうすればよいでしょうか？
3→1→6→2、3→1→6→6、3→4→6→2、3→4→6→6、3→7→6→2、3→7→6→6、2→1→6→2、2→1→6→6、2→4→6→2、2→4→6→6、2→7→6→2、2→7→6→6

上記の例の総組合せの数は2×3×1×2=12(各位の掛算)になりますが、アドバイスをお願いします。
開発言語はGNU Cで、コンパイラはgccです。

No.2 ベストアンサー 回答者： BLUEPIXY 回答日時： 2004/10/12 20:05

(1)1,2,3を一列に並べる

/* "123"の順列を表示する */
#include <stdio.h>
#include <string.h>
#include <malloc.h>

static unsigned count;

void choice(char *select,char *list){
int len,i,j;
char *newSelect,*newList,*p;

len=strlen(list);
if(len==1){
printf("%s%c\n",select, *list);
count++;
return;
}
newSelect=(char*)malloc(strlen(select)+2);
newList =(char*)malloc(len);
for(i=0;i<len;i++){
for(j=0,p=newList;j<=len;j++){ /* 選んだ１文字を除く文字列を作る */
if(j!=i)
*p++=list[j];
}
sprintf(newSelect,"%s%c", select, list[i]);
choice(newSelect, newList);
}
free(newSelect);
free(newList);
}

void main(void){
count=0;
choice("","123");
printf("%u通り\n",count);
}
(2)千の位(3,2)、百の位(1,4,7)、十の位(6)、一の位(2,6)
/* [32][147][6][26]の順列を表示する */
#include <stdio.h>
#include <string.h>
#include <malloc.h>

static unsigned count;
char *table[]={ "32","147","6","26",NULL};

void choice(char *select, int level){
char *newSelect,*p;

if(table[level]==NULL){
count++;
printf("%s\n",select);
return;
}
newSelect=(char*)malloc(strlen(select)+2);
p=table[level];
while(*p){
sprintf(newSelect, "%s%c", select, *p++);
choice(newSelect, level+1);
}
free(newSelect);
}

void main(void){
count=0;
choice("",0);
printf("%u通り\n",count);
}

この回答への補足

お返事ありがとうございます。
とても詳しくソースコードまで書いていただいて申し訳ないのですが、千の位の候補の3,2を"32"というリテラル文字列で扱うのではなく、int comb[][]={{3,1,6,2},{2,4,,6},{,7,,}}という2次元配列のようなもので扱いたいと思っています。そして各位にどれだけ値が入っているかを記憶しておくint check[]={2,3,1,2}という1次元配列を用意して、この二つの配列で総組み合わせを求められないかと考えていました。つまり各位の値をリテラル文字列のようにまとめるのではなく、各値をそれぞれ一つのデータとして扱って組み合わせたいと思っています。私の説明が不足していて申し訳ございませんでした。文章がうまくまとめられておらず分かりずらいと思いますが、もしよろしければアドバイスをお願いいたします。

補足日時：2004/10/13 02:10

No.5 回答者： JaritenCat 回答日時： 2004/10/13 06:05

No.1のコーディング例です。

再帰を使っています。
(インデントを全角の空白にしています)
#include <stdio.h>

#define N 4

int comb[][N]={{3,2,0},{1,4,7},{6,0,0},{2,6,0}};
int check[N]={2,3,1,2};
int kotae[N];

void hyouji(void) {
　int i;
　for (i=0; i<N; i++) {
　　printf("%d ",kotae[i]);
　}
　printf("\n");
}

void naraberu(int n) {
　int i;
　if (n==N) {
　　hyouji();
　} else {
　　for (i=0; i<check[n]; i++) {
　　　kotae[n] = comb[n][i];
　　　naraberu(n+1);
　　}
　}
}

int main(void) {
　naraberu(0);
　return 0;
}

この回答へのお礼

諸事情により回答が遅くなってしまい大変申し訳ございませんでした。
アドバイスいただいたサンプルプログラムは大変わかりやすく、参考になりました。
combやcheck配列を再起関数のローカル変数として扱わないようにする点にはじめ気づかず、格闘していましたが無事動作することができました。
また機会があればアドバイスのほうよろしくお願いいたします。
最後にお礼が遅くなってすみませんでした。
どうもありがとうございました。

お礼日時：2004/11/04 20:07

No.4 回答者： BLUEPIXY 回答日時： 2004/10/13 03:15

#3の補足

combの内容（並び）が#2の補足で示されているものと異なりますが、
配列の下位のモノが並列に変化する
（comb[][i]のようなこと）
方が私にとってなじみがよく好みですのでそう書いております。
もちろん
comb[i][]のようにアクセスしてもかまいません。
同じことです。
老婆心にて。

この回答へのお礼

諸事情によりお返事が遅くなってしまい大変申し訳ございませんでした。
BLUEPIXYさんのサンプルプログラムを参考にcomb[i][]のようにアクセスして試してみたところ動作することが確認できました。
今回は何度もご丁寧な回答をしていただいてとても感謝しています。
また機会があればアドバイスのほうよろしくお願いいたします。最後にお返事が遅くなって本当にすみませんでした。どうもありがとうございました。

お礼日時：2004/11/04 20:04

No.3 回答者： BLUEPIXY 回答日時： 2004/10/13 02:54

#2の補足について

int comb[4][4]={
{3,2,0,0},
{1,4,7,0},
{6,0,0,0},
{2,6,0,0}
};
int check [4]={ 2,3,1,2 };
は、＃２（２）のプログラムを
char table[4][4] = {
{'3','2' ,'\0','\0'},
{'1','4' ,'7' ,'\0'},
{'6','\0','\0','\0'},
{'2','6' ,'\0','\0'}
};
と見なすと
int check [4]={ 2,3,1,2 };
は、あらかじめstrlenしたと見ると
ほとんど同じだということがわかります。
組み合わせる数を
int select[4];
の様に表現するか
あるいは、
int select=0;
として、
select = select * 10 + n;
のように集計するかは、お好みでやればいいかと思います。

No.1 回答者： elmclose 回答日時： 2004/10/12 15:38

一例ですが、下記の手順を実行する関数を作成すれば良いのではないでしょうか。

step 1）
さらに下位があればstep 2 ～ 3を実行し、なければ空列を値として返す。

step 2）
下位の順列を得る（再帰呼び出しでも可能）。

step 3）
現在位置の数（例えば、百の位ならば、１，４，７）それぞれに、上で得た下位の順列それぞれを連結させ、これで得られる全ての列を値として返す。

以上

この回答へのお礼

お返事ありがとうございます。
なかなかプログラムのスキルやアルゴリズムの知識がないため、アドバイスがあまり理解ができなかったのですが、頑張ってみたいと思います。

お礼日時：2004/10/13 02:10