数学と物理の問題

組み合わせの一覧を取得するプログラムを書きました。

Combination::Combination

Combinationは通りすべてのパターンを取得します。

m_flag[index]に、index番目（計個＝m_size）のビットフラグ(int型)を収納します。

index=0では、下位ビットから個埋めて、次からのパターンでは上位ビットに繰り上げていきます。
（たとえば、r=5の場合、0011111からスタートします。次は0101111です。）

“結果”を見て具体的に考えながら、アルゴリズムを追うと分かりやすいでしょう。

//r個をn人で分ける。１人１個まで
Combination::Combination(int n, int r){
	m_n = n;
	m_size = PossibleOutcomes::Combination(n, r);
	m_flag = new int[m_size];
	for (int i=0; i<m_size; i++){
		m_flag[i] = 0;
	}

	m_flag[0] = (1<<r) - 1;//下位の人から順に、１個ずつ渡す（計r個渡す）

	for (int i=1; i<m_size; i++){
		m_flag[i] = m_flag[i-1];
		int j = 0;
		while (!(m_flag[i] & (1<<j))){//持っている人を見つける=j
			j++;
		}
		int k = j;//下位から見たときに、最初に持っている人
		do { 
			j++;
		} while (m_flag[i] & (1<<j));//持っていない人を見つける=j
		int m = (1<<j);
		m_flag[i] |= m;//持っていない人に渡す
		m_flag[i] &= ~(m-1);//下位の持っていた人達から没収
		m_flag[i] |= (1<<(j-k-1)) -1;//残った分を下位の人達に渡す
	}
}

main:

int main() {
	Combination obj(5,2);
	for (int i=0; i<obj.GetSize(); i++){
		std::cout << "[" << i << "]" << std::flush;
		for(int j=obj.GetN()-1; j>=0; j--){
			std::cout << " " << obj.Get(i,j) << std::flush;
		}
		std::cout << std::endl;
	}
	int a;
	std::cin >> a ;
	return 0;
}

結果は次のようになります。(n=5, r=2)

RepeatedCombination::RepeatedCombination

重複有りの組み合わせでは、１人何個でも持てるので0, 1以上の情報を持つ必要があります。

そこで、int型の配列を使います。

全パターンの配列を取得したいので、結局２元配列を使うことになります。

//r個をn人で分ける。１人何個でもよい
RepeatedCombination::RepeatedCombination(int n, int r){
	m_n = n;
	m_size = PossibleOutcomes::RepeatedCombination(n, r);
	m_share = new int*[m_size];
	for (int i=0; i<m_size; i++)
		m_share[i] = new int[n];

	m_share[0][0] = r;
	for (int i=1; i<m_n; i++){
		m_share[0][i] = 0;
	}

	for (int i=1; i<m_size; i++) {
		for (int j=0; true/*j<m_n*/; j++) {
			if(m_share[i-1][j] > 0) {//０個持ちでない人を見つける[j]
				m_share[i][0] = m_share[i-1][j] - 1;//その人の持つ個数から１個引いた残りを最下位の人（[0]の人）に渡す
				for(int k=1; k<=j; k++)
					m_share[i][k] = 0;//取り上げられた人以下の人は０個持ちに（[0]の人は除く）
				m_share[i][j+1] = m_share[i-1][j+1] + 1;//取り上げた人より１つ上の人は１個受け取る[j+1]
				for(int k=j+2; k<m_n; k++)
					m_share[i][k] = m_share[i-1][k];//それ以上の人は変わらず
				break;
			}
		}
	}
}

結果：（n=5, r=2）

以下はクラス宣言のファイルと階乗計算などの関数です。

class PossibleOutcomes {
protected:
	__int64 Factorial(int x) const;//階乗計算
	__int64 Junretsu(int x, int k) const;//順列
	int Combination(int n, int r) const;//組み合わせ
	int RepeatedCombination(int n, int r) const;//重複組み合わせ
};

//n個からr個選ぶ。同じものは選べない＝重複無しの組み合わせ
//（r個をn人で分ける。１人１個まで）←関数中のコメントはこの考え方
class Combination : public PossibleOutcomes {
public:
	Combination(int n, int r);
	~Combination();
	int Get(int index) const;//int型のビットフラグを取得
	int Get(int index, int n) const;//n番目の人がもつかどうか。持っていれば1
	int GetSize() const;//パターン数を取得
	int GetN() const;
protected:
	int m_n;//保持人数
	int m_size;//パターン数
	int *m_flag;
};

//n種類のものからr個選ぶ＝重複組み合わせ
//（r個をn人で分ける。１人何個でも）←関数中のコメントはこの考え方
class RepeatedCombination : public PossibleOutcomes {
public:
	RepeatedCombination(int n, int r);//r個をn人で分ける
	~RepeatedCombination();
	int Get(int index, int n) const;//n番目の人がもつ個数を取得
	int GetSize() const;//パターン数を取得
	int GetN() const;
protected:
	int m_n;//保持人数
	int m_size;//パターン数
	int **m_share;
private:
};

__int64 PossibleOutcomes::Factorial(int x) const{
	__int64 temp = 1;
	for(; x>0; x--)
		temp *= x;
	return temp;
}

__int64 PossibleOutcomes::Junretsu(int x, int k) const{
	__int64 temp = x;
	for(int i=1; i<k; i++)
		temp *= x-i;
	return temp;
}

int PossibleOutcomes::Combination(int n, int r) const{
	int temp = 1;
	if (r > n - r)
		r = n - r;
	for (int i=1; i<=r; i++)
		temp = (temp*(n-r+i)) / i;
	return temp;
}

int PossibleOutcomes::RepeatedCombination(int n, int r) const{
	return Combination(n+r-1, r);
}