3

3x3 グリッドを想像してください:

[A, B, %]
[C, %, D]
[E, F, G]

パーセンテージ%は、空きスペース/位置を表します。

行は、最初の行の構成の順列が次のいずれかになるように、文字列のビーズのように移動できます。

[A, B, %] or [A, %, B] or [%, A, B]

2行目も同様。3 番目の行には空のスロットが含まれていないため、変更できません。

各行の可能な順列を考慮して、可能なすべてのグリッドを作成しようとしています。

出力は次のグリッドを生成する必要があります。

[A, B, %]    [A, B, %]    [A, B, %]
[C, D, %]    [C, %, D]    [%, C, D]
[E, F, G]    [E, F, G]    [E, F, G]

[A, %, B]    [A, %, B]    [A, %, B]
[C, D, %]    [C, %, D]    [%, C, D]
[E, F, G]    [E, F, G]    [E, F, G]

[%, A, B]    [%, A, B]    [%, A, B]
[C, D, %]    [C, %, D]    [%, C, D]
[E, F, G]    [E, F, G]    [E, F, G]

各行を調べてスペースを左右にシフトし、それから新しいグリッドを生成して再帰する方法を試しました。すべてのグリッドをセットに保持し、無限再帰を防ぐために、まだ調査されていない位置のみを生成するようにします。

ただし、私のアルゴリズムは非常に非効率的 (順列ごとに ~1 秒!!) のようで、見栄えもよくありません。これを行う雄弁な方法があるかどうか疑問に思っていましたか？特にパイソンでは。

私には漠然としたアイデアがいくつかありますが、見落としている短くて簡単な方法があると確信しています。

編集: 3x3 は単なる例です。グリッドは任意のサイズにすることができ、重要なのは行の組み合わせです。例えば：

[A, %, C]
[D, E, %, G]
[H, I]

も有効なグリッドです。

編集 2:文字は順序を維持する必要があります。たとえば[A, %, B] != [B, %, A]、[B, A, %]有効ではありません

4

4 に答える 4

2

まず、各行に必要なすべての順列を取得する必要があります。次に、すべてのラインの外積を計算します。

行の順列は、文字[A、B、％]を持ち、開始インデックスを変更することで簡単に計算できます。

import itertools
# Example: line = ['A','B','%']
def line_permutations(line):
   if '%' not in line:
       return [line]
   line.remove('%') # use copy.copy if you don't want to modify your matrix here
   return (line[:i] + ['%'] + line[i:] for i in range(len(line) + 1))

クロス積は、itertools.productを使用して実現するのが最も簡単です。

matrix = [['A','B','%'], ['C', '%', 'D'], ['E', 'F', 'G']]
permutations = itertools.product(*[line_permutations(line) for line in matrix])
for p in permutations:
    print(p)

このソリューションは、順列が再計算されないため、メモリとCPUの要件に最適です。

出力例：

