[Calc] Generate all permutations with StarBasic function

Shared Libraries
Forum rules
For sharing working examples of macros / scripts. These can be in any script language supported by OpenOffice.org [Basic, Python, Netbean] or as source code files in Java or C# even - but requires the actual source code listing. This section is not for asking questions about writing your own macros.
Locked
User avatar
MrProgrammer
Moderator
Posts: 5431
Joined: Fri Jun 04, 2010 7:57 pm
Location: Wisconsin, USA

[Calc] Generate all permutations with StarBasic function

Post by MrProgrammer »

The permutations of a set are rearrangements of its members, where arrangements in different orders are considered distinct. Permutation 0 1 2 is different than 1 2 0. The StarBasic function GENPERM for Calc will generate all permutations of 0 to N-1. For example, the array formula =GENPERM(3) will generate the six rows:
   0   1   2
   1   0   2
   2   0   1
   0   2   1
   1   2   0
   2   1   0

The number of rows returned by =GENPERM(N) is the value of the standard Calc function =FACT(N). Even small parameters can produce many rows. For example, =GENPERM(8) returns more than 40,000 rows and 320,000 cells. =GENPERM(10) would attempt to return more rows than an OpenOffice spreadsheet supports.

If you prefer the permutations to begin with 1 instead of 0, use array formula =1+GENPERM(3). To select permutations of other numbers or of text, use the INDEX function. This is the result of =INDEX({"fee";"fi";"fo";"fum"};1;1+GENPERM(4)):
   fee  fi   fo   fum  
   fi   fee  fo   fum  
   fo   fee  fi   fum  
   fee  fo   fi   fum  
   fi   fo   fee  fum  
   fo   fi   fee  fum  
   fum  fi   fee  fo   
   fi   fum  fee  fo   
   fee  fum  fi   fo   
   fum  fee  fi   fo   
   fi   fee  fum  fo   
   fee  fi   fum  fo   
   fee  fo   fum  fi   
   fo   fee  fum  fi   
   fum  fee  fo   fi   
   fee  fum  fo   fi   
   fo   fum  fee  fi   
   fum  fo   fee  fi   
   fum  fo   fi   fee  
   fo   fum  fi   fee  
   fi   fum  fo   fee  
   fum  fi   fo   fee  
   fo   fi   fum  fee  
   fi   fo   fum  fee  

You will need to install the code below in your OpenOffice system by following the instructions in [Tutorial] How to install a code snippet. Create a topic in the Macros and UNO API forum if you want to discuss the project further. If GENPERM doesn't work as described, attach a spreadsheet showing your use of it, and explain why the function isn't working as you expect. I may not be able to help unless you attach the spreadsheet you're having trouble with. I did not test this function in LibreOffice, but I think it will produce the same result as it does in OpenOffice.

Option Explicit                                           ' Copy everything from ...
Rem Return array of all permutations of the set 0 to N-1  ' ... the Option ...
Rem The array will contain FACT(N) rows and N columns     ' ... Explicit line to ...
Rem For example, GENPERM(3) is 6 rows, 3 columns          ' ... the bottom of ...
Rem              0;1;2|1;0;2|2;0;1|0;2;1|1;2;0|2;1;0      ' ... this topic
Rem When called from Calc, after typing =GENPERM(n) press
Rem      ⌘⇧Enter on a Mac, Ctrl+Shift+Enter on other platforms 
Rem Reference: Permutations by Interchanges, B. R. Heap 
Rem The Computer Journal, Volume 6 Issue 3, November 1963, Pages 293–298

Const NOTPOS="Set size is not positive"                   ' Error message
Dim A() As Integer                                        ' Next permutation
Dim G() As Integer                                        ' All permutations
Dim L As Long                                             ' Permutation counter

Sub [.GPK](K As Double,N As Double)                       ' Recursive subroutine
Dim I As Integer                                          ' Loop index
Dim T As Integer                                          ' Swap variable
Dim J As Integer                                          ' Element selector
Dim K1 As Integer                                         ' K minus 1
If K = 1 Then L = L+1 : _
   For I = 1 To N : G(L,I) = A(I) : Next I : Exit Sub     ' If K=1 add permutation
K1 = K-1 : [.GPK](K1,N)                                   ' Permute leftmost elements
For I = 1 To K1                                           ' Swap A(K)
   J = I : If K Mod 2 Then J = 1                          ' Choose swap pair
   T = A(K) : A(K) = A(J) : A(J) = T                      ' Swap elements
   [.GPK](K1,N)                                           ' Permute leftmost elements
Next I                                                    ' Done with A(K)
End Sub                                                   ' End subroutine

Function GENPERM(N As Double) As Variant                  ' Generate all permutations
If N <= 0 Then GENPERM = NOTPOS : Exit Function           ' Argument must be positive
Dim I As Long                                             ' Loop index
Dim F As Long : F=1                                       ' N factorial value
For I = 2 To N : F = F*I : Next I                         ' Build factorial value
ReDim G(1 To F,1 To N)                                    ' Set result size
ReDim A(1 To N)                                           ' Set row size
For I = 1 To N : A(I) = I-1 : Next I                      ' Initialize row array
L = 0 : [.GPK](N,N)                                       ' Call sub to populate G
GENPERM = G                                               ' Return function value
End Function                                              ' End function
Mr. Programmer
AOO 4.1.7 Build 9800, MacOS 13.7.8, iMac Intel.   The locale for any menus or Calc formulas in my posts is English (USA).
Locked