円順列
いきなりですが、問題です。a,b,c,d,eの5人が円卓に座るとき、座り方の総数は何通りか。
正解は、(5-1)!=24通りです！
さすがQiitaを見ている方というだけあって、余裕という感じですね。
それでは、次の問題です。次の二つの並び方AとBは円形に並べた時同じ並びになるでしょうか！？
A： d, b, a, e, c
B： e, c, d, b, a
これは、同じ並びになります。どちらもaを基準に考えると、a→e→c→d→bの並びになっています。
今回はこの判定をプログラムで実装してみます。
円順列で考えた時に同一の並びになるかを判定する
まず、2つの配列array_aとarray_bを用意します。
array_a = ["d", "b", "a", "e", "c"]
array_b = ["e", "c", "d", "b", "a"]
array_aは変更せず、array_bの要素を回転させてみます。つまり、最初の要素を取り除いて、最後に追加します。
array_b = ["e", "c", "d", "b", "a"]
popped_element = array_b.pop(0) #array_bの0番目の要素を取り除いて値を変数に代入
array_b.append(popped_element) #取り除いた要素を配列の最後に追加
print(array_b) #実行結果['c', 'd', 'b', 'a', 'e']
この操作を配列の要素の数だけ繰り返して、array_aとarray_bが一致するかどうかを判定しましょう。
一致したら"same!"と表示して繰り返し処理を停止し、最後まで一致しなければ"different"と表示します。
array_a = ["d", "b", "a", "e", "c"]
array_b = ["e", "c", "d", "b", "a"]
for i in range(len(array_b)):
popped_element = array_b.pop(0)
array_b.append(popped_element)
if array_a == array_b:
print("same!")
break
if i == len(array_b) - 1:
print("different")
# 出力結果：same!
最後に、配列を2つ受け取り、その2つの配列が円順列で同じ並びになるかを判定するメソッドを定義して出力部分と切り分けます。
def check_circular_permutation_equal(array_a, array_b):
for i in range(len(array_b)):
popped_element = array_b.pop(0)
array_b.append(popped_element)
if array_a == array_b:
return True
if i == len(array_b) - 1:
return False
array_a = ["d", "b", "a", "e", "c"]
array_b = ["a", "e", "c", "b", "d"]
if check_circular_permutation_equal(array_a, array_b):
print("same!")
else:
print("different")
いくつか実験してみました。
array_a = ["e", "f", "a", "c", "d", "b"]
array_b = ["c", "d", "b", "e", "f", "a"]
# 実行結果：same!
array_a = ["c", "f", "b", "d", "a", "e"]
array_b = ["e", "c", "f", "d", "b", "a"]
# 実行結果：different
array_a = ["a", "c", "e", "g", "b", "d", "f"]
array_b = ["e", "g", "b", "d", "f", "a", "c"]
# 実行結果：same!
まとめ
- いくつかのものを円形に並べる方法のことを円順列と言う。 円順列では回転して一致する並べ方は同じと考える。
- 配列の一番最初の要素をpopメソッドで取り出し、その要素をappendメソッドで最後に加えることで、配列を「回転」させることができる。
- 配列の「回転」をfor文で繰り返し処理することによって、2つの配列が円順列で考えた時に一致するか否かを判定することができる。