Permutations

Blitz3D Forums/Blitz3D Programming/Permutations

virtlands

(Posted 2013) [#1]

Hi, this research topic is on permutations and how to generate them.

I've searched the community code archives for this topic, and it looks lik I'm the first to try to generate permuation sets.

The algorithm to compute the number of n items taken k at a time, is the following:

Object order is important, and objects are not allowed to be repeated within a subset.

But the code to actually display all those permutations is much more complex.

I found a very quick algorithm in 'C' known as the "boothroyd" method,
so I translated it into Blit3D in this demonstration program.

I don't understand the boothroyd logic at all, but it works.

;;  Permutation Methods Version 1
;;  This program was created arranged by VirtLands {March 02,,2013}
;;
;;  I used the "boothroyd" algorithm found on the following webpage:
;;  <a href="http://rosettacode.org/wiki/Permutations#C" target="_blank">http://rosettacode.org/wiki/Permutations#C</a>  

 Global x_max=12
 Dim X(x_max) 

 Graphics 900,600,32,2

 Global set_n = 4
 Global set_k = 4

 Global setshow$   ;; just a nice formatting method to display long strings
 Global superset$   ;; a superset of all sets, ..this is used to avoid duplicates
 Global setcount

 Print"  --- A study in permutation methods --- Version 1 ---"
 Print
 Print"  { The goal is to generate all permutations of n different objects } "
 Print"  { Each subset is not allowed to have repeats. } "
 Print"  { Order matters. } "

 Print 
 .Start 
 set_n = Input$("  Enter n objects   : n = ")
 set_k = Input$("  taken k at a time : k = ")
 Print 

 If set_n=0 Or set_k=0 Then End 

 If set_n>x_max          ;; redimension if necessary
           x_max = set_n
           Dim x(x_max) 
 End If 

 For z=0 To set_n        ;; a simple enumeration
        x(z)=z
 Next 

 Local s$

 s = getset()                   ;; get ready to display the first permutation 
 s = s + " "
 setshow = "  "+s
 superset = superset +s      
 setcount = 1

 boothroyd_1A(set_n, set_k)              ;; and then, print the rest... 
 If Len(setshow) Then Print setshow   
 Print"  --- "+setcount+" sets were found. "
 Print 

 setshow="" : superset=""  ; reset these so that we can do another
 Goto Start 

Function boothroyd( n, nn )
       Local c,i,t,z   
       Repeat 
                 If n>2 Then boothroyd( n-1, nn )
                 If c>= n-1 
                           Return
                 End If 

                 If (n And 1)=1
                           i = 0
                 Else 
                           i = c
                 End If 
                 c = c+1
                 t = x(n-1) : x(n-1)=x(i) : x(i)=t

                 setshow = setshow+getset()+" "
                 setcount = setcount +1
                 If Len(setshow)>=100
                          Print setshow
                          setshow = "  "                          
                 End If  
       Forever  
End Function 

;;  This is basically the same as previous, except that I added some code to avoid duplicate sets.
Function boothroyd_1A( n, nn )
       Local c,i,t,z, s$
       Repeat 
                 If n>2 Then boothroyd_1A( n-1, nn )
                 If c>= n-1 
                           Return
                 End If 

                 If (n And 1)=1
                           i = 0
                 Else 
                           i = c
                 End If 
                 c = c+1
                 t = x(n-1) : x(n-1)=x(i) : x(i)=t

                 s = getset()
                 If Instr(superset,s)=0              ;; this code checks for duplicate "sets"
                          setcount = setcount +1
                          s = s +" "
                          superset = superset +s
                          If Len(setshow)>=100
                                   Print setshow
                                   setshow = "  "
                          Else 
                                   setshow = setshow+s
                          End If   
                 End If       
       Forever  
End Function 


;; Creates a nice way to view the set
;;
Function GetSet$()
         Local z,s$
         For z=0 To set_k-1
                 s = s + Chr$(x(z)+65)
         Next 
         Return s     
End Function

[screenshot of program output]

There are apparently times when the Function duplicates set listings,
as in you can obviously see that "ABC" is duplicated.

I made some small 'catch' code and added to "boothroyd_1A" to
avoid duplications...

I'll be back later. My goal is to create my own algorithm for creating permutations. So far, my own ideas didn't work,

but the "boothroyd" method does.

http://rosettacode.org/wiki/Permutations#C