모든 선행 순열을 생성하지 않고 집합의 N번째 순열을 직접 찾을 수 있는 방법은 무엇입니까?

n번째 순열을 직접 가져오기

모든 항목을 명시적으로 계산하지 않고 요소 집합의 n번째 순열을 찾는 작업입니다. 이전 순열. 이는 Factoradic 알고리즘이라는 영리한 알고리즘을 사용하여 달성할 수 있습니다.

Factoradic 알고리즘은 순열 지수의 계승 분해를 활용합니다. 계승수를 사용하여 유클리드 나눗셈을 반복적으로 수행함으로써 순열을 나타내는 몫 세트를 얻습니다.

알고리즘 작동 방식은 다음과 같습니다.

1. 계수 분해: 순열 인덱스 n을 (n-1)!, (n-2)! 등의 계승으로 나눕니다. 몫은 배열에 저장됩니다.
2. 순열 표현: 각 몫은 나머지 요소 중에서 선택한 요소의 인덱스를 나타냅니다.
3. 조정: 몫은 이전 값을 고려하지 않으므로 올바른 순열을 반영하도록 조정해야 합니다. 각 몫을 그보다 작거나 같은 이전 몫의 수만큼 증가시킵니다.

예를 들어, {'A', 'B', 'C'}의 세 번째 순열을 찾아보겠습니다.

• n = 3
• 몫: [1, 0, 0]
• 조정된 몫: [1, 0, 1]

따라서 순열은 'B', 'A', 'C'입니다. 이는 실제로 의 세 번째 순열입니다.

제공된 C 코드는 Factoradic 알고리즘을 구현하여 다음을 얻는 방법을 보여줍니다. 이전 순열을 계산하지 않고 직접 n번째 순열을 계산합니다.

위 내용은 모든 선행 순열을 생성하지 않고 집합의 N번째 순열을 직접 찾을 수 있는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!