半標準ヤング盤の列挙アルゴリズム - 数学の命題示しました

追記：このプログラムにはおそらくバグがあり、特定のサイズのヤング版で正しく列挙できない現象が起こります。
使わないでください。
(2020/09/13)

12月頃，このブログで「平面分割」を列挙するアルゴリズムを載せました．
iwalion.hatenablog.com

今回は似てますが「要素に上限を持つ半標準ヤング盤」を列挙するアルゴリズムを作りました．

半標準ヤング盤とは

長さ $k$ 以下の整数の分割 $\lambda=(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k \geq 0)$ をとります．各 $\lambda_i$ は非負整数です．また， $k$ 以上の非負整数 $b\geq k$ をとります．
以下の二条件を満たす $k\times \lambda_1$ 行列 $A=(a_{i,j})_{1\leq i\leq k,1\leq j\leq \lambda_1}$ を列挙することを考えます．

$A$ の各要素は $1\leq i\leq k, 1\leq j\leq \lambda_i$ のとき， $1$ から $b$ までの整数で，それ以外の $i,j$ のとき $0$ .

$A$ の各要素は $1\leq i\leq k, 1\leq j\leq \lambda_i$ の範囲で，列に関して狭義増大，行に関して弱い意味で増大．

今回も詳細は書くのがめんどくさいので省きますが，c++のコードを載せておきます．
このコードでは例として $\lambda=(5,3,3,2), b=6$ を列挙しています．

たとえば，こんなやつです↓ （下向きに強く増大，右向きに非減少．0は省略している．）

1 1 3 4 4
2 3 4
3 4 5
6 6

このコードで列挙した半標準ヤング盤の集合が間違っていなさそうなことを，「Jadobi-Trudi恒等式」に当てはめて何通りかの $\lambda,b$ で検算しました．
「Jadobi-Trudi恒等式」については，ウィリアム・フルトン『ヤング・タブロー』（丸善，2019）のp. 78か，StanleyのEnumerative Combinatorics vol. 1(Cambridge, 2010) のp. 342を参照してください．

注意：main関数内でc++11が必要な書き方をしているので，-std=c++11をつけてコンパイルしてください．

//
//
// 最大要素を指定する半標準版ヤング盤列挙プログラム
//
// 07/09/2019
//
// author: iwalion
//
//
//
//

#include <iostream>
#include <vector>
#include <fstream>


#define INFTY 10000

using namespace std;

class Tableau
{
	//タブローの本体
	//1000 1000 1000 1000 1000
	//1000 1000 1000 1000    6
	//1000 1000 1000    6    5
	//1000    6    6    5    4
	//1000    5    5    4    3
	// のように行に関して弱く減少，列に関して強く減少の形で保持する
	// 1000は空欄を示す．
	// タブローのタイプより縦横ともにひとつ大きい配列を確保する．
	private:
		vector< vector<int> > my_tableau;
		vector<int> type;
		int size_row;
		int size_col;
		int max_entry;
		
		const int my_INF = INFTY;

	//コンストラクタ・デストラクタ
	public:
		Tableau(vector<int> partition, int max_number);
		~Tableau();

	public:
		//タブローを標準出力で見る
		void inspect();

		//タブローの全順序に従って一つ増やす
		//増やせたら1，増やせなかったら0を返す
		int increase_by_one(void);

		vector< vector<int> > nakami(void){
			return my_tableau;
		}

		//整形して出力するための関数
		void output_to_file(ofstream &ofs);
};

void Tableau::output_to_file(ofstream &ofs)
{
	for(int i=0; i<=type.size()-1; i++){
		for(int j=0; j<=type[0]-1; j++){
			if(my_tableau[size_row-i-1][size_col-j-1] == my_INF){
				ofs << 0;
			}else{
				ofs << my_tableau[size_row-i-1][size_col-j-1];
			}
			if(j < type[0]-1 ){
				ofs << ',';
			}
		}
		if(i < type.size()-1){
			ofs << '/';
		}
	}
	ofs << '\n';
	return;
}


