next_permutation C++

C++ 順列を列挙するプログラムn!

　next_permutationを使って順列を全列挙するためには、もとの配列を昇順にソートしておく必要があります。以下のプログラムでは、{1, 2, 3, 4}を辞書順の一つ後に並び替え続けて、n!通りの並びを列挙します。{1, 2, 3, 4} {1, 2, 4, 3} {1,3, 2, 4}....{4, 3, 2, 1}となります。

int main() {
	vector<int> v={1, 2, 3, 4};
	do{
		for(int i=0; i<4; i++){
			cout << v[i];
			if(i!=3) cout << " ";
		}
		cout << endl;
	}while(next_permutation(v.begin(), v.end()));
	return 0;
}

大小関係のある要素で構成されていれば、文字列でも実装することが出来ます。

int main() {
	string v = "ABCD";
	do{
		cout << v << endl;
	}while(next_permutation(v.begin(), v.end()));
	return 0;
}

ちなみに、next_permutationではなく、prev_permutationとすれば、降順から昇順に列挙できます。その際には、配列や文字列を予め降順にソートしておく必要があります。