(['%', 'A', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['C', 'D', '%'], ['E', 'F', 'G'])
(['A', '%', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G'])
(['A', '%', 'B'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['A', '%', 'B'], ['C', 'D', '%'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['%', 'C', 'D'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['C', 'D', '%'], ['E', 'F', 'G'])
于 2012-04-08T15:15:07.803 に答える
1

サイクルと呼ばれる関数を定義します

>>> def cycle(lst):
    while True:
        lst=lst[1:]+lst[0:1] if '%' in lst else lst
        yield lst
  • イテレータが与えられると、これは周期的な左シフトを生成して返します。
  • 次に、グリッド内の各行をサイクルジェネレーターに渡して、行の長さに一致する合計反復を行う必要があります。
  • 次に、itertools.productを使用して、生成された行の循環的な組み合わせのすべての組み合わせを検索します。
  • 空のスロットがない場合、サイクル順列は生成されません

最終結果は次のとおりです。

>>> for g in list(itertools.product(*[[x for (x,y) in zip(cycle(row),
           range(0,len(row) if '%' in row else 1))] for row in grid])):
    for r in g:
        print r
    print "="*10

グリッドの場合、これにより生成されます

['B', '%', 'A']
['%', 'D', 'C']
['E', 'F', 'G']
===============
['B', '%', 'A']
['D', 'C', '%']
['E', 'F', 'G']
===============
['B', '%', 'A']
['C', '%', 'D']
['E', 'F', 'G']
===============
['%', 'A', 'B']
['%', 'D', 'C']
['E', 'F', 'G']
===============
['%', 'A', 'B']
['D', 'C', '%']
['E', 'F', 'G']
===============
['%', 'A', 'B']
['C', '%', 'D']
['E', 'F', 'G']
===============
['A', 'B', '%']
['%', 'D', 'C']
['E', 'F', 'G']
===============
['A', 'B', '%']
['D', 'C', '%']
['E', 'F', 'G']
===============
['A', 'B', '%']
['C', '%', 'D']
['E', 'F', 'G']
===============
于 2012-04-08T15:17:56.347 に答える
0

素朴な実装：

g=[['A', 'B', '%'],
['C', '%', 'D'],
['E', 'F', 'G']]

from collections import deque
from itertools import product

def rotations(it):
    d = deque(it,len(it))
    for i in xrange(len(it)):
         d.rotate(1)
         yield list(d)

for i in product(*[rotations(x) if '%' in x else [x] for x in g]):
    print i

与える：

(['%', 'A', 'B'], ['D', 'C', '%'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['%', 'D', 'C'], ['E', 'F', 'G'])
(['%', 'A', 'B'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['B', '%', 'A'], ['D', 'C', '%'], ['E', 'F', 'G'])
(['B', '%', 'A'], ['%', 'D', 'C'], ['E', 'F', 'G'])
(['B', '%', 'A'], ['C', '%', 'D'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['D', 'C', '%'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['%', 'D', 'C'], ['E', 'F', 'G'])
(['A', 'B', '%'], ['C', '%', 'D'], ['E', 'F', 'G'])
于 2012-04-08T15:19:11.703 に答える
0

ここにあります。一方では、このアプローチはあまりクリーンではありませんが、＃len（matrix [0]）-1の順列を1回だけ計算し、それらを出力のテンプレートとして使用できることに注意してください。

from itertools import permutations,product

def charPermutation(matrix):
    permutation_list=list(permutations(["%%"]+["%s"]*(len(matrix[0])-1))) #Compute once, use infinitely
    perms={i:[] for i in range(len(matrix))}
    for it,line in enumerate(matrix):
        chars=list(set(line)-set(["%"]))
        if sorted(line)==sorted(chars):
            perms[it]+=["".join([str(i) for i in line])]
        else:
            for p in permutation_list:
                perms[it]+=["".join(["".join(p) % tuple(chars)])]
        perms[it]=list(set(perms[it]))
    return product(*[[list(k) for k in i] for i in perms.values()]) 

g=[
   ["A", "B", "%"],
   ["C", "%", "D"],
   ["E", "F", "G"]]

for x in charPermutation(g):
    print [i for i in x]

[['A', '%', 'B'], ['C', 'D', '%'], ['E', 'F', 'G']]
[['A', '%', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G']]
[['A', '%', 'B'], ['C', '%', 'D'], ['E', 'F', 'G']]
[['%', 'A', 'B'], ['C', 'D', '%'], ['E', 'F', 'G']]
[['%', 'A', 'B'], ['%', 'C', 'D'], ['E', 'F', 'G']]
[['%', 'A', 'B'], ['C', '%', 'D'], ['E', 'F', 'G']]
[['A', 'B', '%'], ['C', 'D', '%'], ['E', 'F', 'G']]
[['A', 'B', '%'], ['%', 'C', 'D'], ['E', 'F', 'G']]
[['A', 'B', '%'], ['C', '%', 'D'], ['E', 'F', 'G']]
于 2012-04-08T15:19:59.967 に答える