Tableau::Tableau(vector<int> partition, int max_number)
{

	if(max_number >= my_INF){
		cerr << "error: プログラム上の定数INFを大きくしてください" << endl;
		exit(1);
	}
	if(partition.size() > max_number){
		cerr << "error: 指定された最大要素は小さすぎて無理です" << endl;
		exit(1);
	}
	if(partition.size() == 0){
		cerr << "error: コンストラクタへの入力が空です\n" << endl;
		exit(1);
	}
	for(int i=0; i<=partition.size()-1; i++){
		if(partition.size() > 1 &&  partition[i] < partition[i+1]){
			cerr << "error: コンストラクタへの入力は単調非増加にしてください\n" << endl;
			exit(1);
		}
	}

	//必要なサイズよりひとつ大きい配列を確保する	
	//空欄はINFTYで埋めておく
	vector< vector<int> > hoge;
	for(int i=0; i<=partition.size(); i++){
		vector<int> piyo(partition[0]+1, my_INF);
		hoge.push_back(piyo);
	}


	//データの書き込み
	max_entry = max_number;
	my_tableau = hoge;
	size_row = my_tableau.size();
	size_col = (my_tableau[0]).size();
	type = partition;


	//大きさが一番小さいタブローを書き込む
	for(int i=0; i<=type.size()-1; i++){
		for(int j=0; j<=type[i]-1; j++){
			my_tableau[size_row-i-1][size_col-j-1] = i+1;
		}
	}


}

Tableau::~Tableau()
{
	cout << "破棄" << endl;
}


int Tableau::increase_by_one(void)
{
	for(int i=0; i<=type.size()-1; i++){
		for(int j=0; j<=type[i]-1; j++){

			//増やせる数字を探す
			if( my_tableau[size_row-i-1][size_col-j-1] < my_tableau[size_row-i-1][size_col-j-2] ){
				if( my_tableau[size_row-i-1][size_col-j-1] < my_tableau[size_row-i-2][size_col-j-1] -1 ){
					if(my_tableau[size_row-i-1][size_col-j-1] < max_entry){
						my_tableau[size_row-i-1][size_col-j-1] += 1;

						//もし増やした場合，それより以前の場所を全部初期化する．
						for(int inner_i=0; inner_i<=i; inner_i++){
							//今いる行より下は全部初期化
							if(inner_i < i){
								for(int inner_j=0; inner_j<=type[inner_i]-1; inner_j++){
									my_tableau[size_row-inner_i-1][size_col-inner_j-1] = inner_i+1;
								}
							}else
							//今いる行は，今いるところまで初期化
							{
								for(int inner_j=0; inner_j<=j-1; inner_j++){
									my_tableau[size_row-inner_i-1][size_col-inner_j-1] = inner_i+1;
								}
							}
						}
						
						//増やせたら1を返す
						return 1;
					}
				}
			}
			//三重ifここまで
		}
	}

	//増やせる数字が一つもないとき0を返す
	return 0;
}

void Tableau::inspect()
{
	for(int i=0; i<=size_row-1; i++){
		for(int j=0; j<=size_col-1; j++){
			if(my_tableau[i][j] != my_INF){
				printf("%2d",my_tableau[i][j]);
			}else{
				//printf("%5d",my_tableau[i][j]);
				printf("  ");
			}
		}
		printf("\n");
	}
}

int main(){
	vector<int> a{5,3,3,2};
	Tableau unko(a,6);

	int num = 1;
	

	ofstream ofs;
	ofs.open("TAB_5332_6.txt", ios::out);

	while(1){
		unko.inspect();
		unko.output_to_file(ofs);
		if(unko.increase_by_one() == 0){
			printf("NUM = %d\n",num);
			break;
		}
		num++;
	}

	ofs.close();
	return 0;
}