기준에 의한 집합의 재귀 할당

Question

그래서 재귀 할당 문제를 해결하려고합니다.
기본적으로 집합 A의 각 요소에 대해 집합 B의 요소를 할당하려고합니다. 여기서 | A | < = | B |.
B의 요소는 A의 한 요소에만 '안전'기준을 충족하는 경우에만 할당 할 수 있습니다.
파이썬에서이 문제의 더 작은 버전을 (훨씬 더 간단한 안전 검사로) 처리하면 다음과 같은 결과를 얻을 수 있습니다. 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')] 

을 기능을 실행할 수 있습니다. 그러나 단 하나의 안전한 할당 만 가능합니다.
누군가가 나에게이 솔루션을 확장하여 모든 안전한 할당을 제공하는 방법에 대한 지침을 줄 수 있기를 바랍니다.

그래서 자두의 의견에 따라 변경 만들기

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')]] 
] 

인을 맞아,하지만 난 아직 쉬지 않아. e 안전한 할당 그 자체를 트리에 apposed하게 만드는 메소드가 있다면.

Answer 1

그래서 내가 한 일은 지금까지 할당 된 내용을 저장하고 저장된 soles를 저장하는 입력을 함수에 추가 한 것입니다. 내가 최종 상태에 도달 할 때 그럼, 즉이 난 후였다 솔루션을 산출하고, 내가 아는 한, 어떤 설정을 위해 일 것

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, 35, 6, 32, ~ 25 배 빠릅니다.