順列、循環配列

前ポストの「点群をたどる順番」について、「全部の点を通る、全通りのたどり順」を考える場合、順列permutationを考える必要があります。pythonには順列や組合せcombinationを簡単に扱えるitertoolsというモジュールがあります。iron pythonでも同様です。これを使って「点群をたどる順番」について考えてみましょう。

from itertools import permutations

l = [0,1,2,3,4,]

combs = []
for comb in permutations(l):
    combs.append(list(comb))

for comb in combs:
    print comb

print len(combs)

[0, 1, 2, 3, 4]
[0, 1, 2, 4, 3]
[0, 1, 3, 2, 4]
[0, 1, 3, 4, 2]
[0, 1, 4, 2, 3]
[0, 1, 4, 3, 2]
[0, 2, 1, 3, 4]
[0, 2, 1, 4, 3]
[0, 2, 3, 1, 4]
[0, 2, 3, 4, 1]
[0, 2, 4, 1, 3]
[0, 2, 4, 3, 1]
[0, 3, 1, 2, 4]
[0, 3, 1, 4, 2]
[0, 3, 2, 1, 4]
[0, 3, 2, 4, 1]
[0, 3, 4, 1, 2]
[0, 3, 4, 2, 1]
[0, 4, 1, 2, 3]
[0, 4, 1, 3, 2]
[0, 4, 2, 1, 3]
[0, 4, 2, 3, 1]
[0, 4, 3, 1, 2]
[0, 4, 3, 2, 1]
[1, 0, 2, 3, 4]
[1, 0, 2, 4, 3]
[1, 0, 3, 2, 4]
[1, 0, 3, 4, 2]
[1, 0, 4, 2, 3]
[1, 0, 4, 3, 2]
[1, 2, 0, 3, 4]
[1, 2, 0, 4, 3]
[1, 2, 3, 0, 4]
[1, 2, 3, 4, 0]
[1, 2, 4, 0, 3]
[1, 2, 4, 3, 0]
[1, 3, 0, 2, 4]
[1, 3, 0, 4, 2]
[1, 3, 2, 0, 4]
[1, 3, 2, 4, 0]
[1, 3, 4, 0, 2]
[1, 3, 4, 2, 0]
[1, 4, 0, 2, 3]
[1, 4, 0, 3, 2]
[1, 4, 2, 0, 3]
[1, 4, 2, 3, 0]
[1, 4, 3, 0, 2]
[1, 4, 3, 2, 0]
[2, 0, 1, 3, 4]
[2, 0, 1, 4, 3]
[2, 0, 3, 1, 4]
[2, 0, 3, 4, 1]
[2, 0, 4, 1, 3]
[2, 0, 4, 3, 1]
[2, 1, 0, 3, 4]
[2, 1, 0, 4, 3]
[2, 1, 3, 0, 4]
[2, 1, 3, 4, 0]
[2, 1, 4, 0, 3]
[2, 1, 4, 3, 0]
[2, 3, 0, 1, 4]
[2, 3, 0, 4, 1]
[2, 3, 1, 0, 4]
[2, 3, 1, 4, 0]
[2, 3, 4, 0, 1]
[2, 3, 4, 1, 0]
[2, 4, 0, 1, 3]
[2, 4, 0, 3, 1]
[2, 4, 1, 0, 3]
[2, 4, 1, 3, 0]
[2, 4, 3, 0, 1]
[2, 4, 3, 1, 0]
[3, 0, 1, 2, 4]
[3, 0, 1, 4, 2]
[3, 0, 2, 1, 4]
[3, 0, 2, 4, 1]
[3, 0, 4, 1, 2]
[3, 0, 4, 2, 1]
[3, 1, 0, 2, 4]
[3, 1, 0, 4, 2]
[3, 1, 2, 0, 4]
[3, 1, 2, 4, 0]
[3, 1, 4, 0, 2]
[3, 1, 4, 2, 0]
[3, 2, 0, 1, 4]
[3, 2, 0, 4, 1]
[3, 2, 1, 0, 4]
[3, 2, 1, 4, 0]
[3, 2, 4, 0, 1]
[3, 2, 4, 1, 0]
[3, 4, 0, 1, 2]
[3, 4, 0, 2, 1]
[3, 4, 1, 0, 2]
[3, 4, 1, 2, 0]
[3, 4, 2, 0, 1]
[3, 4, 2, 1, 0]
[4, 0, 1, 2, 3]
[4, 0, 1, 3, 2]
[4, 0, 2, 1, 3]
[4, 0, 2, 3, 1]
[4, 0, 3, 1, 2]
[4, 0, 3, 2, 1]
[4, 1, 0, 2, 3]
[4, 1, 0, 3, 2]
[4, 1, 2, 0, 3]
[4, 1, 2, 3, 0]
[4, 1, 3, 0, 2]
[4, 1, 3, 2, 0]
[4, 2, 0, 1, 3]
[4, 2, 0, 3, 1]
[4, 2, 1, 0, 3]
[4, 2, 1, 3, 0]
[4, 2, 3, 0, 1]
[4, 2, 3, 1, 0]
[4, 3, 0, 1, 2]
[4, 3, 0, 2, 1]
[4, 3, 1, 0, 2]
[4, 3, 1, 2, 0]
[4, 3, 2, 0, 1]
[4, 3, 2, 1, 0]
120

