Unique Combinations From a Multiset Using Crystal
I presented formula-based versions of our Unique Combinations algorithm using Tcl/Tk and GO in parts 2 and 3 of this "Multiset Combinations" series, respectively. I decided to delve a little deeper into the Crystal programming language, and this seemed like the perfect opportunity to do so, considering these recent posts on Multiset Combinations.
Crystal generates a compiled solution, and we can adapt our GO code (following the original Tcl/Tk script) using Crystal. Again, for the sake of consistency, the output of this code replicates the scripted Tcl version presented in part 2 of this series.
I was pleasantly surprised by the results. The Crystal code execution times were comparably faster than using the same algorithm written in either C or Go. It is worth noting that we took some liberties in using some of Crystal's language features that we didn't consider doing when writing the code in C or Go.
The Code
Everything in Crystal is an object, unlike Tcl/Tk, where everything is a string. The Crystal code is expressive, easy to read, and easy to follow.
The execution time of this program using Crystal is 0.011646 seconds. Crystal's execution speed was significantly better than code written in C and GO, where execution times measured 0.069000 and 0.050129, respectively.
# Unique Combinations - Multiset data
# July 16, 2022
p "Unique Combinations in Crystal"
elapsed_time = Time.measure do
# This monotonic clock should always be used for measuring elapsed time.
time_start = Time.monotonic
puts time_start
items = ["A", "B", "C", "D"]
count = [4, 3, 2, 1]
print "Items: #{items}\n"
print "Count: #{count}\n"
choices = count.map {|n| n + 1}
print "choices: #{choices}\n"
sequence = count.map {|n| 0}
print "sequence: #{sequence}\n"
combinations = choices.product
sumALL = choices.sum
indexWidth = (combinations.to_s).size # =>
sumWidth = (sumALL.to_s).size
sequenceWidth = "#{sequence}".size
printf("indexWidth = %d\n", indexWidth)
printf("sumWidth = %d\n", sumWidth)
printf("combinations = %d\n", combinations)
printf("sumALL = %d\n", sumALL)
#----------< Print the Header >----------
printf("-------- %s---%s: | ", "-"*sequenceWidth, "-"*indexWidth)
choices.each do |k|
printf("%*s", k, "-"*k)
end
printf(" | %*s: %*s |\n", indexWidth, "-", sumALL, "-"*sumALL)
#-----------< Printed Header >-----------
#We could use: while i < combinations
# Crystal's range data type is just as effective
# and easy to use.
(0...combinations).each do |i|
sequenceSum = 0
idivStep = i
sequence[0] = i % choices[0]
sequenceSum += sequence[0]
j = 0
while j < count.size-1
idivStep //= choices[j]
modStep = idivStep % choices[j]
j += 1
sequence[j] = idivStep % choices[j]
sequenceSum += sequence[j]
end
# Process the data
# Sequence index and sequence counts
printf("Sequence %*d = #{sequence}: | ", indexWidth, i)
# Items by count
(0...sequence.size).each do |k|
printf("%*s", choices[k], items[k]*sequence[k])
end
# Sum of sequence counts and "dash graph"
printf(" | %*d: %*s |\n", indexWidth, sequence.sum, sumALL, "-"*sequence.sum)
end
#----------------------------------------------------------------------------
time_elapsed = Time.monotonic - time_start
printf("Program Terminated Normally! Seconds: %f\n", (time_elapsed.nanoseconds)/1_000_000_000)
end
## print the results for Time.measure
printf("Program elapsed time (seconds): %f\n", elapsed_time.nanoseconds/1_000_000_000)
Code Output
The output format replicates the format of our Tcl/Tk and GO implementations. You will also note from the output below that the execution time was even faster than reported above.
"Unique Combinations in Crystal"
1.08:25:44.188034354
Items: ["A", "B", "C", "D"]
Count: [4, 3, 2, 1]
choices: [5, 4, 3, 2]
sequence: [0, 0, 0, 0]
indexWidth = 3
sumWidth = 2
combinations = 120
sumALL = 14
-------- ------------------: | -------------- | -: -------------- |
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! Seconds: 0.009277
Program elapsed time (seconds): 0.009312
Measuring Performance
Crystal's Time.measure function makes it easy to measure the performance of a given program or segment. We used this statement to "wrap" and measure the execution time of the whole program.
elapsed_time = Time.measure do
#...
# Code to execute goes HERE!
#...
end
## print the results for Time.measure
printf("Program elapsed time (seconds): %f\n", elapsed_time.nanoseconds/1_000_000_000)
We also used the Time.monotonic function to demonstrate an alternate means of measuring execution time.
time_start = Time.monotonic
#...
# Code to execute goes HERE!
#...
time_elapsed = Time.monotonic - time_start
printf("Program Terminated Normally! Seconds: %f\n", (time_elapsed.nanoseconds)/1_000_000_000)
The Time function provides various options to display and perform date and time calculations.