「並び替え方」の全探索は、C++ なら next_permutation()、Python3 なら itertools.permutations() が使える！
問題概要
個の長さ
の文字列
が与えられる。
これらを並び替えて得られる文字列 であって、
「 と
が 1 文字違いである」(
)
という条件を満たすものが存在するかどうかを判定せよ。
制約
解法：まず選択肢の個数を check！
今回の問題は「並び替えを探索する」というタイプの問題になっている！
たとえば、 "bbed", "abcd", "abed", "fbed" という入力では、これら 4 つの文字列を上手に並び替えることで、「隣り合う文字列同士が 1 文字違いになるように」できるかを判定することとなる。パズルちっくな問題だ。
並び替え問題においては、探索したい選択肢は 通りある (
は並び替える対象の個数)。
が大きくなると凶悪なまでに選択肢の個数が膨れ上がってしまう。しかし、
が小さければ全探索可能だ。
今回は、 と小さいので、全探索が十分に可能だ。ちなみに、
である。この程度の個数の選択肢なら、パソコンなら余裕で調べられる。
通りを調べる方法
全探索の方法としては、「標準ライブラリを使う」解法と、「再帰関数を用いる」解法とが考えられる。ここでは、標準ライブラリを使ってみよう。再帰関数を用いる方法については、下の方で簡単に触れようと思う。
さて、並び替えを全探索するための標準ライブラリとしては、
- C++ では、
next_permutation() - Python3 では、
itertools.permutations()
が使える。
C++ の next_permutation()
この関数は、「辞書式順序において次の順列」を求めるというものだ。
たとえば、 {
} という
vector<int> 型変数に対して next_permutation(A.begin(), A.end()) を適用すると、 {
} となるし、続けて適用すると、
{
} となる。なお、関数
next_permutation(A.begin(), A.end()) は、次の順列があるときは true を返し、次の順列がないとき ( {
} などのとき) は
false を返す。
vector<string> 型変数に対しても適用できる。たとえば、 {"bbed", "abcd", "abed", "fbed"} に対して
next_permutation(A.begin(), A.end()) を適用すると、 {"bbed", "abcd", "fbed", "abed"} となる。
この関数を利用して、今回の問題を解くアルゴリズムは、次の疑似コードのように書ける。注意点として、配列 を最初にソートしておく必要がある。辞書式順序が最小の状態から探索を開始するようにするためだ。
なお、next_permutation(S.begin(), S.end()) は最後尾の並び替え方に到達したら false を返すので、最後尾に到達した時点で do-while ループを抜けることとなる。
// 辞書式順序が最小の状態にしておく sort(S.begin(), S.end()); do { bool ok = true; for (int i = 0; i < N-1; ++i) { if (S[i] と S[i+1] が一文字違いでない) ok = false; } if (ok) { cout << "Yes" << endl; return 0; } } while (next_permutation(S.begin(), S.end())); cout << "No" << endl;
Python3 の itertools.permutations()
Python の itertools はとにかく優秀だ。「並び替え方」に限らず、色んなパターンの全探索を実現してくれる。
Python なら、今回は次のようなコードを書くだけだ。めっちゃ簡単！
for T in itertools.permutations(S): ok = True for i in range(N - 1): if T[i] と T[i+1] が一文字違いでない: ok = False if ok: print("Yes") exit() print("No")
解答例
C++ でも Python3 でも、計算量は となる。
C++
#include <bits/stdc++.h> using namespace std; // 文字列 A, B の文字が異なる箇所の個数を求める関数 int diff(const string &A, const string &B) { int res = 0; for (int i = 0; i < A.size(); ++i) { if (A[i] != B[i]) ++res; } return res; } int main() { int N, M; cin >> N >> M; vector<string> S(N); for (int i = 0; i < N; ++i) cin >> S[i]; sort(S.begin(), S.end()); do { bool ok = true; for (int i = 0; i < N-1; ++i) { if (diff(S[i], S[i+1]) != 1) ok = false; } if (ok) { cout << "Yes" << endl; return 0; } } while (next_permutation(S.begin(), S.end())); cout << "No" << endl; }
Python3
import itertools # 文字列 A, B の文字が異なる箇所の個数を求める関数 def diff(A, B): res = 0 for a, b in zip(A, B): if a != b: res += 1 return res N, M = map(int, input().split()) S = [input() for _ in range(N)] S.sort() for T in itertools.permutations(S): ok = True for i in range(N - 1): if diff(T[i], T[i+1]) != 1: ok = False if ok: print("Yes") exit() print("No")
別解：再帰関数を用いる
C++ でのみ、再帰関数を用いた解法を示す。再帰関数を用いた全探索をするための、具体的な方法論については、次の記事に記した。
ここでは、配列 を並び替えながら前から順に決めていくような再帰関数を実装した。
C++
#include <bits/stdc++.h> using namespace std; // 文字列 A, B の文字が異なる箇所の個数を求める関数 int diff(const string &A, const string &B) { int res = 0; for (int i = 0; i < A.size(); ++i) { if (A[i] != B[i]) ++res; } return res; } // 再帰関数 // 最初の i 個は確定した状態を考える bool rec(vector<string> &S, int i) { // 文字列を使い切ったら true if (i == S.size()) return true; // まだ使っていない文字列を選ぶ for (int j = i; j < S.size(); ++j) { if (i == 0 || diff(S[i-1], S[j]) == 1) { swap(S[i], S[j]); // S[j] を i 番目に持ってくる if (rec(S, i + 1)) return true; swap(S[i], S[j]); // 元に戻す } } return false; } int main() { int N, M; cin >> N >> M; vector<string> S(N); for (int i = 0; i < N; ++i) cin >> S[i]; cout << (rec(S, 0) ? "Yes" : "No") << endl; }
Python3
# 文字列 A, B の文字が異なる箇所の個数を求める関数 def diff(A, B): res = 0 for a, b in zip(A, B): if a != b: res += 1 return res # 再帰関数 # 最初の i 個は確定した状態を考える def rec(S, i): # 文字列を使い切ったら true if i == len(S): return True; # まだ使っていない文字列を選ぶ for j in range(i, len(S)): if i == 0 or diff(S[i - 1], S[j]) == 1: S[i], S[j] = S[j], S[i] # S[j] を i 番目に持ってくる if rec(S, i + 1): return True S[i], S[j] = S[j], S[i] # 元に戻す return False N, M = map(int, input().split()) S = [input() for _ in range(N)] print("Yes" if rec(S, 0) else "No")
