http://q.hatena.ne.jp/1189233802

配列にカードが入っていて、それを入れ替える方法で作ってみました。

#include <stdio.h>
#include <memory.h>

void main();
void shuffle(int*, int);
void proc(const int*);

#define COUNT 10 // カードの枚数

void main()
{
    int i;
    int c[COUNT];

    /* カード初期化（１～の連番）*/
    for(i = 0; i < COUNT; i++) {
        c[i] = i + 1;
    }

    /* 実行 */
    shuffle(c, 0);
}

/* カード入替処理 */
void shuffle(int* c, int v)
{
    int i, w;

    /* レベルが最深なら復帰 */
    if(v+1 == COUNT) {
        proc(c); // カード出力処理
        return ;
    }
    
    /* 入替無しで再帰 */
    shuffle(c, v+1); 

    /* カードを一箇所入れ替えて再帰 */
    w = c[v];
    for(i = v+1; i < COUNT; i++) {
        c[v] = c[i]; c[i] = w; // 入れ替える
        shuffle(c, v+1);
        c[i] = c[v]; c[v] = w; // 元にもどす
    }
}

/* カード出力処理 */
void proc(const int* c)
{
    static int n = 1; // 行番号
    int i;

    printf("%10d:\t", n++);
    for(i = 0; i < COUNT; i++) {
        printf("%d", c[i]);
        printf("%c",(i+1)!=COUNT?'\t':'\n');    
    }
}

カード１０枚の処理をテキストに出力（3628800行）

ファイルサイズ：120MB

処理時間：30秒

----

簡単にロジックを書いておきます。

下記はカードが4枚の場合

レベル０：一桁目（各パターンに対してレベル１を実行）

(0):1,2,3,4（入替なし）

(1):2,1,3,4（１と２を入替）

(2):3,2,1,4（１と３を入替）

(3):4,2,3,1（１と４を入替）

レベル１：二桁目（各パターンに対してレベル２を実行）

(0-0):1,2,3,4（入替なし）

(0-1):1,3,2,4（２と３を入替）

(0-2):1,4,3,2（２と４を入替）

レベル２：三桁目（各パターンに対してレベル３を実行）

(0-0-0):1,2,3,4（入替なし）

(0-0-1):1,2,4,3（３と４を入替）

レベル３：四桁目（各パターンに対して出力処理）

(0-0-0-0):1,2,3,4（入替なし）

再帰呼び出しで作ってみました。

私も再帰なら樹形図だろ～と思いました。

（以下で約10秒でした。）

	
#include <stdio.h>

void main();
void calc(int cards, int fixedSize, char used);
void check(int cards[]);


#define size 10

/* メイン */
void main() {
	int cards[size];  // 数値の入れ物
	char used[size];  // 数値が使用済みかどうか
	int i;
	/* 初期化 */
	for(i = 0; i < size; i++) {
		cards[i] = -1;  // 別に3や8などでもよい(fixedSizeがあるから)
		used[i] = 0;    // 未使用(0)にセット
	}
	calc(cards, 0, used);
}

/* 再帰関数 */
void calc(int cards, int fixedSize, char used) {
	int i;
	if(fixedSize < size) {
		for(i = 0; i < size; i++) {    // 0から9までで
			if(used[i] == 0) {         // その数字が未使用なら
				used[i] = 1;           // 使用済みにして
				cards[fixedSize] = i;  // その数字を代入して
				calc(cards, (fixedSize + 1), used);  // 次の桁について再帰
				used[i] = 0;           // 終わったらその数字を未使用に戻す
			}
		}
	} else {
		check(cards);  // 全桁確定してたらチェック
	}
}

/* チェック */
void check(int cards[]) {
	static int n = 1;  // 行番号
	int i;
	printf("%d\t", n++);
	for(i = 0; i < size; i++) {
		printf("%d", cards[i]);
	}
	printf("\n");
}

	

【考え方】

(1)長さ10の配列cardsを用意し、ここには数字を重複しないように入れます。

添字0から9まで全てに有効な数字が入ったら、それが並び替えパターンの１つを表します。

(2)再帰関数は、(1)の配列cardsのうち、f個（つまり添字(f-1)まで）に有効な数字が入っている状態で呼ばれたなら、それ以前（添字0から(f-1)）と重複しない数字についてループ（=樹形図の分岐）します。

その配列cardsの(f+1)番目（添字f）に対してループさせた数字を代入し、再帰呼び出しします。

例えば、配列cardsが[5,2,3,0,1,7,4,未確定,未確定,未確定]の状態で再帰関数を実行したならば、6,8,9について３回ループし、１周目では[5,2,3,0,1,7,4,6,未確定,未確定]、２周目では[5,2,3,0,1,7,4,8,未確定,未確定]、３周目では[5,2,3,0,1,7,4,9,未確定,未確定]として再帰します。

(3)(2)でいう重複しない数字を見つけるために、配列の確定している部分について毎回ループするのはコスト増なので、「この数字は使われているかどうか」配列usedを別に用意します。

例えば(2)の配列cardsが[5,2,3,0,1,7,4,未確定,未確定,未確定]のとき、usedは[1,1,1,1,1,1,0,1,0,0]となっています。

なので、樹形図の分岐をするためには、usedについてループをしつつ、未使用である数字のときに再帰すればよいことになります。

【イメージ】

樹形図は、根元は10分岐，次は9分岐，8分岐・・・最後は1分岐のイメージです。

(途中から)
└[6,9,1,0,3]
　├[6,9,1,0,3,2]
　│├[6,9,1,0,3,2,4]
　││├[6,9,1,0,3,2,4,5]
　│││├[6,9,1,0,3,2,4,5,7]
　││││└[6,9,1,0,3,2,4,5,7,8]
　│││└[6,9,1,0,3,2,4,5,8]
　│││　└[6,9,1,0,3,2,4,5,8,7]
　││├[6,9,1,0,3,2,4,7]
　│││└（以下省略）
　││└[6,9,1,0,3,2,4,8]
　││　└（以下省略）
　│├[6,9,1,0,3,2,5]　　↓ここから下も省略
　│├[6,9,1,0,3,2,7]
　│└[6,9,1,0,3,2,8]
　├[6,9,1,0,3,4]
　├[6,9,1,0,3,5]
　├[6,9,1,0,3,7]
　└[6,9,1,0,3,8]

【感想】

もともとはJAVAで書き、Ｃで作り直すのに苦労しました。

Ｃは初心者レベルなので書き方・定義の仕方・使い方などがおかしい部分があるかも知れません。