- TI nspire
[TI-nspire] [Program] 순열(Permutation) - Heap's Algorithm (Recursive)
-
- 2024.07.27 - 01:58 2015.09.29 - 10:11 980
앞서 구현한 순열을 찾는 프로그램은 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
세상의모든계산기 님의 최근 댓글
fx-570 CW 는 아래 링크에서 https://allcalc.org/56026 2025 10.24 불러오기 할 때 변수값을 먼저 확인하고 싶을 때는 VARIABLE 버튼 【⇄[x]】목록에서 확인하고 Recall 하시면 되고, 변수값을 이미 알고 있을 때는 바로 【⬆️SHIFT】【4】로 (A)를 바로 입력할 수 있습니다. 2025 10.24 fx-570 CW 로 계산하면? - 최종 확인된 결과 값 = 73.049507058478629343538 (23-digits) - 오차 = 6.632809104889414877 × 10^-19 꽤 정밀하게 나온건 맞는데, 시뮬레이션상의 22-digits 와 오차 수준이 비슷함. 왜 그런지는 모르겠음. - 계산기중 정밀도가 높은 편인 HP Prime CAS모드와 비교해도 월등한 정밀도 값을 가짐. 2025 10.24 HP Prime 에서 <Home> 73.0495070344 (12-decimal-digits) // python 시뮬레이션과 일치 <CAS> 21자리까지 나와서 이상하다 싶었는데, Ans- 에서 자릿수를 더 늘려서 빼보니, 뒷부분 숫자가 아예 바뀌어버림. 버그인가? (전) 73.0495070584718691243 (21-digits ????) (후) 73.0495070584718500814401 (24-digits ????) 찾아보니 버그는 아니고, CAS에서는 십진수가 아니라 2진수(bit) 단위로 처리한다고 함. Giac uses 48 bits mantissa from the 53 bits from IEEE double. The reason is that Giac stores CAS data (gen type) in 64 bits and 5 bits are used for the data type (24 types are available). We therefore loose 5 bits (the 5 low bits are reset to 0 when a double is retrieved from a gen). 출처 : https://www.hpmuseum.org/cgi-bin/archv021.cgi?read=255657 일단 오차를 놓고 보면 16-decimal-digits 수준으로 보임. 2025 10.23 khiCAS 에서 HP 39gII 에 올린 khiCAS는 254! 까지 계산 가능, 255! 부터는 ∞ fx-9750GIII 에 올린 khiCAS는 factorial(533) => 425760136423128437▷ // 정답, 10진수 1224자리 factorial(534) => Object too large 2025 10.23