여러 요소를 사용하여 계산 순열

나는 요소 집합의 모든 가능한 순열을 생성하려고합니다. 순서는 중요하지 않으며 요소는 여러 번 나타날 수 있습니다. 각 순열의 요소 수는 요소의 총 수와 같습니다.여러 요소를 사용하여 계산 순열

스키마 다음 계산 순열에 대한 기본적인 재귀 알고리즘 (I는 C++에 쓰고 같이 코드가 유사합니다) :

elems = [0, 1, .., n-1]; // n unique elements. numbers only exemplary. 
current = [];    // array of size n 
perms(elems, current, 0); // initial call 

perms(array elems, array current, int depth) { 
    if(depth == elems.size) print current; 
    else { 
     for(elem : elems) { 
      current[depth] = elem; 
      perms(elems, current, depth+1); 
     } 
    } 
}

중복 시퀀스 많은 수의, 예를 생산겠습니까 :

를

0, 0, .., 0, 0 
0, 0, .., 0, 1 // this 
0, 0, .., 0, 2 
. . . . . 
. . . . . 
0, 0, .., 0, n-1 
0, 0, .., 1, 0 // is the same as this 
. . . . . // many more redundant ones to follow

정확한 생성 값을 건너 뛸 수 있지만 지금까지 아무 유용한 것도 발견하지 못했습니다. 나는이 문제를 해킹 할 수있는 방법을 찾을 수있을 것이라고 확신하지만, 나는 또한 볼 수 없었던 이것의 뒤에 규칙이 있다는 것도 확신한다.

편집 : 가능한 솔루션은

elems = [0, 1, .., n-1];  // n unique elements. numbers only exemplary. 
current = [];     // array of size n 
perms(elems, current, 0, 0); // initial call 

perms(array elems, array current, int depth, int minimum) { 
    if(depth == elems.size) print current; 
    else { 
     for(int i=minimum; i<elems.size; i++) { 
      current[depth] = elems[i]; 
      perms(elems, current, depth+1, i); 
     } 
    } 
}

출처

2014-10-23 Arne

'std :: next_permutation()'을 사용할 수 있습니까? – Barry

나는 그런 함수가 존재하는지 몰랐다. 나는 그것을 조사 할 것이다 – Arne

내가 이해하는 방식으로, next_permutation은 현재 요소를 "다음 순열"로 재정렬 할 것이다. 내 경우에는 명령이 부적절하므로 작동하지 않습니다. – Arne

첫 번째 위치는 0에서 n까지 다양합니다. 그런 다음 두 번째 위치를 1로 만듭니다. 그런 다음 첫 번째 위치를 1에서 n까지 변경합니다. 그런 다음 2에서 2로 설정 -> 먼저 2에서 n으로.

출처

2014-10-24 00:02:10

당신의 제안을 포함하도록 알고리즘을 업데이트하려고합니다. 만약 그것이 당신이 그것을 의미하는 방식이라면, 나는 매우 감사 할 것입니다. – Arne

하나 이상의 0이있는 순서를 제외하지 않습니까? –

알고리즘은 실제 솔루션을 빌드하기 전에 중지 시퀀스가 트리거 될 때까지 모든 노드를 확장합니다.이 시점에서 마지막 호출 인스턴스로 역 추적되어 작동합니다. – Arne

나는 하나의 규칙이 (당신이 선호하는 경우, 또는 비 증가) 순서를 감소 비는 될 각 시퀀스의 요소를 가지고있다 생각 +.

출처

2014-10-23 23:58:10

여러 요소를 사용하여 계산 순열

답변

관련 문제