Permutation Table

Permutations are distinct orderings of a set of items.

The six permutations of a set of three colored balls.

Permutations have all sorts of applications in the worlds of mathematics and computing. One recent example is my brute force attempt at solving the Five-House Logic Puzzle. Brute forcing this sort of puzzle requires us to test all possible permutations of a set of items.

Permutations have many potential applications in business software:

Staff Scheduling
Product Configurations
Data Analysis

Calculating Permutation Counts

The number of unique permutations for a set of n items can be computed as a factorial: n!.

For example:

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5,040
8! = 40,320
9! = 362,880

The simplest way to represent a set of unique permutations is to use numbers to represent the items and sort them in lexicographic order.

In lexicographic ordering, the first permutation is in ascending order and the last permutation is in descending order.

Generating Permutations

There are many algorithms for generating permutations, several of which are described in the Wikipedia article on permutations.

There is nothing built into VBA to generate permutations. You would have to implement one of the many algorithms within VBA to generate these values. I started down that road myself. When I did not immediately figure it out on my own, I pivoted to a different approach.

I settled on a three-part solution:

Use Python's itertools.permutations() method to generate permutations
Save the permutations into text files based on corresponding item count
Load the values from those text files into a local Permutation table

The Python Script

It's been many years since I've written much Python, so I had ChatGPT build the script to my specifications.

import itertools

def write_permutations_to_file(file_name, elements):
    with open(file_name, 'w') as file:
        for perm in itertools.permutations(elements):
            line = ' '.join(str(elem) for elem in perm) + '\n'
            file.write(line)

if __name__ == "__main__":
    elements = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    for i in range(1, len(elements) + 1):
        file_name = f"permutations_output_{i}.txt"
        write_permutations_to_file(file_name, elements[:i])
        print(f"Permutations of length {i} written to {file_name}")

The script is short and sweet.

It creates 9 files named:
permutations_output_1.txt
permutations_output_2.txt
...
permutations_output_9.txt
In each file, it creates the permutations for the number of elements embedded in the file name. For example, permutations_output_3.txt has the following contents:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
The files are created in the same folder from where the script is run.

The Access Table

I created an Access table with 12 fields:

PermutationID: Autonumber primary key
ElementCount: The number of elements in the current permutation
Sequence: The position of the current permutation within the lexicographic order
Item1 - Item9: Nine fields that hold the permutation values

Here's a sample of what the touble looks like after it has been populated:

Having fields named Item1, Item2, Item3, etc. breaks a cardinal rule of good normalized database design.

However, I think this is one of those rare situations where it makes sense to denormalize our structure. The above approach will greatly simplify how we end up using this table.

One typical downside to the above approach is that it doesn't scale well if you want to support more than x fields. In this case, I don't think it would be practical to support more than 9 fields, anyway, considering the number of records we would need for 10 items: 10! = 3,628,800.

By all means, though, if you need those records, feel free to adjust the table design, Python script, and VBA code to include them in the table.

The SQL CREATE TABLE Script

If you are interested, here's the SQL script that will build the Permutation table:

CREATE TABLE [Permutation] (
  [PermutationID] AUTOINCREMENT CONSTRAINT [PrimaryKey] PRIMARY KEY UNIQUE NOT NULL,
  [ElementCount] BYTE ,
  [Sequence] LONG ,
  [Item1] BYTE ,
  [Item2] BYTE ,
  [Item3] BYTE ,
  [Item4] BYTE ,
  [Item5] BYTE ,
  [Item6] BYTE ,
  [Item7] BYTE ,
  [Item8] BYTE ,
  [Item9] BYTE 
)

I also added a table index that I called GroupSort which is a combination of the ElementCount and Sequence fields:

The VBA Code

Below is the code I used to populate the Permutation table with the values in the Python-generated text files from above.

' ----------------------------------------------------------------
' Procedure : PopulatePermutationTable
' Date      : 8/8/2023
' Author    : Mike Wolfe
' Source    : https://nolongerset.com/permutation-table/
' Purpose   : Loop through each Python-generated permutations
'               text file and use them to populate the local
'               Permutation table.
' ----------------------------------------------------------------
Sub PopulatePermutationTable()
    Const foPermText As String = "C:\Path\To\My\Python\Files\Folder"
    
    Dim ElementCount As Byte
    For ElementCount = 1 To 9
        Debug.Print "ElementCount: "; ElementCount: DoEvents
        Dim fpPermText As String
        fpPermText = foPermText & "\permutations_output_" & ElementCount & ".txt"
        PopulatePermTblByElement ElementCount, fpPermText
        Debug.Print
    Next ElementCount
    
End Sub


' ----------------------------------------------------------------
' Procedure : PopulatePermTblByElement
' Date      : 8/8/2023
' Author    : Mike Wolfe
' Source    : https://nolongerset.com/permutation-table/
' Purpose   : Populate the local Permutation table with lines of text
'               from a text file generated via Python's
'               itertools.permutations() method.
' ----------------------------------------------------------------
Sub PopulatePermTblByElement(ElementCount As Byte, fpPermText As String)
    ' Open the file for reading
    Dim FileNum As Integer
    FileNum = FreeFile
    Open fpPermText For Input As #FileNum
    
    ' Create an array to hold each byte value from the file
    Dim Items() As String
    ReDim Items(1 To ElementCount)
        
    ' Open a recordset to append data to the table
    Dim db As DAO.Database
    Set db = CurrentDb
    
    Dim rsPerm As DAO.Recordset
    Set rsPerm = db.OpenRecordset("Permutation", dbOpenTable)
    
    ' Read each line and insert into Permutation table
    Dim Seq As Long, LineText As String
    Do Until EOF(FileNum)
        Seq = Seq + 1
        Line Input #FileNum, LineText
        
        ' Populate the array
        Items = Split(LineText, " ")
        
        ' Create a new record in the table
        With rsPerm
            .AddNew
            !ElementCount = ElementCount
            !Sequence = Seq
            Dim i As Byte
            For i = 1 To ElementCount
                .Fields("Item" & i).Value = CByte(Items(i - 1))
            Next i
            .Update
        End With
        
        'https://nolongerset.com/poor-mans-status-bar/
        If Seq Mod 1000 = 0 Then Debug.Print ".";: DoEvents
    Loop
    
    ' Close the recordset and release objects
    rsPerm.Close
    Set rsPerm = Nothing
    Set db = Nothing
    
    ' Close the file
    Close #FileNum
    
End Sub

The fully populated table contains 409,113 records:

You can see that ElementCount 9 is fully populated with 362,880 records and the final line of values is in perfect descending order: 9 8 7 6 5 4 3 2 1.

Sample Database File

Here's a database file with nothing but the Permutation table in it.

If you want to use the Permutation table but don't want to jump through all the hoops to build it yourself, this link is for you: PermutationTable.zip (5.2 MB).

Acknowledgements

One or more code samples generated with the help of ChatGPT