リストl内の5つの整数を5つの点とすると、120通りのたどり方があるということになります。ただし、「始点に戻るループ、逆順も同じループ」のたどり方として考えるのならば、次の手順で調べられます。

  1. 上記の手順で全順列を求める
  2. 各tupleの順列配列をlistに変換
  3. 各listの順列配列の先頭がl[0]と同じになるまで、配列をシフトする
  4. 重複を削除
  5. 各listの逆順を作る
  6. 各listの順列配列の先頭がl[0]と同じになるまで、配列をシフトする
  7. 重複を削除
コードがきれいではありませんが(特にlistとtupleの変換が頻出します)、
from itertools import permutations

l = [0,1,2,3,4,]

combs = []
for comb in permutations(l):
    combs.append(list(comb))

for i in range(len(combs)):
    comb = combs[i]
    while comb[0] != l[0]:#shift the loop
        comb.insert(0,comb[-1])
        comb.pop()
    comb = tuple(comb)#convert to tuple
    combs[i] = comb

combs = list(set(combs))#remove duplication

combss = []
for i in range(len(combs)):
    comb = list(combs[i])
    comb = comb[::-1]#reverse
    combss.append(comb)

for i in range(len(combss)):
    comb = combss[i]
    while comb[0] != l[0]:#shift the loop
        comb.insert(0,comb[-1])
        comb.pop()
    comb = tuple(comb)#convert to tuple
    combss[i] = comb

ll = []
for i in range(len(combss)):
    ll.append([combss[i],combs[i],False])
    #print comb

for i in range(len(ll)):
    for ii in range(i+1,len(ll)):
        if(ll[i][0] == ll[ii][1]):
            ll[i][2] = True
#selection
combs = []
for comb in ll:
    if comb[2] == False:
        combs.append(comb[0])

for comb in combs:
    print comb
print len(combs)

(0, 3, 4, 2, 1)
(0, 4, 3, 1, 2)
(0, 3, 2, 4, 1)
(0, 2, 1, 4, 3)
(0, 4, 3, 2, 1)
(0, 4, 1, 2, 3)
(0, 2, 4, 3, 1)
(0, 3, 1, 2, 4)
(0, 1, 4, 3, 2)
(0, 4, 1, 3, 2)
(0, 3, 1, 4, 2)
(0, 4, 2, 3, 1)
12

5つの点のループは12通りということになります。
6つの点のループは60通りということになります。

まだ、、組合せの爆発が絞り切れず現実的な計算量ではないですね(汗)。

Comments are closed.