Multiset Combinations - Part 3

Unique Combinations From A Multiset Using GO

I presented a formula-based version of a Unique Combinations algorithm in "Multiset Combinations - Part 2." This post presents a version of the same algorithm in GO. The names of the variables are more meaningful in this version, but the expressions and execution sequences are similar to the version presented in Tcl.

This application was simple enough to present a simple version in GO instead of using a scripted language like Tcl. The bonus, of course, is a compiled solution that runs extremely fast. The downside is hard-coded data in the program itself.

For the sake of consistency, the output of this code replicates the scripted Tcl version presented in Part 2 of this series.

We still need to create an interface that will allow us to enter a dataset of any size. At least we know the algorithm works even if we're not taking advantage of some of GO's better features.

The Code

// Unique Combinations - Multiset data
// July 2, 2022

package main

import (
    "fmt"
    "strings"
)

func main() {
    fmt.Println("Unique Combinations in GO")
    defer fmt.Println("\nProgram Terminated Normally")

    // Arrays use a contiguous block of memory
    var items = [4]string{"A", "B", "C", "D"}
    var count = [4]int{4, 3, 2, 1}

    fmt.Printf("items:  %v\n", items)
    fmt.Printf("count:  %v\n", count)

    // Slices are more flexible than arrays and can be
    // sized using a variable instead of hard coding.

    // initialize choices and sequence
    // choices hold the number of choices per item
    // sequence holds the count of each item to form
    // a unique combination.

    var choices = make([]int, len(count), len(count))
    var sequence = make([]int, len(count), len(count))

    // We can use %v, %+v, or %#v to format output
    // +v displays the values in a clean format.
    fmt.Printf("Sequence:  %+v\n", sequence)

    // Calculate the total number of possible combinations
    // and the sum of the counts
    combinations := 1
    sumALL := 0
    for i := 0; i < len(count); i++ {
        combinations *= count[i] + 1
        sumALL += count[i]
        choices[i] = count[i] + 1
    }

    sequenceWidth := len(fmt.Sprintf("%d", combinations))
    fmt.Printf("sequenceWidth = %d\n", sequenceWidth)

    fmt.Printf("Combinations = %d\n", combinations)
    fmt.Printf("Sum Counts = %d\n", sumALL)
    fmt.Printf("Choices: = %+v\n", choices)

    // Set up the formatting to make things look organized
    // Format the header area
    //-------------------------------------------------------------------------------------------------------
    // Format the "sequence and counts" area
    comboWidth := len(fmt.Sprintf("%v", sequence))
    fmt.Printf("---------%s = %s:  | ", strings.Repeat("-", sequenceWidth), strings.Repeat("-", comboWidth))

    // Format the "items" area
    for m := 0; m < len(sequence); m++ {
        fmt.Printf("%*s ", count[m], strings.Repeat("-", count[m]))
    }

    // Format the "sum" and "dash graph" zone
    sumWidth := len(fmt.Sprintf("%d", sumALL))
    fmt.Printf("| %s:  %s |\n", strings.Repeat("-", sumWidth), strings.Repeat("-", sumALL))
    //-------------------------------------------------------------------------------------------------------

    // Calculate combinations
    // The outer loop controls the total number of iterations required

    for i := 0; i < combinations; i++ {
        divStep := i
        sequenceSum := 0
        sequence[0] = i % choices[0]
        sequenceSum += sequence[0]

        for j := 0; j < len(choices)-1; {
            // fmt.Printf("In the loop %d", i)
            divStep /= choices[j]
            j++
            sequence[j] = divStep % choices[j]
            sequenceSum += sequence[j]
        }

        // Process the data count sequence here!
        fmt.Printf("Sequence %*d = %v:  | ", sequenceWidth, i, sequence)
        // Build the list of "items" to display
        //var b bytes.Buffer
        for m := 0; m < len(sequence); m++ {
            fmt.Printf("%*s ", count[m], strings.Repeat(items[m], sequence[m]))
        }
        fmt.Printf("| %*d:  %*s |\n", sumWidth, sequenceSum, sumALL, strings.Repeat("-", sequenceSum))
    }
}

