Atcoder水色への精選 100 問 全探索：順列全探索(Python)

水色になるための精選100問、
今回は15~17までの「全探索：順列全探索」です

qiita.com

前回↓
ビット全探索
algo-archit.hatenablog.com

目次

15　AtCoder Beginner Contest 145 C - Average Length

問題文
atcoder.jp

座標群を並び替え、どの順番で行くかの順列を全探索すればOKです
距離の計算だけ注意です

pythonでの実装例

from itertools import permutations
import math

n = int(input())
li = [tuple(map(int,input().split())) for _ in range(n)]

# 2点間の距離
def length(x1,y1,x2,y2):
    return(math.sqrt(abs(x2-x1)**2+abs(y2-y1)**2))

point = 0

for i in permutations(li):
    for j in range(1,n):
        point += length(i[j-1][0],i[j-1][1],i[j][0],i[j][1])

print(point/math.factorial(n))

16　AtCoder Beginner Contest 150 C - Count Order

問題文
atcoder.jp

並び替えられたリストから、何番目に出てくるかを調べる問題です
こういった時、pythonのitertools関数のpermutationを使うとリストの順列を簡単に生成できるので便利です

for i , j enumerate( list ) の形でリストのインデックスと中身を同時に取り出すことができます
（python辞書型のitemsのようなもの）

pythonでの実装例

from itertools import permutations

n = int(input())
li = [i for i in range(1,n+1)]
p = tuple(map(int,input().split()))
q = tuple(map(int,input().split()))

# pとqが何番目に出てくるかを記録
for i,j in enumerate(permutations(li)):
    if j == p:
        num_p = i
    if j == q:
        num_q = i

print(abs(num_p-num_q))

17　ALDS_13_A - 8 クイーン問題

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A

8×8マスのうちどの８マスにコマを置くかを全通り考えてしまうと
通りもあるので間に合いそうもありません

そこで正解となる置き方において、どの行でもクイーンの個数は１個しかないことに注目します
そのような行の並べ方は８個存在するので、それをどの順番で積み重ねていくかを全探索です

次に、生成された盤面が、先に与えられるK個のコマの配置と一致しているかを考えます

その後、縦方向と横方向にクイーンが被ることはないので、残り斜め方向の被りがないかだけチェックします
チェックにはいろいろ方法がありそうですが私は「右上（左上）からの距離が等しいマスにクイーンは2つ以上存在しない」という条件で探索しました

以下は４×４マスの例です
これで斜め方向にクイーンが２個以上存在するかを調べることができます

右下斜め方向、左下斜め方向が条件を満たすような盤面は１つに限られるのでそれを出力します

pythonでの実装例

from itertools import permutations

n = int(input())
li = [list(map(int,input().split())) for _ in range(n)]
chess = [["." for i in range(8)]for j in range(8)]

for i in range(8):
    chess[i][i] = "Q"

# 行のchessの並べ方を探索
for patern in permutations(chess):
    for y,x in li:
        if patern[y][x] != "Q":
            break
    else:
        rd = [0]*15 # i+jの合計を記録（右下斜め方向）
        ld = [0]*15 # 7-i+jの合計を記録（左下斜め方向）
        for i in range(8):
            for j in range(8):
                if patern[i][j] == "Q":
                    rd[i+j] += 1
                    ld[i+(7-j)] += 1
        for k in range(15):
            # 各斜め方向には１つまでしかQがあってはならない
            if rd[k] > 1 or ld[k] > 1:
                break
        else:
            for l in patern:
                print("".join(l))

↓次回　二分探索
algo-archit.hatenablog.com