사전 정렬 방법은 정렬을 생성합니다

전체 정렬을 생성하는 알고리즘은 주어진 문자 세트에 대해 가능한 모든 전체 정렬을 반복하거나 빠뜨리지 않고 효과적으로 열거하는 것입니다. N 개의 문자 세트의 임의 배열은 1 ~ n 의 N 수 배열과 일대일로 대응될 수 있으므로 N 수의 배열을 예로 들어 정렬 생성을 설명할 수 있습니다. ...

전체 정렬을 생성하는 알고리즘은 주어진 문자 세트에 대해 가능한 모든 전체 정렬을 반복하거나 빠뜨리지 않고 효과적으로 열거하는 것입니다. N 개의 문자 세트의 임의 배열은 1 ~ n 의 N 수 배열과 일대일로 대응될 수 있으므로 N 수 배열을 예로 들어 정렬 생성 방법을 설명합니다.

N 자의 모든 배열 사이에는 명확한 선형 순서 관계가 있습니다. 마지막 정렬을 제외한 모든 정렬에는 후속 배열이 있습니다. 첫 번째 안배 외에 또 하나의 전조가 있다. 각 정렬의 후속 순서는 가장 작은 변화가 있는 전임자에서 얻을 수 있으며, 모든 정렬을 생성하는 알고리즘은 첫 번째 정렬부터 시작하여 모든 정렬을 하나씩 생성하는 방법입니다.

보통 다음 방법으로 내세를 완성할 수 있다.

사전 정렬 방법

증분 십진수 방법

십진체감법

정위교환법

재귀 클래스 알고리즘

1. 사전 정렬 방법

사전 정렬 방법에서 숫자 1, 2,3 의 정렬 ... N 은 해당 숫자의 순서를 왼쪽에서 오른쪽으로 비교하여 다른 정렬의 순서를 결정합니다. 예를 들어 5 자리 배열 12354 및 12345 의 경우 12345 가 맨 앞에 오고 12354 가 맨 끝에 옵니다 이 규정에 따르면 다섯 자리 숫자 중 첫 번째는 12345, 마지막은 5432 1 입니다.

사전 순서 알고리즘은 다음과 같습니다.

P 를 1 ~ n 의 전체 변위로 설정: p = p1p2 ... pn = p1p2 ... pj-/kloc-

1) 배열의 오른쪽 끝에서 시작하여 오른쪽 숫자보다 작은 첫 번째 숫자의 일련 번호 j(j 는 왼쪽 끝에서 계산됨) 를 찾습니다. 즉 j = max {i | pi

2) pj 오른쪽 수에서 pj 보다 큰 모든 수 중 가장 작은 수 PK, 즉 k = max {I | pi "를 찾습니다. Pj} (오른쪽 숫자는 오른쪽에서 왼쪽으로 증가하므로 k 는 Pj 보다 큰 모든 숫자 중 가장 높은 숫자입니다.)

3) 스위치 pi, PK

4) 그런 다음 pj+1... PK-1PPK+1pn 은 거꾸로 배열되어 p "= p1p

예를 들어 83964752 1 은 숫자 1 ~ 9 의 배열입니다. 다음 정렬을 생성하는 단계는 다음과 같습니다.

오른쪽에서 왼쪽으로 첫 번째 숫자 4 83964752 1 을 찾습니다. 오른쪽 숫자보다 작습니다.

이 숫자 뒤의 숫자에서 4 보다 큰 최소 숫자 5 83964752 1 을 찾습니다.

83965742 1 스위치 5 와 4 를 사용합니다.

반전 742 1 83965 1247.

그래서 83964752 1 의 다음 배열은 83965 1247 입니다.

2. 증분 십진수 방법

증분 십진수 방법에서는 한 배열에서 다른 배열을 찾기 위해 중간 숫자가 필요합니다. P 1p2 의 요소 P 1 오른쪽에 있는 숫자 수를 정렬하면 ... 원주율 ... pn 은 ki 로 표시되며, 정렬의 중간 수는 해당 정렬 K 1 ... 키바니스 인터내셔널

예를 들어 83964752 1 을 정렬하는 중간 수는 7264232 1 이고 7, 2, 6, ... 숫자 8,3,9 오른쪽에 있는 숫자는 그것보다 작습니까? ... 각각 배열중입니다.

