基準による集合の再帰的割り当て

Question

私は再帰的割り当ての問題の周りに頭を抱えようとしています。
基本的に、集合Aの各要素について、集合Bから要素を割り当てようとしています。ここで、| A | < = | B |。
Bの要素は、Aからの1つの要素にのみ割り当てられ、「安全」基準を満たす場合にのみ割り当てられます。
Pythonでこの問題のより小さなバージョンを（より簡単な安全性チェックで）処理すると、以下のようになります。f（A、B）は、Bのセットを割り当てようとすると

A = ["A0","A1","A2"] 
B = ["B0","B1","B2","B3"] 

def issafe(a,b): 
    return int(a[1]) <= int(b[1]) 

def f(A,B): 
    if A == []: 
     return [] 
    else: 
     for i in range(len(B)): 
      if issafe(A[0],B[i]): 
       return [(A[0],B[i])] + f(A[1:],B[0:i]+B[i+1:]) 

だから、最初のセットでのに対するBさんのから安全割り当てがある

f(A,B) 
=> [('A0', 'B0'), ('A1', 'B1'), ('A2', 'B2')] 

を機能を実行しています。しかし、1つの可能な安全配分だけです。
私は、このソリューションをどのように拡張してすべての安全な割り当てを提供するかについて、誰かに私に助言を与えることができると考えていました。

ので

プルーンのコメントどおり変化作る

f(A,B) 
=> [[('A0', 'B0'), ('A1', 'B1'), ('A2', 'B2')], 
    [('A0', 'B1'), ('A1', 'B2'), ('A2', 'B3')], 
    [     ...     ]] 

---

のようなもの：これはツリー構造の出力を与える

def f(A,B): 
    C = [] 
    if A == []: 
     return [] 
    else: 
     for i in range(len(B)): 
      if issafe(A[0],B[i]): 
       C.append([(A[0],B[i])] + f(A[1:],B[0:i]+B[i+1:])) 
    return C 

を：

私はあると信じて

[ 
[('A0', 'B0'),[('A1', 'B1'), [('A2', 'B2')], [('A2', 'B3')]], [('A1', 'B2'), [('A2', 'B3')]], [('A1', 'B3'), [('A2', 'B2')]]], 
[('A0', 'B1'), [('A1', 'B2'), [('A2', 'B3')]], [('A1', 'B3'), [('A2', 'B2')]]], 
[('A0', 'B2'), [('A1', 'B1'), [('A2', 'B3')]], [('A1', 'B3')]], 
[('A0', 'B3'), [('A1', 'B1'), [('A2', 'B2')]], [('A1', 'B2')]] 
] 

正しい、しかし私はまだsurではないもし安全な割り当ての集合そのものをツリーに並べる方法があれば、

Answer 1

私がやったことは、今まで割り当てられていたものを格納するための入力と、保存されたsolnを格納するための入力を追加したことです。私は、終了条件に達したときに、私は、言い換えればこれは私が後だった溶液を得て、私の知る限り、任意のセットのために働くだろう

def f(A,B,Assigned = [],Soln = []): 
C = [] 
#If we've assigned all A's 
if A == []: 
    #Add this assignment list to soln list 
    Soln.append(Assigned) 
    #Return blank to stop recursion 
    return ([],Soln) 
else: 
    for i in range(len(B)): 
     #For unassigned safe B's 
     if issafe(A[0],B[i]): 
      C.append( [(A[0],B[i])]    #Newly assigned pair 
         + [f(A[1:], B[0:i] + B[i+1:], #Remainder to be assigned 
         Assigned + [(A[0],B[i])], #Update assigned list 
         Soln)[0]])     #'Transfer' soln to next itteration 
return (C,Soln) 

Ans = f(AInit,BInit)[1] 

for a in Ans: 
    print (a) 

で、SOLNに割り当てられたペアを保存しますAさんとBさんと様々な安全confitions

[('A0', 'B0'), ('A1', 'B1'), ('A2', 'B2')] 
[('A0', 'B0'), ('A1', 'B1'), ('A2', 'B3')] 
[('A0', 'B0'), ('A1', 'B2'), ('A2', 'B3')] 
[('A0', 'B0'), ('A1', 'B3'), ('A2', 'B2')] 
[('A0', 'B1'), ('A1', 'B2'), ('A2', 'B3')] 
[('A0', 'B1'), ('A1', 'B3'), ('A2', 'B2')] 
[('A0', 'B2'), ('A1', 'B1'), ('A2', 'B3')] 
[('A0', 'B3'), ('A1', 'B1'), ('A2', 'B2')] 

感謝の

Answer 2

典型的なアプローチは再帰的です。

• ベースケース：与えられたコールに AまたはBのどちらかが空の場合、完了です。戻る。

• 再帰場合：Aの最初の要素について

  • は、順番にBの各要素（すなわちためループ）を試みます。ペアリングが合法であれば、残りのリストを再現します。
  • すべての成功した割り当てを連結/追加し、それを次のレベルまで上げます。

んソリューションに向かってあなたを移動していますか？

Answer 3

これは、リストの作成と連結が非常に迅速に支配されることに注目する価値があります。イテレータは、これに対処するための良い方法、例えば：私はタプルとジッパーを使用

def allsafe(x, y): 
     if not x: 
      yield() 
     else: 
      v_x = x[0] 
      remaining = x[1:] 
      for i, v_y in enumerate(y): 
       if not issafe(v_x, v_y): 
        continue 
       point = (v_y,) 
       if remaining: 
        for solution in allsafe(remaining, y[:i]): 
         yield point + solution 
        for solution in allsafe(remaining, y[i+1:]): 
         yield point + solution 
       else: 
        yield point 

def test(): 
    a = ["A%d" % i for i in xrange(6)] 
    b = ["B%d" % i for i in xrange(30)] 
    for b_solution in allsafe(a, b): 
     # Don't print with large a/b sizes if you value your terminal history 
     print 'solution: %s' % zip(a, list(b_solution)) 

注だろうが、彼らはあまり重要ではないん。これは、与えられたサイズ（|A|=6、|B|=30）に対して〜15倍速く、6倍、32倍、6倍、35倍などの速度が約20倍速くなります。