- TI nspire
[TI-nspire] [Program] 순열(Permutation) - Heap's Algorithm (Recursive)
앞서 구현한 순열을 찾는 프로그램은 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 전역변수 문제는 조금 더 연구를 해 보아야 할 것 같습니다.
세상의모든계산기 님의 최근 댓글
낮에 TV에서 영화 '말모이' 해주더라구요. 그래서 한번 물어 봤습니다. 2025 10.10 마지막 발언이 마지막 힌트이자 문제의 핵심이군요. 처음 들은 달이 8월이었다면 (15일인지 17일인지 확신할 수 없어서) 마지막 대사를 할 수 없지만, 처음 들은 달이 7월이었다면 (선택지가 16일 하나라서 확신이 가능하므로) 마지막 대사를 할 수 있다. 대사를 했으니 7월이다. 이제 이해되었습니다. 지금 보니까 이해가 되는데, 당시에는 왜 이해가 안됐을까요? 세가지 전제 하에 문제를 풀면 A는 마지막 대화 2줄만으로 C의 생일을 알 수 없어야 정상인데, 무슨 이유에서인지 "그럼 나도 앎!"이라고 선언해 버립니다. 알게 된 이유를 대화 속에서 찾을 수는 없습니다. 이 편견에 사로잡혀 빠져나오지 못하고 다른 길로 계속 샜나봅니다. 2025 10.09 (장*훈)님 (+10,000원) 계좌 후원(2025/10/09) 감사 드립니다. 2025 10.09 원래 식이 풀어진 상태에서는 두번째 인수 v가 분모, 분자에 섞여 있어서 계산기가 처리하지 못하는 듯 합니다. 이 때는 위에서와 반대로 분모 부분만 다른 문자(w)로 치환한 다음 completesquare(,v^2) 처리를 하면 일부분은 묶이는 듯 합니다. 하지만 여기서 처음 모양으로 더 이상 진행되진 않네요. 2025 10.08 전체 식에서 일부분(분모, 루트 내부)만 적용할 수는 없습니다. 번거롭더라도 해당 부분만 따로 끄집어 내서 적용하셔야 합니다. https://allcalc.org/30694#comment_30704 2025 10.08