Ever tried generating the cartesian product of 42 large sets/sequences just to get the 236th index of the product?
Trick Question: You don't have enough memory for that! (probably)
Thankfully, there's an algorithm to get any index you desire, real freakin' fast!
Sometimes, you just need to compute very large cartesian products just so you can use a handful of the indexes from the result. The problem is that generating the whole thing is slow, and often times, too much for your memory to even handle.
That's what prompted me to come up with this algorithm, apparently this is really hard to find on the internet (at least I couldn't find it). So I went ahead and asked some other folks about it and they too confirmed that, although many people know of this algorithm, it's nowhere to be found on the internet. So I'm making a post here for people to hopefully be able to find later :)
What does it do?
Suppose we have 3 sequences -
- A :
{1, 2, 3}
- B :
{2, 6, 7, 9}
- C :
{1, 7}
Simply call get_tuple_by_index
and pass in the list/array of sequences (i.e [A, B, C]
or {A, B, C}
) and the index of the result you want.
For C
(the programming language), you'd also need to pass in the number of sequences (3
in this case) and an array containing the lengths of each sequences ({3, 4, 2}
in this case).
For example, if we'd call get_tuple_by_index
with the 6th index (starting from 0) of the cartesian product A x B x C
, we'd get (1, 9, 1)
How does it work?
For this demonstration, we'll be using the sequences mentioned above as examples
- The
list
/array
of sequences, that we'd like the cartesian product to, in this case[A, B, C]
or{A, B, C}
is reverse iterated through. - In each iteration, the
result tuple
is filled up from backwards. - In each iteration, the
current element
of theresult tuple
will be theindex % length_of_current_set
th index of the current set. - Additionally, in each iteration, the
index
is set toindex // length_of_current_set
where//
signifies integer division So, in this case, in the first iteration, forindex = 6
, thecurrent element
will beC[6 % 2]
orC[0]
or1
. That will now be added as the last element ofresult tuple
. It'll now look like ->(1)
index
is now set to 6 // 2
or 3
In the second iteration, the current element
will be B[3 % 4]
or B[3]
or 9
.
That will now be added as the second to last element of result tuple
. It'll now look like -> (9, 1)
index
is now set to 3 // 4
or 0
In the third iteration, the current element
will be A[0 % 3]
or A[0]
or 1
.
That will now be added as the third to last element (or first element in this case) of result tuple
. It'll now look like -> (1, 9, 1)
The Code
Pretty cool! Here's some psuedocode to demonstrate the algorithm-
getNthTuple(sets, pos):
tuple = ()
for i in [(|sets|-1)..0]:
set = sets[i]
elem = set[pos mod |set|]
tuple = (elem, tuple)
pos = pos // |set|
return tuple
If you'd like to see examples in real programming languages, you can find the java
, python
and C
versions here!
Top comments (0)