CODEWITHSUNDEEP
algorithmcombinatoricscartesian-product
ijustlovemath
ijustlovemath

Reputation: 938

How to generate the next tuple in a Cartesian product?

I have an n-tuple, x = (x[0], .., x[n-1]) where each member of the tuple comes from a distinct, ordered set S[i] such that x[i] \in S[i]. The sets S[i] all have different cardinalities N[i]. I want to know how to generate the next tuple in lexical order given the sets S[i].

Example:

S[0] = {0,1,2}
S[1] = {1,2,3,4}
S[2] = {8,9,7}

x = {2,2,7}
xnext = {2,3,8}
xnextnext = {2,3,9}

etc

This doesn't have to be very efficient, just closed form in terms of the current tuple elements and the sets. If it's easier, it would be equivalent to think of the n-tuple as indices in the sets.

Upvotes: 0

Views: 332

Answers (2)

user6732794
user6732794

Reputation:

For a given tuple, you can map the elements of the tuple to their respective indices in each set of S, then try to "increment" the mixed-radix number represented by this tuple of indices. Then, take the incremented "number" and map it back to a tuple of elements. Here's a proof-of-concept in Python:

def next_tuple(x, S):
    assert len(x) == len(S)
    assert all(element in set_ for element, set_ in zip(x, S))

    # compute the bases for our mixed-radix system
    lengths = [len(set_) for set_ in S]
    # convert tuple `x` to a mixed-radix number
    indices = [set_.index(element) for element, set_ in zip(x, S)]

    # try to increment, starting from the right
    for k in reversed(range(len(indices))):
        indices[k] += 1

        if indices[k] == lengths[k]: 
            # case 1: we have a carry, rollover this index and continue
            indices[k] = 0
        else:
            # case 2: no carry, map indices back to actual elements and return
            return [set_[index] for index, set_ in zip(indices, S)]

    # we have gone through each position and still have a carry.
    # this means the "increment" operation overflowed, and there
    # is no "next" tuple.
    return None


S = [[0, 1, 2], [1, 2, 3, 4], [8, 9, 7]]

print("next tuple after {} is {}".format([2, 2, 7], next_tuple([2, 2, 7], S)))
print("all tuples in order:")

x = [0, 1, 8]

while x is not None:
    print(x)
    x = next_tuple(x, S)

As a final note, if you need to enumerate the entire cartesian product in order, it's simpler to use a direct algorithm rather than repeatedly using next_tuple which has to recompute indices every time.

Upvotes: 1

ijustlovemath
ijustlovemath

Reputation: 938

I got it to work using this pseudocode:

# x = [2,2,7]
sets = [[0,1,2], [1,2,3,4], [8,9,7]]
def next_tuple(x):
    for i, el in enumerate(x):
        if(i < len(sets[i]) - 1):
            x[i] = sets[i, sets[i].index(x[i])+1] // requires lists to have unique elements
            return x
        else :
            x[i] = sets[i,0]

Basically you scan in a character from the tuple, and if it can be incremented, increment it. If not, set it to 0 and go to the next character.

Upvotes: 0

Related Questions