일부 고정 숫자가있는 순열

Question

특정 자리에서 일부 문자/숫자가 필요한 경우 숫자 (또는 단어의 문자)의 순열을 효과적으로 생성하는 방법은 무엇입니까?

예컨대 자릿수 3을 처음부터 두 번째 자리에 작성하고 자릿수 1 자릿수 끝에서 두 번째 자로 생성하십시오. 숫자의 각 숫자는 고유해야하며 숫자 1-5에서만 선택할 수 있습니다.

4 3 2 1 5 
4 3 5 1 2 
2 3 4 1 5 
2 3 5 1 4 
5 3 2 1 4 
5 3 4 1 2 

나는 next_permutation 기능이 알고, 그래서 난 숫자 배열을 준비 할 수 있습니다 {4, 2, 5}이 기능에 사이클이 게시하지만, 고정 된 위치를 처리하는 방법?

Answer 1

모든 순열을 2 4 5으로 생성하고 출력 루틴에 3과 1을 삽입하십시오. 단지는 위치가 그들이해야했다 기억 :

int perm[3] = {2, 4, 5}; 
const int N = sizeof(perm)/sizeof(int); 

std::map<int,int> fixed; // note: zero-indexed 
fixed[1] = 3; 
fixed[3] = 1; 

do { 
    for (int i=0, j=0; i<5; i++) 
     if (fixed.find(i) != fixed.end()) 
      std::cout << " " << fixed[i]; 
     else 
      std::cout << " " << perm[j++]; 
    std::cout << std::endl; 
} while (std::next_permutation(perm, perm + N)); 

출력

2 3 4 1 5 
2 3 5 1 4 
4 3 2 1 5 
4 3 5 1 2 
5 3 2 1 4 
5 3 4 1 2 

Answer 2

당신이 당신의 고정 번호를 원하는 배치하는 것을 기억하십시오. 배열에서 제거하십시오. 평소와 같이 순열을 생성하십시오. 모든 순열 후에 고정 숫자를 나타낼 위치에 삽입하고 출력합니다.

Answer 3

숫자가 {4,3,2,1,5}인데 3과 1이 순열되지 않는다는 것을 알고 있다면 세트에서 꺼내서 { 4, 2, 5}. 그 후에해야 할 일은 파워 세트의 각 세트에 대해 각각의 위치에 1을 삽입하는 것입니다.

나는 similar question을 게시했으며 거기에는 powerset 코드가 있습니다.

Answer 4

나는 다른 답변을 읽었으며 귀하의 특정 문제에 대해 그들이 나의 것보다 낫다고 믿습니다. 그러나 누군가가 귀하의 문제에 대한 일반화 된 솔루션을 필요로 할 경우를 대비하여 답변을 드리겠습니다.

최근에 3 개의 분리 된 연속 범위 [first1, last1) + [first2, last2) + [first3, last3]의 모든 순열을 생성해야했습니다. 이것은 세 개의 범위가 모두 길이 1이고 오직 하나의 요소로 분리 된 귀하의 경우에 해당합니다. 내 경우에 유일한 제한은 거리 (first3, last3)> = distance (first1, last1) + distance (first2, last2)입니다 (이것은 더 많은 계산 비용으로 완화 될 수 있습니다).

내 응용 프로그램은 각 고유 순열을 생성했지만 그 반대는 생성하지 않았습니다.

http://howardhinnant.github.io/combinations.html

그리고 특정 적용 기능 (조합을 생성하는) combine_discontinuous3이며, 순열을 생성 reversible_permutation :: 연산자()에서의 사용 : 코드는 여기에있다.

이것은 기성품 패키지 솔루션이 아닙니다. 그러나 문제의 일반화를 해결하는 데 사용할 수있는 도구 세트입니다. 다시 말하면, 당신의 정확한 간단한 문제에 대해, 나는 다른 사람들이 이미 제안한보다 간단한 솔루션을 추천한다.