Cool Algorithm: Calculating any index of a Cartesian Product!
Published: 2020-02-02 05:54:53

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 the `result tuple` will be the `index % length_of_current_set`th index of the current set.
* Additionally, in each iteration, the `index` is set to `index // length_of_current_set` where `//` signifies **integer division**
  So, in this case, in the first iteration, for `index = 6`, the `current element` will be `C[6 % 2]` or `C[0]` or `1`.
  That will now be added as the **last element** of `result 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](https://github.com/TotallyNotChase/Fast-Cartesian-Product)!