총 순열은 시간 복잡도가 O(n!)인 알고리즘입니다. 이틀 전에 학생들에게 강의를 하다가 우연히 이 문제가 생각나서 7가지 알고리즘으로 풀 수 있습니다. 그 중 동적 루프는 역추적 알고리즘과 유사하기 때문에 구현하기가 상대적으로 번거로워 독자들의 편의를 위해 6가지 유형을 정리했습니다. 모든 알고리즘은 JavaScript로 작성되었으며 직접 실행할 수 있습니다.
알고리즘 1: 교환(재귀)
전체 순열(Recursive Swap)
Mengliao Software Studio - Bosun Network Co., Ltd.
2011.05.24
전체 순열(재귀 링크)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
전체 순열(재귀적 역추적)
Mengliao Software Studio - Bosun Network Co., Ltd.
2012.03.29
2012.03.29
전체 순열(비재귀 모듈로)
;/p> 원래 배열의 요소 수와 같습니다.
2. n개 요소 모두 배열됨, 즉
3. 정수 >=0에서 시작하여 매번 1씩 누적되며 첫 번째 요소 arr[0]을 가져옵니다. , 1자리 표현식의 최하위 비트를 찾습니다. 즉, 모듈로 1인 인덱스의 w 값을 찾고, 결과의 첫 번째 요소(arr[0])를 삽입하고, index1을 반복합니다.
5; 두 번째 요소 arr[1]을 가져와 이진수식의 가장 낮은 비트, 즉 모듈로 2 인덱스의 w 값을 찾고 두 번째 요소(arr[1])를 변경하여 결과의 w 위치를 삽입하고, 인덱스를 index2로 반복합니다.
6. 세 번째 요소 arr[2]를 가져와 삼항 표현식의 가장 낮은 비트를 찾습니다. 즉, 인덱스 모듈로 3w의 값을 찾고 세 번째 요소(arr[2])를 삽입합니다. 결과의 w 위치로 이동하고 마지막 요소 arr[arr.length-1이 취해질 때까지] index3을
7,...
8로 반복합니다. 이때 순열이 얻어집니다.
9. 인덱스 루프가 완료되면 모든 순열을 얻습니다.
예:
4개 요소["a", "b", "c", "d"]의 전체 배열을 찾아 4!=총 24회 반복하고 임의의 항목에서 시작할 수 있음> ;= 정수 인덱스 0은 루프를 시작하고 루프가 인덱스 23에 도달한 후 끝날 때까지 매번 1을 누적합니다.
인덱스=13(또는 13 24, 13 2*24, 13 3*24...) ), 총 4개의 요소가 있으므로 4번 반복한 후 결과 순열 프로세스는 다음과 같습니다.
첫 번째 반복, 13/1, 몫 = 13, 나머지 = 0이므로 첫 번째 요소가 0번째 위치(즉, 아래 첨자는 0), get ["a"]; 두 번째 반복, 13/2, 몫=6, 나머지=1이므로 두 번째 요소가 첫 번째 위치에 삽입됩니다(즉, 첨자는 1)이고 [ "a", "b"];
3번째 반복, 6/3, 몫=2, 나머지=0을 얻으므로 세 번째 요소가 0번째 위치에 삽입됩니다. (즉, 아래 첨자는 0), [" c", "a", "b"]를 얻습니다.
4번째 반복, 2/4, 몫=0, 나머지=2이므로 4번째 요소입니다. 두 번째 위치에 삽입됩니다(즉, 아래 첨자는 2입니다). Get ["c", "a", "d", "b"]
*/
var count = 0; >function show(arr) {
document.write("P< ;sub>" count ": " arr "
")
}
function perm( arr) {
var result = new Array(arr.length) ;
var fac = 1
for (var i = 2; i <= arr.length; i )
fac * = i;
for (index = 0; index < fac ; index ) {
var t = index
for (i = 1; i <= arr.length; i ) {
var w = t % i;
for (j = i - 1; j > w; j--)
결과[j] = 결과[j - 1]
결과[w] = arr[i - 1];
t = Math.floor (t / i)
} }
show(result)
}
}
perm([" e1", "e2", "e3", "e4"]);
