Table of contents
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.