Unique Combinations with Tcl

Redge Shepherd — Sun, 26 Jun 2022 20:17:46 +0000

Background

Using Tcl to list all the unique combinations for items in a given multiset. The items and corresponding number of each item are contained in two separate lists: list_Items and list_Count.

Our code assumes the items consist of the letters A, B, C, and D where each has a quantity of 4, 3, 2, and 1, respectively. In other words, we want to know and display the total number of unique combinations from the multiset "AAAABBBCCD"

We simply display the combination or count sequence to simulate a "process" after calculating the sequence of counts. I applied this approach to determine optimal cut sequences for mixed lengths of materials.

While the example here is very simple, I use Tcl as a rapid prototyping language before delving too far using a compiled language.

Yes, I could've written this routine in any number of languages. The materials optimization I referred to earlier was written entirely in Fortran and it is screamingly fast.

The code

I defer an in-depth explanation to the comments in the code.

# Unique Combinations - Multiset data
# AAAA BBB CC D
# 2022-06-18

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

# Calculate the total number of unique combinations
# Create a list containing the number of CHOICES per Item
# Create a list to manage the unique combination
# Note:  lappend creates a list if it does not exist.

# Version 2 (2022-06-18)
set choices 1
# Calculate the sum of all counts to be used for the field width of SUM
set sum_ALL 0

for {set i 0} {$i < [llength $list_Count]} {incr i} {
    # Get the count of items from list_Count, add 1 to the value and
    # append "number of choices" to list_Choices
    lappend list_Choices [expr { [lindex $list_Count $i] + 1}]
    # Set up a list to hold the unique combination generated by our code.
    lappend list_Index 0
    # Calculate new value of choices
    set choices [expr { $choices * [lindex $list_Choices $i] }]
    set sum_ALL [expr { $sum_ALL + [lindex $list_Count $i] }]
}

puts "choices = $choices"
puts "list_Choices = $list_Choices"

#------------------------------------------------------------------#
# We use "i" to serve as our counter and convert it to a unique
# combination.
# Version 2 (2022-06-15)
#
# We'll print a "prettier" table this time.
set dash "-"
    puts -nonewline [format "%*s:  " [string length $choices] \
                                     [string repeat $dash [string length $choices]]]
    puts -nonewline [format "%*s " [expr {[llength $list_Index]*2 - 1} ] \
                       [string repeat $dash [expr {[llength $list_Index]*2 - 1}]]]
    for {set m 0} { $m < [llength $list_Index] } { incr m } {
        puts -nonewline [format "  %-*s" [lindex $list_Count $m] \
                                        [string repeat $dash [lindex $list_Count $m]]]
    }
    puts -nonewline [format " | %*s:  " [string length $sum_ALL] \
                                         [string repeat $dash [string length $sum_ALL]]]
    puts [format "%*s | " $sum_ALL [string repeat $dash $sum_ALL]]

for {set i 0} {$i < $choices} {incr i} {
    # The first data set combination is ALL ZEROES

    # Convert the variable "i" to a unique combination.
    # Get the data set combination
    # The first element of the solution is the "mod" of the index "i."
    # list_Choices contains each item's number of choices (Count of elements + 1).

    # We use the "mod" and "div" commands to convert "i" into a combination
    # derived from the available choices we have for each letter.
    # The process is similar to discerning the digits in our base ten numbering
    # system to isolate the 1's, 10's, 100's, 1000's and so on.

    #---------< This is the core "engine" that is doing the work >---------#

    set div_Step $i

    set list_Length [llength $list_Items]

    # We know the first "count" is simply the mod and we can set it
    # immediately.  We also know that the result is the first element
    # in our count sequence, so, for the sake of speed of execution,
    # we're using 0 instead of setting and using a variable.
    # 
    lset list_Index 0 [expr {$div_Step % [lindex $list_Choices 0]}]

    # j points to the next count
    # k points to the initial count

    for {set j 1; set k 0} {$j < $list_Length} {incr j; incr k} {
        # div div_Step by the previous number of choices
        set div_Step       [expr {$div_Step / [lindex $list_Choices $k]}]
        # mod div_Step by the current number of choices
        lset list_Index $j [expr {$div_Step % [lindex $list_Choices $j]}]
    }

    #----------------------< Process the DATA Set  >-----------------------#
    # list_Index contains the unique combination data set.
    # Display the data set combination - Default is the console.
    # We could also create a file to save the information
    # format formatString ?arg arg ...?

    puts -nonewline "[format "%0*d:  %s" [string length $choices] $i  $list_Index]"
    for {set m 0} { $m < [llength $list_Index] } { incr m } {
        puts -nonewline "  [format %*s [lindex $list_Count $m] [string repeat [lindex $list_Items $m] [lindex $list_Index $m]]]"
    }

    # Process the data set
    # Calculate the sum of the counts
    set sum 0
    for {set m 0} { $m < [llength $list_Index] } { incr m } {
        set sum [expr {$sum + [lindex $list_Index $m]}]
    }

    puts "[format " | %*d:  %*s |" [string length $sum_ALL] $sum $sum_ALL [string repeat $dash $sum]]"
    #       ...
    #       ...
    # Process ends

    # Loop to Get the NEXT data set combination
}

