How can I compute a Cartesian product iteratively?

by

1) Create a list of indexes into the respective lists, initialized to 0, i.e:

indexes = [0,0,0,0,0,0]

2) Yield the appropriate element from each list (in this case the first).

3) Increase the last index by one.

4) If the last index equals the length of the last list, reset it to zero and carry one. Repeat this until there is no carry.

5) Go back to step 2 until the indexes wrap back to [0,0,0,0,0,0]

It’s similar to how counting works, except the base for each digit can be different.

Here’s an implementation of the above algorithm in Python:

def cartesian_product(aListOfList):
    indexes = [0] * len(aListOfList)
    while True:
        yield [l[i] for l,i in zip(aListOfList, indexes)]
        j = len(indexes) - 1
        while True:
            indexes[j] += 1
            if indexes[j] < len(aListOfList[j]): break
            indexes[j] = 0
            j -= 1
            if j < 0: return

Here is another way to implement it using modulo tricks:

def cartesian_product(aListOfList):
    i = 0
    while True:
        result = []
        j = i
        for l in aListOfList:
             result.append(l[j % len(l)])
             j /= len(l)
        if j > 0: return
        yield result
        i += 1

Note that this outputs the results in a slightly different order than in your example. This can be fixed by iterating over the lists in reverse order.

More Related Contents:

  1. Algorithm for iterating over an outward spiral on a discrete 2D grid from the origin
  2. How can I pair socks from a pile efficiently?
  3. Unique (non-repeating) random numbers in O(1)?
  4. Getting the closest string match
  5. Converting a Uniform Distribution to a Normal Distribution
  6. Can hash tables really be O(1)?
  7. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  8. What distribution do you get from this broken random shuffle?
  9. Is there an O(n) integer sorting algorithm?
  10. recursion versus iteration
  11. Determine font color based on background color
  12. Nearest neighbors in high-dimensional data?
  13. What algorithm gives suggestions in a spell checker?
  14. How can I measure the similarity between two images? [closed]
  15. Generate all unique substrings for given string
  16. Sum-subset with a fixed subset size
  17. What is a good Hash Function?
  18. design a stack such that getMinimum( ) should be O(1)
  19. Binary Search in Array
  20. Puzzle: Find largest rectangle (maximal rectangle problem)
  21. Calculate largest inscribed rectangle in a rotated rectangle
  22. The Sieve of Atkin
  23. How to partition an array of integers in a way that minimizes the maximum of the sum of each partition?
  24. Polygon enclosing a set of points
  25. 3 dimensional bin packing algorithms
  26. “Rounding” colour values to the nearest of a small set of colours
  27. Can an array be grouped more efficiently than sorted?
  28. Convert light frequency to RGB?
  29. Tournament bracket placement algorithm
  30. Postfix notation to expression tree

Leave a Comment