Cross product of sets using recursion

by

The simplest recursive definition of the cartesian product I can think of looks like this. You can see that like yours, this has a loop — actually, two loops embedded in a list comprehension. Unlike yours, this can handle two or more sequences:

def product(*seqs):
    if not seqs:
        return [[]]
    else:
        return [[x] + p for x in seqs[0] for p in product(*seqs[1:])]

Here’s a walk-through to give you a sense of how it works. By definition, the cartesian product of an empty sequence (product()) is a sequence containing the empty sequence. In other words, product() == [[]] — see here for why.

Now let’s say we call product([1, 2, 3]) — seqs is non-empty, so the return value is the result of the list comprehension. In this case, product(*seqs[1:]) == product(*[]) == product() == [[]], so the list comprehension is equivalent to this:

[[x] + p for x in seqs[0] for p in [[]] ]

Which is equivalent to all of these:

[[x] + [] for x in seqs[0]]
[[x] for x in seqs[0]]
[[1], [2], [3]]

Adding another sequence, we have product([4, 5, 6], [1, 2, 3]). Now the list comprehension looks like this:

[[x] + p for x in [4, 5, 6] for p in product(*seqs[1:])]
[[x] + p for x in [4, 5, 6] for p in [[1], [2], [3]]]
[[4, 1], [4, 2], [4, 3], [5, 1], [5, 2], [5, 3], [6, 1], [6, 2], [6, 3]]

The pattern continues from there; for each additional sequence, each of the values in the sequence is prepended to each of the values in the cartesian product of the following sequences.

More Related Contents:

  1. Why does this recursion return 0?
  2. One line recursive loop in python
  3. Nested defaultdict of defaultdict
  4. Recursive code returns None [duplicate]
  5. How to do a recursive sub-folder search and return files in a list?
  6. Finding a key recursively in a dictionary
  7. How can I build a recursive function in python? [duplicate]
  8. Can a lambda function call itself recursively in Python?
  9. Function with varying number of For Loops (python)
  10. Hitting Maximum Recursion Depth Using Pickle / cPickle
  11. Python recursion permutations
  12. Search for a key in a nested Python dictionary
  13. Python recursive function error: “maximum recursion depth exceeded” [duplicate]
  14. Recursion applied to lists vs trees in Python
  15. Can generators be recursive?
  16. What is the hard recursion limit for Linux, Mac and Windows?
  17. Process finished with exit code -1073741571
  18. Confusing […] List in Python: What is it?
  19. Recursion using yield
  20. python ctype recursive structures
  21. Counting recursive calls of a function
  22. Flattening a list recursively [duplicate]
  23. Is there a recursive version of the dict.get() built-in?
  24. Why does Python have a maximum recursion depth?
  25. Recursive generator for flattening nested lists
  26. Python recursive function to display all subsets of given set
  27. Why Python raises RecursionError before it exceeds the real recursion limit?
  28. Recursive Typing in Python 3.5+ [duplicate]
  29. Python Array Rotation
  30. Given a list of elements in lexicographical order (i.e. [‘a’, ‘b’, ‘c’, ‘d’]), find the nth permutation – Average time to solve?

Leave a Comment