1

長さ n のリストで長さ k の巡回シフトのすべての順列を生成するにはどうすればよいですか。ここで、シフトはサイクリックで右です。次の点に注意してください。

K==1 の場合、シフトはありません。したがって、これらの 0 シフトの順列はありません。
K==2 の場合、これは要素を交換することと同じです。したがって、すべて n! 順列を生成できます。

例えば。リストが [1 4 2] の場合、K=2 (したがって、0 から NK まで、ループ) 

P1: [1,4,2] #Original list. No shift.
P2: [4,1,2] #Shift from 0 of [1,4,2]
P3: [4,2,1] #Shift from 1 of [4,1,2] as 0 gives P1
P4: [2,4,1] #Shift from 0 of [4,2,1]  
P5: [2,1,4] #Shift from 1 of [1,4,2] as 0 of P4=P3
P6: [1,2,4] #Shift from 0 of [2,1,4]

K==3 の場合、いくつかの順列が除外されるため、興味深いものになります。

例えば。if list=[1,3,4,2],K=3 (したがって、インデックス 0 から 4-3 まで、ループ)

P1 : [1,3,4,2] #Original list. No shift. 
P2 : [4,1,3,2] #Shift from 0th of [1,3,4,2]  
P3 : [3,4,1,2] #Shift from 0th of [4,1,3,2]  
P4 : [3,2,4,1] #Shift from 1th of [3,4,1,2] as 0th gives P1
P5 : [4,3,2,1] #Shift from 0th of [3,2,4,1] 
P6 : [2,4,3,1] #Shift from 0th of [4,3,2,1] 
P7 : [2,1,4,3] #Shift from 1th of [2,4,3,1] as 0th gives P3
P8 : [4,2,1,3] #Shift from 0th of [2,1,4,3] 
P9 : [1,4,2,3] #Shift from 0th of [4,2,1,3] 
P10: [2,3,1,4] #Shift from 1th of [2,1,4,3] as 0 from P9=P7,1 from P9=P1,1 from P8=P5  
P11: [1,2,3,4] #Shift from 0th of [2,3,1,4] 
P12: [3,1,2,4] #Shift from 0th of [1,2,3,4] 

#Now,all have been generated, as moving further will lead to previously found values.

これらの順列は、本来あるべき (24) の半分 (12) であることに注意してください。 このアルゴリズムを実装するために、私は現在バックトラッキングを使用しています。これが私がこれまでに試したことです（Pythonで）

def get_possible_cyclic(P,N,K,stored_perms): #P is the original list
    from collections import deque  

    if P in stored_perms:
        return    #Backtracking to the previous

    stored_perms.append(P)

    for start in xrange(N-K+1):
        """
        Shifts cannot wrap around. Eg. 1,2,3,4 ,K=3
        Recur for  (1,2,3),4 or 1,(2,3,4) where () denotes the cycle
        """
        l0=P[:start]                    #Get all elements that are before cycle ranges
        l1=deque(P[start:K+start])      #Get the elements we want in cycle
        l1.rotate()                     #Form their cycle
        l2=P[K+start:]                  #Get all elements after cycle ranges

        l=l0+list(l1)+l2                #Form the required list
        get_possible_cyclic(l,N,K,stored_perms)

    for index,i in enumerate(stored_perms):    
        print i,index+1

get_possible_cyclic([1,3,4,2],4,3,[])
get_possible_cyclic([1,4,2],3,2,[])

これにより、出力が生成されます

[1, 3, 4, 2] 1
[4, 1, 3, 2] 2
[3, 4, 1, 2] 3
[3, 2, 4, 1] 4
[4, 3, 2, 1] 5
[2, 4, 3, 1] 6
[2, 1, 4, 3] 7
[4, 2, 1, 3] 8
[1, 4, 2, 3] 9
[2, 3, 1, 4] 10
[1, 2, 3, 4] 11
[3, 1 ,2, 4] 12

[1, 4, 2] 1
[4, 1, 2] 2
[4, 2, 1] 3
[2, 4, 1] 4
[2, 1, 4] 5
[1, 2, 4] 6

これはまさに私が望んでいるものですが、ここでは再帰の深さが N>7 を超えているため、はるかに遅くなります。私は自分自身を明確に説明したことを願っています。最適化を行っている人はいますか?

4

1 に答える 1

1

小切手

if P in stored_perms:

コピーが見つかるか、リストの最後に到達するまで、一度に 1 つの要素stored_permsと比較する必要があるため、成長するにつれてますます遅くなります。すべての順列が 1 回に追加されるため、 との比較の数は、見つかった順列の数の少なくとも 2 次であり、一般に、k が偶数か奇数かによって (1 < k < N)。Pstored_permsstored_permsP

setを使用する方がはるかに効率的です。Python のセットはハッシュ テーブルに基づいているため、メンバーシップ チェックは通常 O(N) ではなく O(1) です。ただし、いくつかの制限があります。

  1. セットに追加される要素はhashableである必要があり、Python リストは hashable ではありません。幸いなことに、タプルはハッシュ可能であるため、小さな変更で問題が修正されます。

  2. セットの反復は予測できません。特に、反復処理中にセットを確実に変更することはできません。

P をタプルに変更し、stored_perms をセットに変更することに加えて、再帰的な検索ではなく、ワークキューに基づく検索を検討する価値があります。高速になるかどうかはわかりませんが、再帰の深さに関する問題は回避されます。

以上をまとめると、以下のようになりました。

def get_cyclics(p, k):
  found = set()      # set of tuples we have seen so far
  todo = [tuple(p)]  # list of tuples we still need to explore
  n = len(p)
  while todo:
    x = todo.pop()
    for i in range(n - k + 1):
      perm = ( x[:i]                    # Prefix
             + x[i+1:i+k] + x[i:i+1]    # Rotated middle
             + x[i+k:]                  # Suffix
             )
      if perm not in found:
        found.add(perm)
        todo.append(perm)
  for x in found:
    print(x)
于 2015-10-05T21:10:06.813 に答える