配列組合せアルゴリズムの再帰的実現

1303 ワード

配列の組み合わせを復習します
1.配列は簡単で、コードは以下の通りである.

void perm(string &str, int k)
{
	int size = str.size();
	if (k == size - 1)
		cout << str << endl;
	else
	{
		for (int i = k; i < size; ++i)
		{
			swap(str.at(i), str.at(k));
			perm(str, k + 1);
			swap(str[i], str[k]);
		}
	}
}

2.組み合わせが分かりにくい.ここでindexは文字の下付き文字を格納し、sizeはstr長であり、sizeからm文字の組み合わせを選択する.注意組合せには順序がないので、indexのデフォルトは下付きの順序、すなわちindex[i]

void combine(string &str, int index[], int k, const int m, int size)
{
for (int i = size - 1; i >= k - 1; --i)
{
index[k - 1] = i;
if (k > 1)
{
combine(str, index, k - 1, m, i);
}
else
{
for(int i = 0; i < m; ++i)
cout << str[index[i]];
cout << endl;
}
}
}

3.主関数

int main()
{
	string str;
	cin >> str;
	const int LEN = 2;
	int index[LEN];
	int size = str.size();
	cout << "____-----------________" << endl;
	perm(str, 0);
	cout << "____-----------________" << endl;
	combine(str, index, LEN, LEN, size);
	return 0;
}

マトリックス求逆アルゴリズム

黄金分割に基づく修正Powellアルゴリズム