algorithmperlmathcartesian-productcross-product# How to select specific item from cartesian product without calculating every other item

I'm mostly convinced that there is an answer to this problem, but for the life of me can't figure out how to do it.

Let's say I have three sets:

```
A = [ 'foo', 'bar', 'baz', 'bah' ]
B = [ 'wibble', 'wobble', 'weeble' ]
C = [ 'nip', 'nop' ]
```

And I know how to calculate the cartesian / cross product, (ant it's covered all over the place, on this site and elsewhere) so I won't go over that here.

What I'm looking for is an algorithm that would allow me to simply select a specific item from the cartesian product *without* generating the whole set or iterating until I reach the nth item.

Of course, I could easily iterate for a small example set like this, but the code I am working on will be working with much larger sets.

Therefore, I'm looking for a function, let's call it 'CP', where:

```
CP(1) == [ 'foo', 'wibble', 'nip' ]
CP(2) == [ 'foo', 'wibble', 'nop' ]
CP(3) == [ 'foo', 'wobble', 'nip' ]
CP(4) == [ 'foo', 'wobble', 'nop' ]
CP(5) == [ 'foo', 'weeble', 'nip' ]
CP(6) == [ 'foo', 'weeble', 'nop' ]
CP(7) == [ 'bar', 'wibble', 'nip' ]
...
CP(22) == [ 'bah', 'weeble', 'nop' ]
CP(23) == [ 'bah', 'wobble', 'nip' ]
CP(24) == [ 'bah', 'wobble', 'nop' ]
```

And the answer is produced in O(1) time, more or less.

I've been following the idea that it should be possible, (heck, even simple!) to calculate the indices of the elements from A,B,C that I want and then simply return the them from the original arrays, but my attempts to make this work correctly have so far, um, not worked.

I'm coding in Perl, but I can handily port a solution from Python, JavaScript, or Java (and probably a few others)

Solution

The number of possible combinations ist given by

```
N = size(A) * size(B) * size(C)
```

and you can index all items by an index `i`

ranging from `0`

to `N`

(exclusive) via

```
c(i) = [A[i_a], B[i_b], C[i_c]]
```

where

```
i_a = i/(size(B)*size(C))
i_b = (i/size(C)) mod size(B)
i_c = i mod size(C)
```

(all sets are assumed to be indexable starting wih zero, `/`

is integer division).

In order to get your example you may shift the index by 1.

- How to find kth smallest element in a BST when the tree may be modified frequently?
- How to check whether a matrix is a framed matrix?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- How does one make a Zip bomb?
- How to calculate the midpoints of each triangle edges of an icosahedron
- Calculate circular shift pairs in a list
- Uniformly randomly generate a vector of k unsigned ints that sums to N
- Identify connected subnetworks (R-igraph)
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array
- If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?
- Why is KNN slow with custom metric?
- Based on a condition, how to remove an item from the processed array and move it to another array?
- The simplest algorithm for poker hand evaluation
- Find longest repetitive sequence in a string
- Check if all elements in a list are identical
- Minimize sum of products of adjacent elements of an array
- Sorting an array with a repeating element (given its frequency) in linear time
- Creating dijkstras algorithm and having issues in C language