/*
  Copyright(C) 2014 Ryuji Matumoto / matumoto(AT)pluto.ai.kyutech.ac.jp

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

  配布ページ
  http://www.pluto.ai.kyutech.ac.jp/~matumoto/syougi/

  同じ物を含む順列の生成プログラム

  生成するのは、順列であって、組み合わせではない。

*数学的な話。

  Aがa個、Bがb個、Cがc個ある場合は、順列の総数は

  (a+b+c)! / (a! b! c!)
  
  Ref: http://kakuritsu.com/onaji.html


* 生成アルゴリズム
オリジナル? (まぁ同じ事を考えた人は多数いるだろう。)

Aが2個、Bが3個, Cが1個あるとする。まだ値を置いてない空き地を _ として

まず、Aが2個、空き地を4個(Bが3個 + Cが1個)を置くパターン全てを作る。
---
1.　AA____
2.　A_A___
3.　A__A__
4.　A___A_
    .. 
15. ____AA
---

みたいに生成して、次に

1. の空き地にBを3個、空き地を1個置くパターン全てを作る。
---
1.1. AABBB_
1.2. AABB_B
1.3. AAB_BB
1.4. AA_BBB
---

つぎに、
1.1の空き地にCを置く
---
1.1.1. AABBBC
---

1.2の空き地にCを置く
---
1.2.1. AABBCB
---

てな感じ。

*/
#include <iostream>
using namespace std;

#define AKICHI (-1)
//#define YOUSO_TERMINAL (-1)
#define YOUSO_TERMINAL (100)

//#define COUNT_ONLY 0
int static kumi_count = 0;
int static saiki_count = 0;

void print_list(int leng, int list[]){
    kumi_count++;
#ifndef COUNT_ONLY
  cout << "[";
  for(int i = 0; i < leng; i++){
    cout << list[i];;
    if(i != (leng-1)){
      cout << ",";
    }
  }
  cout << "]" << endl;
#endif
}

/* アルゴリズム練習版
  youso[0][0] = 順列生成に使う数字,   youso[0][1] = 順列生成に使う数字の個数

  list[] = 生成する順列
  list_pos = listで現在値を置いている場所
*/
void gen_kumi(const int leng, int youso[][2], int list[], int list_pos){

  saiki_count++;
  if(0){
    cout << "In gen_kumi, target youso = " << youso[0][0]
	 << ", list_pos = " << list_pos << endl;
    cout.flush();
  }

  if(youso[0][0] == YOUSO_TERMINAL){
    /* 全て置いた */
    print_list(leng, list);
    return;
  }

  if(youso[0][1] == 0){
    // 現在置いている数字が残りゼロになったので、次の数字に移る 
    // youso+1 -> youso[1][0]と同じ意味。
    gen_kumi(leng, youso+1, list, 0);
    return;
  }

  // リストの終端。 まだ現在置いている数字が残ってる。
  if(list_pos == leng){
    return;
  }

  if(list[list_pos] == AKICHI){
    // 数字を置く
    list[list_pos] = youso[0][0];
    youso[0][1]--;

    // 再帰
    gen_kumi(leng, youso, list, list_pos+1);

    // 数字を取り除く。
    list[list_pos] = AKICHI;
    youso[0][1]++;

  }
  
  // 数字をおかず、空き地をあける。
  gen_kumi(leng, youso, list, list_pos+1);  
}

/*
  アルゴリズム最適化版

  list[] = 生成する順列

  list_pos = listで現在値を置いている場所

  list_akichi = listで空き地の数。

  list_aft_akichi = list_posより後ろの空き地の数。利かずの駒並べの
                    全解探索ではこの値を数えるのは難しいので使ってない。

*/
void gen_kumi2(const int leng, int youso[][2],
	      int list[], int list_pos, int list_akichi, int list_aft_akichi){

  saiki_count++;
  if(0){
    cout << "In gen_kumi2, target_youso = " << youso[0][0]
	 << ", list_pos = " << list_pos 
	 << ", list_akichi = " << list_akichi 
	 << ", list_aft_akichi = " << list_aft_akichi << endl;
    cout.flush();
  }

  /* listで空き地は無い。つまり全て置いた。 */ 
  if(list_akichi == 0){
    print_list(leng, list);
    return;
  }

  // 現在置いている数字が残りゼロになったので、次の数字に移る */
  // youso+1 -> youso[1][0]と同じ意味。
  if(youso[0][1] == 0){
    gen_kumi2(leng, youso+1, list, 0, list_akichi, list_akichi);
    return;
  }

  // list_posより後ろの空き地が、残りの要素より多い
  // たぶんこの条件式は成立しない。
  if(list_aft_akichi < youso[0][1]){
    //cout << "MAYBE Unexec \n";
    return;
  }

  // 頭出し
  while(list[list_pos] != AKICHI){
    list_pos++;
  }

  // 数字をひとつ置いて再帰
  list[list_pos] = youso[0][0];
  youso[0][1]--;

  list_aft_akichi--;

  if(1 /* ここに将棋の盤面評価部を入れる */){
    gen_kumi2(leng, youso, list, list_pos+1, list_akichi-1, list_aft_akichi);
  }

  // 数字を取り除く。
  list[list_pos] = AKICHI;
  youso[0][1]++;

  // 空き地のまま、数字をおかずに再帰。但し空き地の数が残りの要素より多いのみ。
  if(list_aft_akichi >= youso[0][1]) {
    gen_kumi2(leng, youso, list, list_pos+1, list_akichi, list_aft_akichi);  
  }
}

int main()
{
  /* {{順列に使う数字1, 数字の個数}, {順列に使う数字2, 数字の個数}, {YOUSO_TERMINAL, 0個}} 
   YOUSO_TERMINALは順列生成に利用不可 */
  int youso[][2] = {{1, 2},{2, 3},{0,2},{YOUSO_TERMINAL,0}}; 

  int leng;

  leng=0;
  for(int i=0; youso[i][0]!= YOUSO_TERMINAL; i++){
    leng+=youso[i][1];
  }

  cout << "leng = " << leng << endl;

  int list[leng];
  for(int i=0; i< leng; i++){
    list[i]=AKICHI;
  }

  //習作
  //gen_kumi(leng, youso, list,0);

  //最適化版
  gen_kumi2(leng, youso, list, 0, leng, leng);

  cout << "KUMIAWASE = " << kumi_count << endl;
  cout << "SAIKI KAISU = " << saiki_count << endl;
}