- TI nspire
[TI-nspire] [Program] 순열(Permutation) - Heap's Algorithm (Recursive)
-
- 2024.07.27 - 01:58 2015.09.29 - 10:11 982
앞서 구현한 순열을 찾는 프로그램은 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://allcalc.org/5876 2025 10.26 [BA II PLUS] 로 입력해 보니 [EL-738XT] 과 달리 【+|-】 버튼을 이용하든 【－】버튼을 이용하든 앞에 입력된 항목값은 음수 입력에 영향을 주지 않네요. 2025 10.26 오류 발생 https://www.youtube.com/watch?v=dcg0x5SjETY 위 영상의 문제의 함수를 직접 구해 보았습니다. 그래프로는 잘 확인이 되는데... fmin(), fmax() 함수로 직접 구해보니, 결과가 기대한 것과 다르네요. 구간을 넣지 않으니 fmim, fmax 둘 다에서 오류인 결과를 내놓습니다. 구간을 넣더라도, 적절하게 넣지 않으면, 답이 잘 안나오는 걸 확인할 수 있습니다. fmin 은 그나마 x=0을 기준으로 나누지 않더라도 답이 나오는 편이지만, fmax 는 -10~10 을 구간으로 넣을 때, 가운데 x=0 근방에서 그래프가 위로 솟아오르는 구간은 함수값을 확인하지 않는 듯 합니다. ㄴ fmax가 더 열등해서 그런 것은 아니고, 뒤집어진 모양에서는 반대로 fmin이 못찾습니다. 구간 범위가 커질 경우, 함수에 적용하여 계산하다가 숫자 허용 한계를 벗어나서 overflow 가 나서 오류가 발생할 수도 있는 듯 합니다. 뒤에 점을 넣으니 경고 문구가 추가로 나오긴 했는데, ⚠️ Questionable accuracy. When applicable, try using graphical methods to verify the results. 그래도 실망이네요. * 믿음직한 녀석은 아닌 듯 하니, 주의 표시 ⚠️가 나오든 안나오든, 사용에 주의하시기 바랍니다. 가급적이면 그래프로 검증해 보시는게 좋겠습니다. 2025 10.26 예시 8-1 : 분수식 solve시 오류 예시, 분모에 들어간 X³을 X로 치환해 해결? https://allcalc.org/56074 2025 10.25 fx-570 CW 는 아래 링크에서 https://allcalc.org/56026 2025 10.24