- TI nspire
[TI-nspire] [Program] 순열(Permutation) - Heap's Algorithm (Recursive)
-
- *.165.6.43
- 2024.07.27 - 01:58 2015.09.29 - 10:11 879
앞서 구현한 순열을 찾는 프로그램은 n^n 루프를 회전시켜야만 하는 비효율적인 프로그램이었습니다.
http://www.allcalc.org/7618
그래서 좀 더 나은 것을 찾아봤는데, 이게 가장 효율적이었습니다.
https://en.wikipedia.org/wiki/Heap%27s_algorithm
하지만 재귀호출방식이라서 잘 될까 의문이 들었습니다. 기본 알고리즘은 다음과 같습니다.
procedure generate(n : integer, A : array of any): if n = 1 then output(A) else for i := 0; i < n - 1; i += 1 do generate(n - 1, A) if n is even then swap(A[i], A[n-1]) else swap(A[0], A[n-1]) end if end for generate(n - 1, A) end if
배열[ ]이 0부터 시작하는 것을 주의하여 프로그램을 짜 봤는데...
|
Define perm_list(list,n)= Prgm : :k+1→k :© Disp "============" :© Disp "ⓐ N th trials = ",k,"---------------" : :Local f_i : If n=1 Then : Disp "★",list : Else : For f_i,1,n-1 :© Disp "ⓒ i=",f_i,", n-1=",n-1 : perm_list(list,n-1) : If mod(n,2)=0 Then : Disp "Before",list : Disp "Even n=",n,"↔",f_i : swap(list,f_i,n)→list : Disp "After ",list : Else : Disp "Before",list : Disp "Odd n=",n,"↔ 1" : swap(list,1,n)→list : Disp "After ",list : EndIf : EndFor : perm_list(list,n-1) : EndIf : :EndPrgm
|
★ {1,2,3,4} Before {1,2,3,4} Even n 2 ↔ 1 After {2,1,3,4} ★ {2,1,3,4} Before {1,2,3,4} Odd n 3 ↔ 1 After {3,2,1,4} ★ {3,2,1,4} Before {3,2,1,4} Even n 2 ↔ 1 After {2,3,1,4} ★ {2,3,1,4} Before {3,2,1,4} Odd n 3 ↔ 1 After {1,2,3,4} ★ {1,2,3,4} Before {1,2,3,4} Even n 2 ↔ 1 After {2,1,3,4} ★ {2,1,3,4} Before {1,2,3,4} Even n 4 ↔ 1 After {4,2,3,1}
(중간 생략)
★ {1,2,4,3} Before {2,1,4,3} Odd n 3 ↔ 1 After {4,1,2,3} ★ {4,1,2,3} Before {4,1,2,3} Even n 2 ↔ 1 After {1,4,2,3} ★ {1,4,2,3} |
결과에 자꾸 반복되는 조합이 생겨서 뭐가 문제인가 봤더니...
새로 찾은 (swap 후) 결과 list가 다음번에 유지되지 않고, 이전 호출 perm_list(list)로 돌아면서 새 list 대신 이전 호출때 입력받은 list 를 사용하는 것 같더라구요. (추정)
그래서 일단 list 를 프로그램의 인자로 사용하지 않고, 전역변수를 이용하도록 변경하였습니다.
Define LibPriv perm_heap(n)= Prgm : : Local f_i : If n=1 Then : count_k+1→count_k : Disp "#",count_k,heap_list : Else : For f_i,1,n-1 : perm_heap(n-1) : If mod(n,2)=0 Then : swap(heap_list,f_i,n)→heap_list : Else : swap(heap_list,1,n)→heap_list : EndIf : EndFor : perm_heap(n-1) : EndIf :EndPrgm |
0→count_k:{a,b,c,d}→heap_list perm_heap(dim(heap_list)) # 1 {a,b,c,d} # 2 {b,a,c,d} # 3 {c,a,b,d} # 4 {a,c,b,d} # 5 {b,c,a,d} # 6 {c,b,a,d} # 7 {d,b,a,c} # 8 {b,d,a,c} # 9 {a,d,b,c} # 10 {d,a,b,c} # 11 {b,a,d,c} # 12 {a,b,d,c} # 13 {a,c,d,b} # 14 {c,a,d,b} # 15 {d,a,c,b} # 16 {a,d,c,b} # 17 {c,d,a,b} # 18 {d,c,a,b} # 19 {d,c,b,a} # 20 {c,d,b,a} # 21 {b,d,c,a} # 22 {d,b,c,a} # 23 {c,b,d,a} # 24 {b,c,d,a} |
|
일단 답은 나왔습니다만, 인자 vs 전역변수 문제는 조금 더 연구를 해 보아야 할 것 같습니다.