Search for a command to run...
Calculating an INDEX from a Count Sequence
I have over 40 years of programming experience using a variety of languages over the course of my career to develop real-time solutions for real-world problems.
Keyboards connect us to the world and, as a keyboard enthusiast, I am searching for the ideal keyboard.
No comments yet. Be the first to comment.
Looking at an article for the book “Gist of Go: Concurrency,” I also stumbled across a reference to “High-precision date/time in SQLite” written by the same author, Anton Zhiyanov. I use SQLite in man
Happy 10th Anniversary - RUST!
Login failed. It appears you are offline
Modern Fortran: Tricks of the Software Engineering Trade by Damian Rouson Sometimes I think I'm one of the few programmers routinely using Fortran long after my Engineering studies too many years ago. As such, I'm pleasantly surprised when a new book...
Make GIT a Habit
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.
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.
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"
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.
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:
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)
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.
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
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.