추가 제한 사항을 사용하여 임의의 다중 세트 순열을 효과적으로 생성하는 방법은 알려진 알고리즘이 있습니까?제한이있는 임의의 다중 세트 순열 생성
예 : I는 예를 들어 항목 MULTISET 가질 예 : {1,1,1,2,2,3,3,3} 한 세트의 제한 세트 {{3}, {1,2}, {1,2,3}, {1,2,3}, {1,2,3}, {1,2,3}, {2,3}, {2,3}}. 나는 항목의 순열을 찾고,하지만 첫 번째 요소는 3이어야하며, 두 번째는 1 또는 2 인 제한을 맞는 등
그러한 치환해야합니다 : {3,1,1,1,2,2,3,3}이
예, 있습니다. 나는 this German forum에서 물었고 다음과 같은 대답을 얻었습니다 : 문제는 a maximum matching on a bipartite graph을 찾는 것으로 줄일 수 있습니다. 이렇게하려면 멀티 세트의 모든 요소에 대한 정점을 도입하십시오. 이 꼭지점은 이분 그래프의 한면을 형성합니다. 그런 다음 각 제한 집합에 대해 정점을 도입하십시오. 이 정점들은 이분 그래프의 다른면을 형성합니다. 이제 각 제한 세트의 가장자리를 첫 번째면의 꼭지점으로 가져와 첫 번째면의 꼭지점이 연결된 세트에 포함 된 요소를 나타내는 경우에만 "맞춰집니다".
하여 예 이분 그래프는 다음과 같을 것이다 : 는 
이제 매칭은 두 개의 인접하는 에지가 선택되지 않도록하는 방식으로 에지를 선택한다. 예 : 두 번째 제한 "{1,2}"에 대해 첫 번째 "1"이 선택되면 더 이상 다른 제한에 사용할 수 없습니다.이 꼭지점에서 다른 가장자리를 사용하면 더 이상 일치하지 않으므로 더 이상 사용할 수 없습니다.
다른 질문이 있으시면 언제든지 문의하십시오.