Redge Shepherd
TclTk Scripts

TclTk Scripts

Multiset Combinations - Part 4

Multiset Combinations - Part 4

Formula-Based Solution In Crystal

Redge Shepherd's photo
Redge Shepherd
·Jul 18, 2022·

12 min read

Subscribe to my newsletter and never miss my upcoming articles

Table of contents

  • Unique Combinations From a Multiset Using Crystal
  • The Code
  • Code Output
  • Measuring Performance
  • Related Articles and Resources

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.

Did you find this article valuable?

Support Redge Shepherd by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this