Output

Unique Combinations in GO
items:  [A B C D]
count:  [4 3 2 1]
Choices:.  [0 0 0 0]
Sequence:  [0 0 0 0]
sequenceWidth = 3
Combinations = 120
Sum Counts = 10
Choices: = [5 4 3 2]
------------ = ---------:  | ---- --- -- - | --:  ---------- |
Sequence   0 = [0 0 0 0]:  |               |  0:             |
Sequence   1 = [1 0 0 0]:  |    A          |  1:           - |
Sequence   2 = [2 0 0 0]:  |   AA          |  2:          -- |
Sequence   3 = [3 0 0 0]:  |  AAA          |  3:         --- |
Sequence   4 = [4 0 0 0]:  | AAAA          |  4:        ---- |
Sequence   5 = [0 1 0 0]:  |        B      |  1:           - |
Sequence   6 = [1 1 0 0]:  |    A   B      |  2:          -- |
Sequence   7 = [2 1 0 0]:  |   AA   B      |  3:         --- |
Sequence   8 = [3 1 0 0]:  |  AAA   B      |  4:        ---- |
Sequence   9 = [4 1 0 0]:  | AAAA   B      |  5:       ----- |
Sequence  10 = [0 2 0 0]:  |       BB      |  2:          -- |
Sequence  11 = [1 2 0 0]:  |    A  BB      |  3:         --- |
Sequence  12 = [2 2 0 0]:  |   AA  BB      |  4:        ---- |
Sequence  13 = [3 2 0 0]:  |  AAA  BB      |  5:       ----- |
Sequence  14 = [4 2 0 0]:  | AAAA  BB      |  6:      ------ |
Sequence  15 = [0 3 0 0]:  |      BBB      |  3:         --- |
Sequence  16 = [1 3 0 0]:  |    A BBB      |  4:        ---- |
Sequence  17 = [2 3 0 0]:  |   AA BBB      |  5:       ----- |
Sequence  18 = [3 3 0 0]:  |  AAA BBB      |  6:      ------ |
Sequence  19 = [4 3 0 0]:  | AAAA BBB      |  7:     ------- |
Sequence  20 = [0 0 1 0]:  |           C   |  1:           - |
Sequence  21 = [1 0 1 0]:  |    A      C   |  2:          -- |
Sequence  22 = [2 0 1 0]:  |   AA      C   |  3:         --- |
Sequence  23 = [3 0 1 0]:  |  AAA      C   |  4:        ---- |
Sequence  24 = [4 0 1 0]:  | AAAA      C   |  5:       ----- |
Sequence  25 = [0 1 1 0]:  |        B  C   |  2:          -- |
Sequence  26 = [1 1 1 0]:  |    A   B  C   |  3:         --- |
Sequence  27 = [2 1 1 0]:  |   AA   B  C   |  4:        ---- |
Sequence  28 = [3 1 1 0]:  |  AAA   B  C   |  5:       ----- |
Sequence  29 = [4 1 1 0]:  | AAAA   B  C   |  6:      ------ |
Sequence  30 = [0 2 1 0]:  |       BB  C   |  3:         --- |
Sequence  31 = [1 2 1 0]:  |    A  BB  C   |  4:        ---- |
Sequence  32 = [2 2 1 0]:  |   AA  BB  C   |  5:       ----- |
Sequence  33 = [3 2 1 0]:  |  AAA  BB  C   |  6:      ------ |
Sequence  34 = [4 2 1 0]:  | AAAA  BB  C   |  7:     ------- |
Sequence  35 = [0 3 1 0]:  |      BBB  C   |  4:        ---- |
Sequence  36 = [1 3 1 0]:  |    A BBB  C   |  5:       ----- |
Sequence  37 = [2 3 1 0]:  |   AA BBB  C   |  6:      ------ |
Sequence  38 = [3 3 1 0]:  |  AAA BBB  C   |  7:     ------- |
Sequence  39 = [4 3 1 0]:  | AAAA BBB  C   |  8:    -------- |
Sequence  40 = [0 0 2 0]:  |          CC   |  2:          -- |
Sequence  41 = [1 0 2 0]:  |    A     CC   |  3:         --- |
Sequence  42 = [2 0 2 0]:  |   AA     CC   |  4:        ---- |
Sequence  43 = [3 0 2 0]:  |  AAA     CC   |  5:       ----- |
Sequence  44 = [4 0 2 0]:  | AAAA     CC   |  6:      ------ |
Sequence  45 = [0 1 2 0]:  |        B CC   |  3:         --- |
Sequence  46 = [1 1 2 0]:  |    A   B CC   |  4:        ---- |
Sequence  47 = [2 1 2 0]:  |   AA   B CC   |  5:       ----- |
Sequence  48 = [3 1 2 0]:  |  AAA   B CC   |  6:      ------ |
Sequence  49 = [4 1 2 0]:  | AAAA   B CC   |  7:     ------- |
Sequence  50 = [0 2 2 0]:  |       BB CC   |  4:        ---- |
Sequence  51 = [1 2 2 0]:  |    A  BB CC   |  5:       ----- |
Sequence  52 = [2 2 2 0]:  |   AA  BB CC   |  6:      ------ |
Sequence  53 = [3 2 2 0]:  |  AAA  BB CC   |  7:     ------- |
Sequence  54 = [4 2 2 0]:  | AAAA  BB CC   |  8:    -------- |
Sequence  55 = [0 3 2 0]:  |      BBB CC   |  5:       ----- |
Sequence  56 = [1 3 2 0]:  |    A BBB CC   |  6:      ------ |
Sequence  57 = [2 3 2 0]:  |   AA BBB CC   |  7:     ------- |
Sequence  58 = [3 3 2 0]:  |  AAA BBB CC   |  8:    -------- |
Sequence  59 = [4 3 2 0]:  | AAAA BBB CC   |  9:   --------- |
Sequence  60 = [0 0 0 1]:  |             D |  1:           - |
Sequence  61 = [1 0 0 1]:  |    A        D |  2:          -- |
Sequence  62 = [2 0 0 1]:  |   AA        D |  3:         --- |
Sequence  63 = [3 0 0 1]:  |  AAA        D |  4:        ---- |
Sequence  64 = [4 0 0 1]:  | AAAA        D |  5:       ----- |
Sequence  65 = [0 1 0 1]:  |        B    D |  2:          -- |
Sequence  66 = [1 1 0 1]:  |    A   B    D |  3:         --- |
Sequence  67 = [2 1 0 1]:  |   AA   B    D |  4:        ---- |
Sequence  68 = [3 1 0 1]:  |  AAA   B    D |  5:       ----- |
Sequence  69 = [4 1 0 1]:  | AAAA   B    D |  6:      ------ |
Sequence  70 = [0 2 0 1]:  |       BB    D |  3:         --- |
Sequence  71 = [1 2 0 1]:  |    A  BB    D |  4:        ---- |
Sequence  72 = [2 2 0 1]:  |   AA  BB    D |  5:       ----- |
Sequence  73 = [3 2 0 1]:  |  AAA  BB    D |  6:      ------ |
Sequence  74 = [4 2 0 1]:  | AAAA  BB    D |  7:     ------- |
Sequence  75 = [0 3 0 1]:  |      BBB    D |  4:        ---- |
Sequence  76 = [1 3 0 1]:  |    A BBB    D |  5:       ----- |
Sequence  77 = [2 3 0 1]:  |   AA BBB    D |  6:      ------ |
Sequence  78 = [3 3 0 1]:  |  AAA BBB    D |  7:     ------- |
Sequence  79 = [4 3 0 1]:  | AAAA BBB    D |  8:    -------- |
Sequence  80 = [0 0 1 1]:  |           C D |  2:          -- |
Sequence  81 = [1 0 1 1]:  |    A      C D |  3:         --- |
Sequence  82 = [2 0 1 1]:  |   AA      C D |  4:        ---- |
Sequence  83 = [3 0 1 1]:  |  AAA      C D |  5:       ----- |
Sequence  84 = [4 0 1 1]:  | AAAA      C D |  6:      ------ |
Sequence  85 = [0 1 1 1]:  |        B  C D |  3:         --- |
Sequence  86 = [1 1 1 1]:  |    A   B  C D |  4:        ---- |
Sequence  87 = [2 1 1 1]:  |   AA   B  C D |  5:       ----- |
Sequence  88 = [3 1 1 1]:  |  AAA   B  C D |  6:      ------ |
Sequence  89 = [4 1 1 1]:  | AAAA   B  C D |  7:     ------- |
Sequence  90 = [0 2 1 1]:  |       BB  C D |  4:        ---- |
Sequence  91 = [1 2 1 1]:  |    A  BB  C D |  5:       ----- |
Sequence  92 = [2 2 1 1]:  |   AA  BB  C D |  6:      ------ |
Sequence  93 = [3 2 1 1]:  |  AAA  BB  C D |  7:     ------- |
Sequence  94 = [4 2 1 1]:  | AAAA  BB  C D |  8:    -------- |
Sequence  95 = [0 3 1 1]:  |      BBB  C D |  5:       ----- |
Sequence  96 = [1 3 1 1]:  |    A BBB  C D |  6:      ------ |
Sequence  97 = [2 3 1 1]:  |   AA BBB  C D |  7:     ------- |
Sequence  98 = [3 3 1 1]:  |  AAA BBB  C D |  8:    -------- |
Sequence  99 = [4 3 1 1]:  | AAAA BBB  C D |  9:   --------- |
Sequence 100 = [0 0 2 1]:  |          CC D |  3:         --- |
Sequence 101 = [1 0 2 1]:  |    A     CC D |  4:        ---- |
Sequence 102 = [2 0 2 1]:  |   AA     CC D |  5:       ----- |
Sequence 103 = [3 0 2 1]:  |  AAA     CC D |  6:      ------ |
Sequence 104 = [4 0 2 1]:  | AAAA     CC D |  7:     ------- |
Sequence 105 = [0 1 2 1]:  |        B CC D |  4:        ---- |
Sequence 106 = [1 1 2 1]:  |    A   B CC D |  5:       ----- |
Sequence 107 = [2 1 2 1]:  |   AA   B CC D |  6:      ------ |
Sequence 108 = [3 1 2 1]:  |  AAA   B CC D |  7:     ------- |
Sequence 109 = [4 1 2 1]:  | AAAA   B CC D |  8:    -------- |
Sequence 110 = [0 2 2 1]:  |       BB CC D |  5:       ----- |
Sequence 111 = [1 2 2 1]:  |    A  BB CC D |  6:      ------ |
Sequence 112 = [2 2 2 1]:  |   AA  BB CC D |  7:     ------- |
Sequence 113 = [3 2 2 1]:  |  AAA  BB CC D |  8:    -------- |
Sequence 114 = [4 2 2 1]:  | AAAA  BB CC D |  9:   --------- |
Sequence 115 = [0 3 2 1]:  |      BBB CC D |  6:      ------ |
Sequence 116 = [1 3 2 1]:  |    A BBB CC D |  7:     ------- |
Sequence 117 = [2 3 2 1]:  |   AA BBB CC D |  8:    -------- |
Sequence 118 = [3 3 2 1]:  |  AAA BBB CC D |  9:   --------- |
Sequence 119 = [4 3 2 1]:  | AAAA BBB CC D | 10:  ---------- |

Program Terminated Normally

Next Steps

I did not present any error checking and will have to add it when I develop the user interface.

Now that we have a means of calculating every possible combination, we need to work on an application that can put it to good use.