중간 수는 계산 배열의 중간 부분입니다. 주어진 안배는 다음 안배가 필요하다. 우선, 중개 수를 결정하십시오. 배정된 상속자의 경우 중개번호는 원래 배정된 중개번호에 1 을 더한 것이다. 가운데 수의 마지막 kn- 1+ 1=2 인 경우 앞으로 이동합니다. 일반적으로 KI+ 1 = 인 경우 예를 들어 83964752 1 의 중간 수가 7264232 1 이면 다음 정렬의 중간 수는 673422/입니다

중간 수를 얻은 후 그에 따라 해당 정렬을 복원할 수 있습니다.

알고리즘은 다음과 같습니다.

중간 번호 k 1, k2, ..., KN- 1 은 숫자 n, n- 1, ..., 2 는 정렬에서 오른쪽 끝에서 시작하므로 k 를 눌러야 합니다 그리고 그것들을 하나씩 배열합니다. I 는 오른쪽에서 시작하여 ki+ 1 의 위치에 있습니다. 숫자를 이미 배치한 경우 위치가 계산되지 않고 마지막 공백은 1 에 배치됩니다.

따라서 8496 17523 은 83964752 1 의 마지막 배열인 67342300 에서 얻을 수 있습니다. 9 가 1 위에 있고, k1= 6,9 가 오른쪽 7 위에 있고, 6 개의 빈자리가 남아 있고, 8, k2 = 7,8 이 오른쪽 8 위에 있지만 9 가 한 자리를 차지하므로 8 은 오른쪽 9 위에 놓여야 합니다

3. 십진수 체감법

증분 십진수 방법에서 중간 수의 가장 낮은 비트는 각 바이너리 1 이며 이는 단점입니다. 오름차순 10 진수를 반대로 하여 내림차순 10 진수를 얻습니다.

83964752 1 의 중간 수는 6734221(k1k2 ... kn-1) 으로 반전됩니다 주어진 배열 P, P 의 다음 배열의 중간 수는 P 의 중간 수에 1 을 더한 값으로 정의됩니다. 예를 들어 p=83964752 1, p 의 중개 수는 1224376, p 의 다음 배열 중개 수는1224376+/kloc-입니다

지정된 중간 수는 증분 10 진수 방법과 유사한 방법으로 정렬을 복원할 수 있습니다. 그러나 10 진수 시스템에서는 중간 수를 먼저 계산하지 않고 다음 정렬을 한 배열에서 직접 얻을 수 있습니다. 구체적인 알고리즘은 다음과 같습니다.

1) p(I)= n 및 I 인 경우

2) p(n)= n 인 경우 연속 감소 시퀀스 9,8, ..., I 를 찾아 배열의 왼쪽 끝에서 제거하고 반대 순서로 배열의 오른쪽 끝에 추가한 다음 왼쪽 숫자와 I- 1 을 교환합니다.

예를 들어 p=89364752 1 의 다음 배열은 98364752 1 입니다. 98364752 1 의 다음 정렬을 찾을 때 9 는 맨 왼쪽에 있고 두 번째 위치는 8 이고 세 번째 위치는 7 이 아니므로 8 과 9 는 364752 189 의 맨 오른쪽 끝에 98364752 가 있습니다 예를 들어, 98763542 1 의 다음 정렬을 찾으려면 9876 을 가장 작은 것부터 가장 오른쪽 순으로 정렬하고 5 를 왼쪽의 숫자 3 으로 전환하면 5342 16789 를 얻을 수 있습니다.

4. 정위교환법

인접한 정렬 방법의 다음 배열은 항상 이전 정렬의 인접한 두 자리 중 일부를 교환하여 얻습니다. 네 가지 요소의 배열을 예로 들면 마지막 요소 4 를 이전 요소와 하나씩 교환하여 네 가지 새로운 배열을 만들 수 있습니다.

12 3 412 4 314 2 3 412 3

그런 다음 마지막 정렬의 끝에 있는 두 요소를 스왑한 다음 해당 행의 맨 위에 있는 4 를 다음 요소와 하나씩 스왑하여 네 개의 새 정렬을 생성합니다.

413 214 3 213 4 213 2 4

