[TI-nspire] [Program] 순열(Permutation) - Heap's Algorithm (Recursive)

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}

			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}