Multiset Combinations - Part 1

What is a multiset?

A Multiset contains one or more groups of like elements or items. For example, AAAA BBB CC D is a multiset comprised of four groups of letters.

How many Unique Combinations?

The number of unique combinations is the product of the number of choices we have for each letter, where not choosing a letter is also a good choice.

The number of choices for each letter in "AAAA BBB CC D" is 5, 4, 3, and 2, respectively. The number of unique combinations is 120, which is the product of 543*2.

Multiset Data Structure

We can represent this data using an array, a dictionary, or a list. However, for the sake of simplicity, we will use Tcl's list data structure to describe the multiset as follows:

set list_Items [list A B C D]
set list_Count [list 4 3 2 1]

Using two separate lists allows us to focus on the steps required to create the combination and to simplify the calculations.

How To Get ALL Combinations

We use two nested for loop structures to create a complete list of unique combinations. The outer loop iterates over the total number of choices while the inner loop generates the unique combination for the current iteration. In essence, the loop works similar to an odometer where the item count is used to determine when the "rollover" should occur. This will become clear when you run the code below.

Unique Combinations - Code

# Unique Combinations - Multiset data
# 2022-06-13

set list_Items [list A B C D]
set list_Count [list 4 3 2 1]
set list_Index [list 0 0 0 0]

set choices 1
for {set i 0} {$i < [llength $list_Count]} {incr i} {
    set counter [expr { [lindex $list_Count $i] + 1}]
    set choices [expr { $choices * $counter}]
}

puts "choices = $choices"

for {set i 0} {$i < $choices} {incr i} {
    # The first data set combination is ALL ZEROES
    #
    # Process the data set
    #   Display the data set combination - Default is console.
    #   We could also create a file to save the information
    #   format formatString ?arg arg ...?
    #
    puts "[format %0*d: [string length $choices] [expr {$i + 1}]]  $list_Index"
    #
    #       ...
    #       ...

    # Get the next data set combination
    for {set k 0} {$k < [llength $list_Items]} {incr k} {
        # puts "[lindex $list_Index $k] == [lindex $list_Count $k]"
        if { [lindex $list_Index $k] == [lindex $list_Count $k] } {
            # puts "They are EQUAL"
            lset list_Index $k 0
        } else {
            # puts "They are NOT EQUAL"
            lset list_Index $k [expr {[lindex $list_Index $k] + 1}]
            # puts "$list_Index"
            break
        }
    }
    # list_Index contains the new data set.
    # Loop to Display, Process, and Get the NEXT data set combination.
}

puts "Program Terminated Normally!"

Program output

The program outputs the total number of choices and a complete list of unique combinations followed by the "Program Terminated Normally" message.

Each line begins with a "solution index" followed by the letter counts that comprise the unique combination. For example, 120: 4 3 2 1 has a solution index of 120 comprised of 4 A's, 3 B's, 2 C's, and 1 D.

choices = 120
001:  0 0 0 0
002:  1 0 0 0
003:  2 0 0 0
004:  3 0 0 0
005:  4 0 0 0
006:  0 1 0 0
007:  1 1 0 0
      .
      .
      .
117:  1 3 2 1
118:  2 3 2 1
119:  3 3 2 1
120:  4 3 2 1
Program Terminated Normally!

Next Steps

You'll notice I left space to "process data." To be consistent with our example, we could easily print the letter combinations in this area. We'll get a little more creative in part 2 of this series where we will present a formula-driven method to calculate the unique combination for any given solution index.