그런 다음 마지막 정렬의 끝에 있는 두 요소를 교환하고 4 를 뒤에서 앞으로 이동합니다.

312 4 314 2 3 412 4 312

이 주기는 모든 배열을 찾을 수 있을 뿐만 아니라

5 요소 증분 방법 (n 요소 방법)

1), 원래 배열 P = P 1p2 부터 ... PN, n- 1 을 n 위에 추가합니다. 이 비트의 값이 n 을 초과하면 n 으로 나누고 나머지 비트로 교체하고 반올림합니다 (n 번째 비트에 1).

2) n- 1 비트, n-2 비트, ... 반올림이 더 이상 나타나지 않고 한 정렬을 처리한 후 새 정렬을 생성할 때까지 같은 방식으로 처리합니다.

3) 동일한 요소가 있는 정렬을 삭제합니다.

4) 첫 번째 요소의 값이 "인 경우; N 이 끝났습니다.

예를 들어 1, 2,3 의 세 자리 배열을 예로 들 수 있습니다. 원래 배열은12 2 3 입니다. 이 세 번째 요소는 3,3+2 = 5,5 mod 3 = 2 입니다. 요소를 통과하는 증분은 1 2 3, 1 3 2, 2 1 1, 21입니다

밑줄 정렬에는 반복 요소가 있습니다. 그것들을 버리면 나머지는 모든 안배이다.

6. 재귀 클래스 알고리즘

재귀적으로 전체 변위의 생성 방법을 간결하게 설명하고 여러 가지 구현 방법을 사용할 수 있습니다.

1) 역추적 방법

역추적 방법은 일반적으로 스패닝 트리 한 그루를 구성하는 것이다. 세 가지 요소를 예로 들어 보겠습니다. 트리의 노드에는 데이터가 있으며 사용할 수 있는 값은 1, 2 및 3 입니다. 1 이 0 이면 값이 없음을 의미합니다.

초기 상태는 (0,0,0) 이고 1 개 요소 값은 각각 1, 2,3 으로 선택할 수 있으므로 세 개의 하위 노드가 확장됩니다. 같은 방법으로 이러한 노드의 두 번째 요소에 가능한 값을 찾는 등 새 노드의 세 데이터가 모두 0 이 아니면 전체 정렬 체계를 찾습니다. 가능한 모든 방안을 시도했을 때, 질문에 대한 답이 나왔다.

2) 재귀 알고리즘

P 는 n 개 요소의 정렬을 나타내고, Pi 는 요소 I 의 정렬이 없음을 나타내며, (I)Pi 는 Pi 를 정렬하기 전에 접두사 I 가 있는 정렬을 나타내는 경우 n 개 요소의 정렬을 재귀적으로 다음과 같이 정의할 수 있습니다.

N= 1 이면 변위 p 에는 요소 I 가 하나만 있습니다.

N> 1 인 경우 변위 p 는 변위 (I)Pi(I = 1, 2, ... n- 1) 에 의해 교체됩니다.

정의에 따르면 k- 1 개 요소의 정렬이 이미 생성된 경우 k- 1 개 요소의 각 정렬 Pi 앞에 요소 I 를 추가하여 K 개 요소의 정렬을 생성할 수 있다는 것을 쉽게 알 수 있습니다. 예를 들어 두 요소의 배열은12 와 21이고 다른 요소의 경우 p 1 은 2 3 과 3 2 입니다. 각 정렬 앞에 1 을 추가하여 두 개의 새 정렬12 3 과13 2 를 만들고 p2 와 P3 은1을 생성합니다 같은 방법으로 새 배열 2 1 3, 2 3 1, 3 1 2 및 3 2 1 을 생성할 수 있습니다.

3) 순환 이동 방법

이미 k- 1 개 요소의 배열을 생성한 경우 각 정렬 뒤에 요소 k 를 추가하여 k 개 요소의 배열로 만든 다음 각 정렬 루프를 왼쪽 (오른쪽) 으로 이동하면 이동할 때마다 새 정렬이 생성됩니다.

예를 들어 두 요소의 배열은12 와 21입니다. 12 뒤에 3 을 추가하여 새 정렬12 3 으로 만들고 왼쪽으로 루핑하여 새 정렬 2 31,3/kloc/를 생성합니다