組合せのアリゴリズム

質問

例えば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 · ベストアンサー

(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次元配列を用意して、この二つの配列で総組み合わせを求められないかと考えていました。つまり各位の値をリテラル文字列のようにまとめるのではなく、各値をそれぞれ一つのデータとして扱って組み合わせたいと思っています。私の説明が不足していて申し訳ございませんでした。文章がうまくまとめられておらず分かりずらいと思いますが、もしよろしければアドバイスをお願いいたします。

回答No.5

JaritenCat

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配列を再起関数のローカル変数として扱わないようにする点にはじめ気づかず、格闘していましたが無事動作することができました。
また機会があればアドバイスのほうよろしくお願いいたします。
最後にお礼が遅くなってすみませんでした。
どうもありがとうございました。

回答No.4

BLUEPIXY

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

お礼

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

回答No.3

BLUEPIXY

#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

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

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

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

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

以上

お礼

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