- TI nspire
[TI-nspire] [Program] 순열(Permutation) - Heap's Algorithm (Recursive)
-
- 2024.07.27 - 01:58 2015.09.29 - 10:11 1168
앞서 구현한 순열을 찾는 프로그램은 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 전역변수 문제는 조금 더 연구를 해 보아야 할 것 같습니다.
-
25
세상의모든계산기 님의 최근 댓글
은행앱 통합하면서 없어졌나보네요. ㄴ 비슷한 기능 찾으시는 분은 : 스마트 금융 계산기 검색해 보세요. https://play.google.com/store/apps/details?id=com.moneta.android.monetacalculator 2026 01.25 Ctrl+Z 를 이용해 뒤로 돌아기기 Undo 기능이 있는지 살펴보세요. 2026 01.23 쌀집계산기로 연립방정식 계산하기 - 크래머/크레이머/크라메르 공식 적용 https://allcalc.org/56739 3. 'x' 값 구하기 계산기 조작법 목표: x = Dx / D = [(c×e) - (b×f)] / [(a×e) - (b×d)] 계산하기 1단계: 분모 D 계산 (메모리 활용) 1 * 1 M+ : 메모리(M)에 1를 더합니다. (현재 M = 1) -0.1 * -0.2 M- : 메모리(M)에서 0.02를 뺍니다. (현재 M = 0.98 = 0.98) 이로써 메모리(MR)에는 분모 0.98가 저장됩니다. 2단계: 분자 Dx 계산 후 나누기 78000 * 1 : 78000를 계산합니다. = : GT에 더합니다. -0.1 * 200000 : -20000를 계산합니다. ± = : 부호를 뒤집어 GT에 넣습니다. // sign changer 버튼 사용 GT : GT를 불러옵니다. GT는 98000 (분자 Dx) 값입니다. ÷ MR = : 위 결과(98000)를 메모리(MR)에 저장된 분모 D(0.98)로 나누어 최종 x값 100,000를 구합니다. 4. 'y' 값 구하기 계산기 조작법 목표: y = Dy / D = [(a×f) - (c×d)] / [(a×e) - (b×d)] 계산하기 1단계: 분모 D 계산 (메모리 활용) 'x'에서와 분모는 동일하고 메모리(MR)에 0.98가 저장되어 있으므로 패스합니다. 2단계: 분자 Dy 계산 후 나누기 GT ± = : GT를 불러오고 부호를 뒤집어 GT에 더합니다. GT가 0으로 리셋됩니다. 【AC】를 누르면 M은 유지되고 GT만 리셋되는 계산기도 있으니 확인해 보세요. 1 * 200000 : 200000를 계산합니다. = : GT에 더합니다. 78000 * -0.2 : -15600를 계산합니다. ± = : 부호를 뒤집어 GT에 넣습니다. GT : GT를 불러옵니다. 215600 (분자 Dy) 값입니다. ÷ MR = : 위 결과(215600)를 메모리(MR)에 저장된 분모 D(0.98)로 나누어 최종 y값 220,000를 구합니다. x, y 값을 이용해 최종 결과를 구합니다. 2026 01.18 크레이머 = 크레머 = 크라메르 공식 = Cramer's Rule https://allcalc.org/8985 2026 01.18 부호 변경, Sign Changer 버튼 https://allcalc.org/52092 2026 01.18