概要
範囲の順列の取得や順列かの判定を行います。
範囲の指定方法は、
・std::xxx(C++03): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲 [first, last) のイテレータ―を指定します。
・std::ranges::xxx(C++20): 対象の範囲を直接指定します。
条件判定に関数を指定できます。※
std::ranges::xxx(C++20): 射影(projection)関数を指定できるものがあります。※
※詳細についてはこちらを参照してください。
https://mappuri.com/program/cpp20-algorithm/
順列はある範囲の要素の組み合わせを表します。例えば次の3つの要素があった場合、次の順列があります。
範囲の順列の取得や順列かの判定
next_permutation
範囲の辞書順で次の順列を取得します。
範囲は双方向に読み書き可能である必要があります。
prev_permutation
範囲の辞書順で前の順列を取得します。
範囲は双方向に読み書き可能である必要があります。
is_permutation
2つの範囲が順列か判定します。
範囲は順方向に読み書き可能である必要があります。
next_permutation, prev_permutation, is_permutation のサンプル(C++03, C++11)
#include <iostream>
/** r 内の [first, last) の範囲と値を出力 範囲:[0, 9) 値:1 2 3 4 5 4 5 6 6 */
template<class T, class U, class V>
static void output(T&& r, U&& first, V&& last) {
std::cout << "範囲:[" << std::distance(std::begin(r), first) << ", " << std::distance(std::begin(r), last) << ")";
std::cout << " 値:";
std::string delim = "";
for (auto i = first; i != last; ++i, delim = ", ") {
std::cout << delim << *i;
}
std::cout << std::endl;
}
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
{
// 範囲の辞書順で次の順列を取得します。(C++03)
std::vector<int> r = { 1, 2, 3 };
do {
output(r, r.begin(), r.end());
// 範囲:[0, 3) 値:1, 2, 3
// 範囲:[0, 3) 値:1, 3, 2
// 範囲:[0, 3) 値:2, 1, 3
// 範囲:[0, 3) 値:2, 3, 1
// 範囲:[0, 3) 値:3, 1, 2
// 範囲:[0, 3) 値:3, 2, 1
} while (std::next_permutation(r.begin(), r.end()));
}
{
// 範囲の辞書順で前の順列を取得します。(C++03)
std::vector<int> r = { 3, 2, 1 };
do {
output(r, r.begin(), r.end());
// 範囲:[0, 3) 値:3, 2, 1
// 範囲:[0, 3) 値:3, 1, 2
// 範囲:[0, 3) 値:2, 3, 1
// 範囲:[0, 3) 値:2, 1, 3
// 範囲:[0, 3) 値:1, 3, 2
// 範囲:[0, 3) 値:1, 2, 3
} while (std::prev_permutation(r.begin(), r.end()));
}
{
// 2つの範囲が順列か判定します。(C++11)
std::vector<int> r = { 1, 2, 3 };
std::vector<int> r1 = { 3, 2, 1 };
std::vector<int> r2 = { 4, 2, 1 };
bool is_permutation1 = std::is_permutation(r.begin(), r.end(), r1.begin(), r1.end());
std::cout << std::boolalpha << "is_permutation1 = " << is_permutation1 << std::endl; // is_permutation1 = true
bool is_permutation2 = std::is_permutation(r.begin(), r.end(), r2.begin(), r2.end());
std::cout << std::boolalpha << "is_permutation2 = " << is_permutation2 << std::endl; // is_permutation2 = false
}
return 0;
}
next_permutation, prev_permutation, is_permutation のサンプル(C++20 range)
#include <algorithm>
#include <iostream>
#include <vector>
int main(int argc, char* argv[]) {
{
// 範囲の辞書順で次の順列を取得します。(C++03)
std::vector<int> r = { 1, 2, 3 };
do {
output(r, r.begin(), r.end());
// 範囲:[0, 3) 値:1, 2, 3
// 範囲:[0, 3) 値:1, 3, 2
// 範囲:[0, 3) 値:2, 1, 3
// 範囲:[0, 3) 値:2, 3, 1
// 範囲:[0, 3) 値:3, 1, 2
// 範囲:[0, 3) 値:3, 2, 1
} while (std::ranges::next_permutation(r).found);
}
{
// 範囲の辞書順で前の順列を取得します。(C++03)
std::vector<int> r = { 3, 2, 1 };
do {
output(r, r.begin(), r.end());
// 範囲:[0, 3) 値:3, 2, 1
// 範囲:[0, 3) 値:3, 1, 2
// 範囲:[0, 3) 値:2, 3, 1
// 範囲:[0, 3) 値:2, 1, 3
// 範囲:[0, 3) 値:1, 3, 2
// 範囲:[0, 3) 値:1, 2, 3
} while (std::ranges::prev_permutation(r).found);
}
{
// 2つの範囲が順列か判定します。(C++03)
std::vector<int> r = { 1, 2, 3 };
std::vector<int> r1 = { 3, 2, 1 };
std::vector<int> r2 = { 4, 2, 1 };
bool is_permutation1 = std::ranges::is_permutation(r, r1);
std::cout << std::boolalpha << "is_permutation1 = " << is_permutation1 << std::endl; // is_permutation1 = true
bool is_permutation2 = std::ranges::is_permutation(r, r2);
std::cout << std::boolalpha << "is_permutation2 = " << is_permutation2 << std::endl; // is_permutation2 = false
}
return 0;
}
コメント