1

I have N infinite generators. I already know how to take the Cartesian product of these infinite generators because there are several methods listed here ("zig-zag", "expanding square", etc.). I don't really care which method is used as the basis of what I really want: I want to convert an "index into the Cartesian product" into a "tuple of indexes into the original generators" without actually iterating a Cartesian product until that point. I am well aware that I can't actually index into generators. That's fine, because all I need are the indexes themselves. Basically, I want the same thing described here but works for infinite generators.

This will be easiest to understand if we consider a concrete example. Let's consider just two generators (N=2) and let them both be itertools.count() so that the indexes into the generators and the values of the generators are all the same.

from itertools import count
a = count()  # 0, 1, 2, ...
b = count()  # 0, 1, 2, ...

Let's assume I use the zig-zag algorithm because the author so kindly made it available on PyPI.

from infinite import product
p = product(a, b)  # (0,0), (0,1), (1,0), (0,2), (1,1), (2,0), ...

I want a function that, given an index into p, returns a tuple of indexes into a and b, like this:

f(2)  # (1,0)
f(4)  # (1,1)

Again, it doesn't have to be the linear index into the zig-zag algorithm. Any algorithm that produces the Cartesian product on infinite generators can be used as the basis.

drhagen
  • 8,331
  • 8
  • 53
  • 82
  • Still I am not sure why you can create your function `f(n)` to return the value of `n`th index from the result of `product(a, b)` ??? – Moinuddin Quadri Feb 04 '18 at 20:18
  • @MoinuddinQuadri `n` could be large and I don't want to iterate over `O(n)` to get an answer that should be calculable directly in `O(1)` – drhagen Feb 04 '18 at 20:24
  • 1
    I'd suggest you try to reduce the amount of information in your question. At the moments it's quite difficult to tell what you're asking. I think your question can be expressed in a single sentence: _"Given an index `n` as input, how can I calculate the nth element in the sequence `[(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),...]`?"_ – Aran-Fey Feb 04 '18 at 20:28

2 Answers2

4

You're trying to invert a pairing function. The "zig-zag" algorithm you give as an example is the Cantor pairing function (up to a change of argument order), given by f(x, y) = (x+y)(x+y+1)/2 + y, and it has inverse as follows.

If f^-1(z) = (x, y), then

w = floor((sqrt(8z+1)-1)/2)
t = w(w+1)/2
y = z-t
x = w-y

You can see the Wikipedia links for the full derivation.

user2357112
  • 260,549
  • 28
  • 431
  • 505
  • Yep, that's what I was looking for in two dimensions. If I can figure out how to extend it to arbitrary dimensions, I'll post it as a new answer. – drhagen Feb 04 '18 at 21:08
  • @drhagen: You can "unpair" the results of unpairing to generate 3-tuples and beyond, although the order won't be anything like `infinite.product`. – user2357112 Feb 04 '18 at 21:19
0

The various methods of generating the Cartesian products are all variants of the same procedure:

  1. Partition the product tuples into a countably infinite number of finite-sized chunks;

  2. Generate the tuples in each chunk in turn.

The "zigzag" method and Cantor's function, for example, chunk by the sum of indexes:

For integer i = 0 to infinity
    generate all tuples with sum(component_indexes) == i

The "expanding square method" is:

For integer i = 0 to infinity
    generate all tuples with max(component_indexes) == i

etc...

To find the kth tuple directly for any of these methods, you:

  1. Let SMALLER(i) be the number of tuples in chunks numbered less than i. Find the maximum i such that SMALLER(i) <= k. This is the number of the chunk that contains the kth tuple.
  2. Get the (k-SMALLER(i))th tuple (zero-based) with in chunk number i.

For the "expanding square" method in N dimensions, for example, SMALLER(i) = i^N -- the number of tuples with all components less than i, so i = floor(Nth_root(k)). Let r = k - i^N, and then find the rth tuple (in lexical order, for example) with max component equal to k.

The easiest kind of product to index directly, though, is bit interleaving. In this scheme, successive bits in the binary expansion of the product index are assigned to the component indexes in round-robin fashion. In python it looks like this:

def getProductTerm(dimensions, index):
    ret=[0]*dimensions
    bit=0
    while index>0:
        ret[dimensions-1-(bit%dimensions)]+=(index&1)<<(bit/dimensions)
        index >>= 1
        bit+=1
    return ret

You can try it here: https://ideone.com/0dTMU3

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87