Multiset Combinations - Part 5

Background Introduction

Parts 2 (Tcl), 3 (GO), and 4 (Crystal) of this series presented a formula-based solution to calculate count sequences that comprise a unique data set based on a given index. To further develop our application, we calculate the index from a given count sequence.

Converting a sequence to a given index requires us to know the number of choices we have for each item in the original data set. We'll use the same data set from our previous posts expressed as follows using Tcl:

set list_items [list A B C D]
set list_count [list 4 3 2 1]

We add one to each count to determine the number of choices available for each item. Based on our "list_count," we can express the number of choices in Tcl as set list_choices [list 5 4 3 2]

The total number of choices is the product of the choices available for each element. In our case, the number of choices is the product of 5 * 4 * 3 * 2 or 120.

Calculating the Index

We'll use an example to demonstrate how to calculate the index for a given sequence. Given a count sequence of 2 3 1 1, the series of calculations becomes:

2 + 3 * (5) + 1 * (5 * 4) + 1 * (5 * 4 * 3) = 97

Referring to the table below and the calculations, you will notice a progressive index as we move from left to right:

You will also notice a growing "factorial" as we move from left to right through the sequence: 5, 5*4, 5*4*3. The letters "B," "C," and "D" appear when the index is greater than or equal to 5, 20, and 60, respectively.

TCL Script - The Code

The following Tcl script calculates the index for the Test Sequence 2 3 1 1

puts "-------------------< PART 2:  Sequence to Index >-------------------"
puts "Recreate the Original Data Set"

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

# Calculate the index from a given sequence
# Create a list containing the number of CHOICES per Item
# Note:  lappend creates a list if it does not exist.

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}]

    # 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"

# Convert a data set to an index

set test_Sequence [list 2 3 1 1]
puts "test_Sequence = $test_Sequence"

set Factorialize 1
set Sequence_SxM [lindex $test_Sequence 0]

for {set i 0; set j 1} {$j < [llength $test_Sequence]} {incr i; incr j} {
    puts "Sequence_SxM @ j = $j = $Sequence_SxM"
    set Factorialize [expr {$Factorialize * [lindex $list_Choices $i]}]
    set Sequence_SxM [expr {$Sequence_SxM + $Factorialize * [lindex $test_Sequence $j]}]
}
    puts "Sequence_SxM @ j = $j = $Sequence_SxM"

puts "test_Sequence $test_Sequence = Index $Sequence_SxM"

Crystal Code - Sequence to Index Calculation

We added the following code to the listing presented in Part 4 of this series:

    factorialize = 1
    sequence_SxM = sequence[0]

    (0...(sequence.size-1)).each do |m|
        factorialize *= choices[m]
        m += 1
        sequence_SxM = sequence_SxM + factorialize*sequence[m]
    end

    printf(" %*d |\n", indexWidth, sequence_SxM)

The result of the index calculation appears in the last column of the output.

Why Crystal?

You may be wondering why I'm presenting code written in Crystal when our focus is typically Tcl/Tk. The answer is simple. As I've mentioned in previous posts, I use Tcl/Tk for rapid program development or as a proof of concept.

TCL/Tk is a dynamic scripting language that makes it easy to make changes and see the results without having to go through the trouble of compiling the application, although crystal play diminishes this argument to a great degree.

Using crystal play provides the ability to test code snippets in a locally hosted browser application. To run the Playground, enter crystal play at the command prompt in a terminal session:

Then open your browser and enter the 127.0.0.1:8080 into the address bar of your browser:

Crystal Code - Full Code Listing

The following is a full code listing for the Crystal version of our Unique Combinations application and includes code for the newly added "index" calculation.

# Unique Combinations - Multiset data
# July 18, 2022

p "Unique Combinations in Crystal"
p "With Sequence to Index Calculation"
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 = count.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:  | ", "-"*indexWidth, "-"*sequenceWidth)
    choices.each do |k|
      printf("%*s", k, "-"*k)
    end
  printf(" | %*s:  %*s |", sumWidth, "-", sumALL, "-"*sumALL)
  printf(" %*s |\n", indexWidth, "-"*indexWidth)
  #-----------< 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]

    # The following code is replaced by the
    # range.each do loop immediately following
    #
    # 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

    (0...count.size-1).each do |j|
      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 |", sumWidth, sequence.sum, sumALL, "-"*sequence.sum)

    #--------------------------------------------------------------------------
    # Convert count sequence to an index

    factorialize = 1
    sequence_SxM = sequence[0]

    (0...(sequence.size-1)).each do |m|
        factorialize *= choices[m]
        m += 1
        sequence_SxM = sequence_SxM + factorialize*sequence[m]
    end

    printf(" %*d |\n", indexWidth, sequence_SxM)

  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)

Crystal Code - Running the Program

Run the code above in a terminal session, and the output that follows below should appear on your screen.

I am using Visual Studio Code to write Crystal applications as it readily identifies my WSL Ubuntu installation.

To run the code, enter crystal run yourfilename.cr where yourfilename.cr is the name of your Crystal file.

To compile the code, enter crystal build yourfilename.cr where yourfilename.cr is the name of your Crystal file. If the build is successful, enter ./yourfilename at the command prompt to run the program.

Crystal Code - Program Output

The following is a complete listing of the output using the above Crystal program running in a Ubuntu Linux terminal on my Windows machine.

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

Next Steps

I have yet to experiment with concurrency using Crystal, and this may present further efficiencies than demonstrated here. This is sure to be a topic for a future post.

Related Articles and Resources

• Comparing Crystal's Concurrency With That of Go (Part I) by Mohammad Molla, Jul 31, 2020.
• Comparing Crystal’s concurrency with that of Go (Part II) by Mohammad Molla, Aug 1, 2020.