puts "Program Terminated Normally!"

Run the program using the tclsh interpreter. The output generated by the program should appear in your console as follows:

## The Output

choices = 120
list_Choices = 5 4 3 2
---:  -------   ----  ---  --  - | --:  ---------- |
000:  0 0 0 0                   |  0:             |
001:  1 0 0 0     A             |  1:           - |
002:  2 0 0 0    AA             |  2:          -- |
003:  3 0 0 0   AAA             |  3:         --- |
004:  4 0 0 0  AAAA             |  4:        ---- |
005:  0 1 0 0          B        |  1:           - |
006:  1 1 0 0     A    B        |  2:          -- |
007:  2 1 0 0    AA    B        |  3:         --- |
008:  3 1 0 0   AAA    B        |  4:        ---- |
009:  4 1 0 0  AAAA    B        |  5:       ----- |
010:  0 2 0 0         BB        |  2:          -- |
011:  1 2 0 0     A   BB        |  3:         --- |
012:  2 2 0 0    AA   BB        |  4:        ---- |
013:  3 2 0 0   AAA   BB        |  5:       ----- |
014:  4 2 0 0  AAAA   BB        |  6:      ------ |
015:  0 3 0 0        BBB        |  3:         --- |
016:  1 3 0 0     A  BBB        |  4:        ---- |
017:  2 3 0 0    AA  BBB        |  5:       ----- |
018:  3 3 0 0   AAA  BBB        |  6:      ------ |
019:  4 3 0 0  AAAA  BBB        |  7:     ------- |
020:  0 0 1 0              C    |  1:           - |
021:  1 0 1 0     A        C    |  2:          -- |
022:  2 0 1 0    AA        C    |  3:         --- |
023:  3 0 1 0   AAA        C    |  4:        ---- |
024:  4 0 1 0  AAAA        C    |  5:       ----- |
025:  0 1 1 0          B   C    |  2:          -- |
026:  1 1 1 0     A    B   C    |  3:         --- |
027:  2 1 1 0    AA    B   C    |  4:        ---- |
028:  3 1 1 0   AAA    B   C    |  5:       ----- |
029:  4 1 1 0  AAAA    B   C    |  6:      ------ |
030:  0 2 1 0         BB   C    |  3:         --- |
031:  1 2 1 0     A   BB   C    |  4:        ---- |
032:  2 2 1 0    AA   BB   C    |  5:       ----- |
033:  3 2 1 0   AAA   BB   C    |  6:      ------ |
034:  4 2 1 0  AAAA   BB   C    |  7:     ------- |
035:  0 3 1 0        BBB   C    |  4:        ---- |
036:  1 3 1 0     A  BBB   C    |  5:       ----- |
037:  2 3 1 0    AA  BBB   C    |  6:      ------ |
038:  3 3 1 0   AAA  BBB   C    |  7:     ------- |
039:  4 3 1 0  AAAA  BBB   C    |  8:    -------- |
040:  0 0 2 0             CC    |  2:          -- |
041:  1 0 2 0     A       CC    |  3:         --- |
042:  2 0 2 0    AA       CC    |  4:        ---- |
043:  3 0 2 0   AAA       CC    |  5:       ----- |
044:  4 0 2 0  AAAA       CC    |  6:      ------ |
045:  0 1 2 0          B  CC    |  3:         --- |
046:  1 1 2 0     A    B  CC    |  4:        ---- |
047:  2 1 2 0    AA    B  CC    |  5:       ----- |
048:  3 1 2 0   AAA    B  CC    |  6:      ------ |
049:  4 1 2 0  AAAA    B  CC    |  7:     ------- |
050:  0 2 2 0         BB  CC    |  4:        ---- |
051:  1 2 2 0     A   BB  CC    |  5:       ----- |
052:  2 2 2 0    AA   BB  CC    |  6:      ------ |
053:  3 2 2 0   AAA   BB  CC    |  7:     ------- |
054:  4 2 2 0  AAAA   BB  CC    |  8:    -------- |
055:  0 3 2 0        BBB  CC    |  5:       ----- |
056:  1 3 2 0     A  BBB  CC    |  6:      ------ |
057:  2 3 2 0    AA  BBB  CC    |  7:     ------- |
058:  3 3 2 0   AAA  BBB  CC    |  8:    -------- |
059:  4 3 2 0  AAAA  BBB  CC    |  9:   --------- |
060:  0 0 0 1                 D |  1:           - |
061:  1 0 0 1     A           D |  2:          -- |
062:  2 0 0 1    AA           D |  3:         --- |
063:  3 0 0 1   AAA           D |  4:        ---- |
064:  4 0 0 1  AAAA           D |  5:       ----- |
065:  0 1 0 1          B      D |  2:          -- |
066:  1 1 0 1     A    B      D |  3:         --- |
067:  2 1 0 1    AA    B      D |  4:        ---- |
068:  3 1 0 1   AAA    B      D |  5:       ----- |
069:  4 1 0 1  AAAA    B      D |  6:      ------ |
070:  0 2 0 1         BB      D |  3:         --- |
071:  1 2 0 1     A   BB      D |  4:        ---- |
072:  2 2 0 1    AA   BB      D |  5:       ----- |
073:  3 2 0 1   AAA   BB      D |  6:      ------ |
074:  4 2 0 1  AAAA   BB      D |  7:     ------- |
075:  0 3 0 1        BBB      D |  4:        ---- |
076:  1 3 0 1     A  BBB      D |  5:       ----- |
077:  2 3 0 1    AA  BBB      D |  6:      ------ |
078:  3 3 0 1   AAA  BBB      D |  7:     ------- |
079:  4 3 0 1  AAAA  BBB      D |  8:    -------- |
080:  0 0 1 1              C  D |  2:          -- |
081:  1 0 1 1     A        C  D |  3:         --- |
082:  2 0 1 1    AA        C  D |  4:        ---- |
083:  3 0 1 1   AAA        C  D |  5:       ----- |
084:  4 0 1 1  AAAA        C  D |  6:      ------ |
085:  0 1 1 1          B   C  D |  3:         --- |
086:  1 1 1 1     A    B   C  D |  4:        ---- |
087:  2 1 1 1    AA    B   C  D |  5:       ----- |
088:  3 1 1 1   AAA    B   C  D |  6:      ------ |
089:  4 1 1 1  AAAA    B   C  D |  7:     ------- |
090:  0 2 1 1         BB   C  D |  4:        ---- |
091:  1 2 1 1     A   BB   C  D |  5:       ----- |
092:  2 2 1 1    AA   BB   C  D |  6:      ------ |
093:  3 2 1 1   AAA   BB   C  D |  7:     ------- |
094:  4 2 1 1  AAAA   BB   C  D |  8:    -------- |
095:  0 3 1 1        BBB   C  D |  5:       ----- |
096:  1 3 1 1     A  BBB   C  D |  6:      ------ |
097:  2 3 1 1    AA  BBB   C  D |  7:     ------- |
098:  3 3 1 1   AAA  BBB   C  D |  8:    -------- |
099:  4 3 1 1  AAAA  BBB   C  D |  9:   --------- |
100:  0 0 2 1             CC  D |  3:         --- |
101:  1 0 2 1     A       CC  D |  4:        ---- |
102:  2 0 2 1    AA       CC  D |  5:       ----- |
103:  3 0 2 1   AAA       CC  D |  6:      ------ |
104:  4 0 2 1  AAAA       CC  D |  7:     ------- |
105:  0 1 2 1          B  CC  D |  4:        ---- |
106:  1 1 2 1     A    B  CC  D |  5:       ----- |
107:  2 1 2 1    AA    B  CC  D |  6:      ------ |
108:  3 1 2 1   AAA    B  CC  D |  7:     ------- |
109:  4 1 2 1  AAAA    B  CC  D |  8:    -------- |
110:  0 2 2 1         BB  CC  D |  5:       ----- |
111:  1 2 2 1     A   BB  CC  D |  6:      ------ |
112:  2 2 2 1    AA   BB  CC  D |  7:     ------- |
113:  3 2 2 1   AAA   BB  CC  D |  8:    -------- |
114:  4 2 2 1  AAAA   BB  CC  D |  9:   --------- |
115:  0 3 2 1        BBB  CC  D |  6:      ------ |
116:  1 3 2 1     A  BBB  CC  D |  7:     ------- |
117:  2 3 2 1    AA  BBB  CC  D |  8:    -------- |
118:  3 3 2 1   AAA  BBB  CC  D |  9:   --------- |
119:  4 3 2 1  AAAA  BBB  CC  D | 10:  ---------- |
Program Terminated Normally!

DEV Community: Redge Shepherd

Unique Combinations with Tcl

Background

The code