두 세트 간의 가능한 모든 bijection 찾기

Question

내가하고 싶은 것은 두 세트의 오브젝트 사이에 가능한 모든 bijection을 찾을 수있는 알고리즘을 만드는 것입니다.

간단한 예를 들어 두 개의 배열 {1,2,3} {4,5,6}이 있다고 가정 해 봅시다.

알고리즘 날 (3)을 수득한다 = 다음되어 3 * 2 * 1 = 6 bijections!

1-4 2-5 3-6 \ 1-4 2-6 3-5 \ 1-5 2-4 3-6 \ 1-5 2-6 3-4 \ 1-6 2-5 3-4 \ 1-6 2-4 3-5 \

비록 그것은 처음부터 단순 해 보인다, 나는 아주 붙어있다. combinatorics, bijections 또는 permutations의 이론에이 문제를 해결하기위한 표준 알고리즘이 있습니까? 미리 감사드립니다. 및 솔루션에 추가 - -

크리스티나는

Answer 1

당신은 재귀, "선택"에서 각각 하나 개의 변수 해야 모든 가능성을 위해 그것을 할, 각 재귀 호출에 당신의 가능한 선택 범위를 좁힐.

가짜 코드는 [가정 | S1 | == | S2 |] :

getAllBijections(S1,S2,sol): 
    if (S1 is empty): 
     print sol 
    else: 
     first <- S1.first 
     S1 <- S1.deleteFirst() 
     for each e in S2: 
      S2.remove(e) 
      sol.append(first,e) 
      getAllBijections(S1,S2,sol) // note we are invoking with modified S1,S2,sol 
      sol.removeLast() //remove the last sol 
      S2.add(e) //return e to S2 
     end for 
    end if 

가 실제로 n! 가능성을 생성 있습니다 각각의 반복에 대해 당신이 ... 예상대로 n * (n-1) * ... * 1 = n! 가능성의 총 결과에서

을 선택하는 하나 개의 작은 요소를 가지고 있기 때문에

Answer 2

combinatorics, bijections 또는 permutations의 이론에이 문제를 해결하기위한 표준 알고리즘이 있습니까?

예! N 요소의 두 세트 사이에서 모든 bijection을 생성하는 것은 N 요소의 모든 순열을 생성하는 것과 같습니다. 순열을 첫 번째 집합의 각 요소에 대해 두 번째 집합의 어떤 요소가 bijection 하에서의 이미지가 될 것임을 나타내는 것으로 생각하십시오. 따라서 "모든 순열 생성"알고리즘을 찾고 있습니다.

크 누스 (Knuth)는 주제에 대해 book이라는 짧은 문자가 있습니다.이 파일은 무료로 다운로드 할 수도 있습니다 : "The Art of Computer Programming: Generating all Permutations"(참고 : 압축 된 포스트 스크립트 형식). 그가 제시 한 첫 번째 알고리즘은 명백한 재귀 알고리즘에 대한 흥미로운 대안 인 "알고리즘 L"입니다.

"Algorithms to generate permutations"에 대한 위키 백과 토론은 당신에게 흥미로울 것입니다. C++로 프로그래밍하는 경우 next_permutation 함수에서 구현을 사용할 수 있습니다.

(물론, 이것은 당신이 x ⟼ x+1처럼, 말의 실수의 bijections 약 셀 수 세트 이야기, 그리고 가정합니다.)

Answer 3

이 문제가 단순히 모든 순열을하는 것입니다 단순화 할 수있는 방법을 제 1 어레이와 치환 된 각각의 제 2 어레이 사이에서 n- 대 -n 매핑을 수행 할 수있다.

예를 들어 [1,2]와 [3,4]가있는 경우 먼저 [3,4] -> [[3,4], [4,3]}의 순열을 계산 한 다음 각각 [1,2]와 쌍을 이룬다. 결과는 {[(1,3), (2,4)], [(1,4), (2,3)]}입니다.

아래의 Python 예제 구현을 포함했습니다.

import itertools 
a = [1,2] 
b = [3,4] 

for p in itertools.permutations(b): 
    print zip(a,p) 

# Output: 
# [(1, 3), (2, 4)] 
# [(1, 4), (2, 3)]