close_btn

  • ※ 사이트 내부 통합검색


  • ※ 카카오페이로 기부하기

  • ※ 사이트 내부 통합검색
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄

앞서 구현한 순열을 찾는 프로그램은 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 전역변수 문제는 조금 더 연구를 해 보아야 할 것 같습니다.

?