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

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


  約数を生成する。
  引数の渡しかたはgen_kumiawase.cを参照する。

  約数は平方数以下を生成すれば、平方数以上は自動生成できる。
  36の約数2を求めれば、36/2も約数。以下のflagでその処理を
  する。一部関数のみ。
  
  -DSQRT_YAKUSU

*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_ARRAY 5

void check(int yakusu, const int work_list[], const int plist[])
{
    int i, j, y2 = 1;
    for (i = 0; plist[i] != 0; i++)
	for (j = 0; j < work_list[i]; j++)
	    y2 *= plist[i];
    if (y2 != yakusu) {
	printf("NG:");
	exit(1);
    }
}

void saiki_aux(int depth, const int list[], const int plist[],
	       int work_list[], int a_yakusu)
{
    int i;
    int yakusu = a_yakusu;

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

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

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

    saiki_aux(0, list, plist, work_list, 1);
}

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

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

    carry = 0;			//桁上がり
    depth = 0;			//再帰の深さ
    yakusu = 1;
    while (depth >= 0) {
	if (depth == len)	//再帰の最深部
	{
	    for (i = 0; i < len; i++)
		printf("%d,", work_list[i]);
	    printf("\n");
	    check(yakusu, work_list, plist);
	    printf("yakusuu=%d\n", yakusu);


	    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;
		work_yakusu[depth] = 1;
		depth--;	//再帰を一つ浅い所に戻る
		continue;
	    } else {
		yakusu = work_yakusu[depth] * plist[depth];
	    }
	    //桁上りが無いので再帰を最深部に戻す
	}
	for (i = depth; i < len; i++)
	    work_yakusu[i] = yakusu;
	depth = len;
    }
}

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

#ifdef SQRT_YAKUSU
    int sqrt_gousei = 1;
    int gousei = 1;
#endif

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

#ifdef SQRT_YAKUSU
    for (i = 0; i < len; i++) {
	int j;
	for (j = 0; j < list[i]; j++)
	    gousei *= plist[i];
    }
    sqrt_gousei = sqrt(gousei) + 0.5;
#endif

    yakusu = 1;
    while (1) {
	int carry;		//桁上がり

	for (i = 0; i < len; i++)
	    printf("%d,", work_list[i]);
	printf("\n");
	check(yakusu, work_list, plist);
	printf("yakusuu=%d\n", yakusu);
#ifdef SQRT_YAKUSU
	if (gousei / yakusu != yakusu)	//平方数だったら同じ数が二つ出る
	    printf("yakusuu=%d\n", gousei / yakusu);
#endif

	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;
	    } else {
		yakusu = work_yakusu[i] * plist[i];
#ifdef SQRT_YAKUSU
		if (yakusu > sqrt_gousei) {
		    work_list[i] = 0;
		    carry = 1;
		}
#endif
	    }
	}

	//最上位桁で桁上りが起きるという事はすべての組み合わせが生成された。
	if (carry == 1)
	    break;

	for (i++; i < len; i++)
	    work_yakusu[i] = yakusu;
    }
}

int main()
{
#if 0
    int list[MAX_ARRAY + 1] = { 2, 1, 3, 0 };	// ゼロ終端
    int plist[MAX_ARRAY + 1] = { 7, 5, 3, 0 };	// ゼロ終端//check関数がゼロ終端を要求してる
#endif

#if 1
    int list[MAX_ARRAY + 1] = { 2, 2, 0 };	// ゼロ終端
    int plist[MAX_ARRAY + 1] = { 5, 3, 0 };	// ゼロ終端//check関数がゼロ終端を要求してる
#endif


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

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

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

    printf("*saiki_unroll\n");
    counter(list, plist);

    return 0;
}