원하는 순서로 번호 순열

Question

특정 순서로 고유 번호 목록의 순열 알고리즘을 생성하고 싶습니다.
예 : - 순열 때문이다
수는

1 2 3 4 

주문 있습니다 첫 번째 숫자는 4 위 및 네 번째로 세 번째, 두 번째 첫 번째 장소에 3 위로 이동합니다 즉 순열 후

3 1 4 2 

두 번째 장소. 알고리즘은 다음 약간 반복 후에는 입력 된 숫자와 동일한 시퀀스를 생성 순서에 의해 치환을 수행하는 것을 계속하고 중지하는 경우
이제 숫자 순서는 지금

2 4 1 3 

것이다. 반복이 경우 총 개수를 들어 내가 number[] 및 order[]라는 이름의 다른 두 배열을 다른 배열 tmp[]를 취함으로써이 일을하고 4

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

입니다. 이제는 order[]에서 특정 요소의 위치 순서를 유지하고 다음 반복 전에 동일한 번호 시퀀스를 확인하여 number[]의 요소를 tmp[]에 복사하는 것입니다. 다른 반복이 필요한 경우 number[]=tmp[]이고 알고리즘은 이전 단계를 반복합니다.

이제 요소 수가 많으면 예 : 10^7 이상이면이 방법은 느리게 실행됩니다. 반복 횟수를 찾는 더 좋은 해결책이 있습니까?

Answer 1

순열을 생성하려면 복잡도가 출력 크기와 같기 때문에 솔루션은 이미 최적입니다.

는 별개의 순열의 수에만 관심이있다 그러나 경우에 당신은 당신이 훨씬 더 잘 할 수 생성 할 수 있습니다

• 을주기에 "순서를"분해 : 예를 3 1 4 2 1 개주기 1 -> 3 -> 4 -> 2 -> 1하지만 2 1 4 3 두 가지입니다 위해 사이클 1 -> 2 -> 1 및 3 -> 4 -> 3
• n1, …, np이주기의 길이이며 lcm 최소 공배수이다 구별 순열의 수 lcm(n1, …, np)이다.