/*
Copyright(C) 2010 Ryuji Matumoto (matumoto@pluto.ai.kyutech.ac.jp)

ライセンス: GNU General Public Licence(GPL)

  (約数の生成に使う)組み合わせの生成。普通の組み合わせじゃないよ。

  例えば36を素因数分解すると、

  36=3^2 * 2^3
    = 3 * 3 * 2 * 2 * 2;

 だから約数は、

    3^0 * 2^0, 3^0 * 2^1, , 3^0 * 2^2, 3^0 * 2^3, 
    3^1 * 2^0, ....
    ...                                3^2 * 2^3, 

 この時に使う組み合わせを生成する。

  配列listに{2,3}と与えると、以下の組み合わせを生成する。
  listはゼロ終端で与えるので実際は{2,3,0}を与える。

  {2,3} = 
      (0,0),(0,1),(0,2),(0,3),
      (1,0),(1,1),(1,2),(1,3),
      (2,0),(2,1),(2,2),(2,3),
*/

#include <stdio.h>

#define MAX_ARRAY 5


// 再帰版
void saiki_aux(int depth, const int list[], int work_list[])
{
    int i;

    if (list[depth] == 0) {
	for (i = 0; list[i] != 0; i++)
	    printf("%d,", work_list[i]);
	printf("\n");
    } else {
	saiki_aux(depth + 1, list, work_list);
	for (i = 0; i < list[depth]; i++) {
	    work_list[depth]++;
	    saiki_aux(depth + 1, list, work_list);
	}
	work_list[depth] = 0;
    }
}

void saiki(const int list[])
{
    int i, work_list[MAX_ARRAY + 1];

    for (i = 0; i <= MAX_ARRAY; i++)
	work_list[i] = 0;

    saiki_aux(0, list, work_list);
}

// 再帰版をloopに展開
void saiki_unroll(const int list[])
{
    int carry, i, j, depth, len, work_list[MAX_ARRAY + 1];

    for (i = 0; list[i] != 0; i++) {
	work_list[i] = 0;
    }
    len = i;

    carry = 0;			//桁上がり
    depth = 0;			//再帰の深さ
    while (depth >= 0) {
	if (depth == len)	//再帰の最深部
	{
	    for (j = 0; j < len; j++)
		printf("%d,", work_list[j]);
	    printf("\n");
	    depth--;		//再帰を一つ浅い所に戻る
	    carry = 1;		//1を足せ
	    continue;
	}

	if (carry == 1) {
	    work_list[depth] += carry;
	    carry = 0;
	    if (work_list[depth] > list[depth]) {	//桁上り
		work_list[depth] = 0;
		carry = 1;
		depth--;	//再帰を一つ浅い所に戻る
		continue;
	    }
	}
	//桁上りが無いので再帰を最深部に戻す
	depth = len;
    }
}

// ループ, カウンタを実装しているだけ
// よくよく考えると、saiki_unrollを最適化しているだけ。
void counter(const int list[])
{
    int carry, len, i, work_list[MAX_ARRAY + 1];

    for (len = 0; list[len] != 0; len++) {
	work_list[len] = 0;
    }

    while (1) {
	for (i = 0; i < len; i++)
	    printf("%d,", work_list[i]);
	printf("\n");

	//一番下の桁に1を足す
	carry = 1;
	for (i = len - 1; i >= 0 && carry == 1; i--) {
	    work_list[i] += carry;
	    carry = 0;
	    if (work_list[i] > list[i]) {	//桁上り
		work_list[i] = 0;
		carry = 1;
	    }
	}
	//最上位桁で桁上りが起きるという事はすべての組み合わせが生成された。
	if (carry == 1)
	    break;
    }
}


int main()
{
    int list[MAX_ARRAY + 1] = { 2, 1, 3, 0 };	// ゼロ終端

    //念のため
    list[MAX_ARRAY] = 0;

    printf("*saiki\n");
    saiki(list);

    printf("*saiki_unroll\n");
    saiki_unroll(list);

    printf("*counter\n");
    counter(list);
}