Calculating the cardinality of ordered n-tuple
Given a tuple of 4 elements, if each of the elements can have the same amount of different position as there is elements in the tuple. We can calculate the cardinality of the total possible count of different tuples when there elements are positioned in order.
aaaa a a a a
aaab a a a b
aaac a a a c
aaad a a a d
aabb a a b b
aabc a a b c
aabd a a b d
aacc a a c c
aacd a a c d
aadd a a d d
abbb a b b b
abbc a b b c
abbd a b b d
abcc a b c c
abcd a b c d
abdd a b d d
accc a c c c
accd a c c d
acdd a c d d
addd a d d d
bbbb b b b b
bbbc b b b c
bbbd b b b d
bbcc b b c c
bbcd b b c d
bbdd b b d d
bccc b c c c
bccd b c c d
bcdd b c d d
bddd b d d d
cccc c c c c
cccd c c c d
ccdd c c d d
cddd c d d d
dddd d d d d
In this case we can count the number of rows present and notice that with for a tuple of 4 elements we have a cardinality of 35.
Algorithm
The algorithm calculates the cardinality, or total number of distinct tuples, for ordered n-tuples where each element can take one of several values. For example, in a tuple of 4 elements, where each element can be any of four distinct values, we compute how many unique ordered combinations are possible.
This process works by recursively constructing the tuples and counting them, ensuring that the elements follow a specific order. The function uses recursion to build the tuples and accumulates the number of possible combinations.
The recursive function calculate builds the tuples incrementally, and the total number of distinct combinations is stored in the sum. This approach is computationally efficient for small tuple sizes, with increasing execution times for larger tuples, as seen in the output.
This algorithm illustrates how combinatorial explosion occurs with increasing tuple sizes, as the cardinality grows rapidly due to the factorial nature of permutations. The code provided prints the cardinality for tuple sizes from 1 to 20, demonstrating the growth in both cardinality and the time it takes to compute.
package main
import (
"fmt"
"time"
)
func calculate(t int, l int, index int, sum int) int {
l += 1
for i := 1; i <= index; i++ {
if l < t {
sum = calculate(t, l, i, sum)
} else {
sum += i
}
}
return sum
}
func main() {
for i := 1; i <= 20; i++ {
fmt.Printf("Calculating cardinality for tuple of size %d\n", i)
startTime := time.Now()
res := calculate(i, 1, i, 0)
endTime := time.Now()
executionTime := endTime.Sub(startTime)
fmt.Printf("Card: %d\n", res)
fmt.Printf("Execution time: %d nanosecond\n\n", executionTime)
}
}
Calculating cardinality for tuple of size 1
Card: 1
Execution time: 42 nanosecond
Calculating cardinality for tuple of size 2
Card: 3
Execution time: 41 nanosecond
Calculating cardinality for tuple of size 3
Card: 10
Execution time: 83 nanosecond
Calculating cardinality for tuple of size 4
Card: 35
Execution time: 166 nanosecond
Calculating cardinality for tuple of size 5
Card: 126
Execution time: 416 nanosecond
Calculating cardinality for tuple of size 6
Card: 462
Execution time: 958 nanosecond
Calculating cardinality for tuple of size 7
Card: 1716
Execution time: 3125 nanosecond
Calculating cardinality for tuple of size 8
Card: 6435
Execution time: 11500 nanosecond
Calculating cardinality for tuple of size 9
Card: 24310
Execution time: 42958 nanosecond
Calculating cardinality for tuple of size 10
Card: 92378
Execution time: 179666 nanosecond
Calculating cardinality for tuple of size 11
Card: 352716
Execution time: 833459 nanosecond
Calculating cardinality for tuple of size 12
Card: 1352078
Execution time: 2423500 nanosecond
Calculating cardinality for tuple of size 13
Card: 5200300
Execution time: 9075291 nanosecond
Calculating cardinality for tuple of size 14
Card: 20058300
Execution time: 34792667 nanosecond
Calculating cardinality for tuple of size 15
Card: 77558760
Execution time: 156505417 nanosecond
Calculating cardinality for tuple of size 16
Card: 300540195
Execution time: 511428791 nanosecond
Calculating cardinality for tuple of size 17
Card: 1166803110
Execution time: 1991442583 nanosecond
Calculating cardinality for tuple of size 18
Card: 4537567650
Execution time: 7740995792 nanosecond
Calculating cardinality for tuple of size 19
Card: 17672631900
Execution time: 30314188167 nanosecond
Calculating cardinality for tuple of size 20
Card: 68923264410
Execution time: 118286735917 nanosecond