algorithm - 중복 - next_permutation 함수




벡터의 순열 (2)

예. 가장 왼쪽의 위치부터 시작하여, 그 위치 i에서 (다른) 잘못 배치 된 요소와 바꿔서 올바른 위치 i에 요소를 놓습니다. 여기서 우리는 O (1) 추가 공간이 필요합니다. 이 위치에있는 요소가 올 때까지 요소 쌍을 서로 바꿔 놓습니다. 그런 다음에야 다음 단계로 나아가고 똑같은 일을합니다.

예:

[5 3 2 1 0 4] 초기 상태

[4 3 2 1 0 5] 교환 (5,4), 5는 올바른 위치에 있지만 4는 여전히 잘못되었습니다.

[0 3 2 1 4 5] swapped (4,0), 이제 4와 0 모두 올바른 위치에 있고, 다음 위치로 이동합니다.

[0 1 2 3 4 5] swapped (3,1), 이제 1과 3이 모두 올바른 위치에 있고, 다음 위치로 이동합니다.

[0 1 2 3 4 5] 모든 요소가 올바른 위치에 있습니다.

참고 :

각 스왑 연산은 적어도 두 개 요소 중 하나를 올바른 위치에 배치하므로 N 개 이상의 스왑을 모두 필요로합니다.

내가 벡터를 가지고 있다고 가정 해보자.

 0  1  2  3  4  5
[45,89,22,31,23,76]

그리고 그것의 색인의 순열 :

[5,3,2,1,0,4]

이렇게 순열에 따라서 그것을 의지하는 능률적 인 방법 있는가?

[76,31,22,89,45,23]

최대 O (1) 개의 추가 공간을 사용합니까?


잭의 해결책은 아주 좋습니다.

아직도, 나는 왜 분류 할 필요가 있는지 궁금해하고 있었다. 인덱스 순열이있는 경우 값을 이전 배열에 대한 포인터로 사용하십시오.

이렇게하면 처음부터 배열을 정렬 할 필요가 없습니다. 이것은 모든 경우에 사용할 수있는 솔루션은 아니지만 대부분의 경우에 정상적으로 작동합니다.

예 :

a = [45,89,22,31,23,76];
b = [5,3,2,1,0,4]

이제 a에 있는 값들을 살펴보고 싶다면 (의사 코드)와 같은 것을 할 수 있습니다 :

for i=0 to 4
{
    process(a[i]);
}

새 주문에서 값을 반복하려면 다음을 수행하십시오.

for i=0 to 4
{
    process(a[b[i]]);
}

앞서 언급했듯이,이 해결책은 많은 경우에 충분할 수 있지만 다른 경우에는 그렇지 않을 수도 있습니다. 다른 경우 Zach의 솔루션을 사용할 수 있습니다. 그러나이 솔루션을 사용할 수있는 경우에는 정렬이 필요 없기 때문에 더 좋습니다.





swap