順列の問題はitertoolsを使いたおす

今回は順列の問題を解きました。
問題をざっくりというと、N個の街があって、全部の町を巡回します。
巡回する順番は無数にありますが、それらの全てのパターンの距離の平均値を求める問題です。

atcoder.jp

方針としてはNは2〜8なので、街の順番の配列の全パターンを考えても通り。
そこから移動距離を求めるのは通り。
なので、計算量は大丈夫そう。
街の順番の配列を生成して、その配列の要素ごとに移動距離を求めて、最後に割り算ををします。

街の順番の配列の全パターンを作るのは順列を作ることになるので、迷わずitertools.permutationを使いました。
練習になってない気がしてしまいますが。。。

docs.python.org

itertoolsはかなり便利で、iterableな配列を引数に渡すと、permutations（順列）だけでなくcombinations（組み合わせ）、accumulate（累積和）の配列を返してくれます。

from itertools import permutations
lst = [1, 2, 3]
list(permutations(lst))
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

permutationのおかげですんなりと問題が解けました。

from itertools import permutations
from math import sqrt
N = int(input())
towns = []
for _ in range(N):
    x, y = [int(i) for i in input().split()]
    towns.append((x, y))
towns_distance = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        towns_distance[i][j] = sqrt((towns[i][0] - towns[j][0])**2 + (towns[i][1] - towns[j][1])**2)
patterns = list(permutations([i for i in range(N)]))
total = 0
for m in patterns:
    for i in range(N-1):
        total += towns_distance[m[i]][m[i+1]]
print(round(total/len(patterns), 10))

街の間の距離を事前に配列にメモしましたが、あまり意味なかったかも。