python: recursive expanding list comprehension

Question

I've been looking around and I don't quite find my specific question answered. What makes my question specific is that I'm trying to only use list comprehension.

Question:

With the following code:

[print(k,l,m) for k in range(3) for l in range(2) for m in range(1)]

I get the output:

This works for n=3, or any hardcoded n. However, what I would like to do is:

[print(k1,k2,...,kn) for k1 in range(n) for k2 in range(n-1) .. for kn in range(1)].

I hope someone out there sees the answer immediately-- and thanks!

Edit The solution was posted below, but also to be clear about the format I was hoping for, here's how I used it to print out the encoding tuples:

n=3
[print(x) for x in itertools.product(*[list(range(i)) for i in range(n,0,-1)])]

(Didn't use reverse on the range for simplicity).

How is your output different than what you would like to see? Please supply a desired output — bcr, Apr 13 '18 at 14:59
@bcr I gave an example with n=3, but I would like to be able to do this for any non-hardcoded n. — Richard, Apr 13 '18 at 15:00
What does "only list comprehensions" mean? You used `print` and `range`, which are not list comprehensions. Am I allowed to use `itertools.product` in my solution? Can I define a recursive lambda function in my list comprehension? And what's the point of doing everything in a list comprehension anyway? — Aran-Fey, Apr 13 '18 at 15:02
In fact, there is a write the worst code possible challenge. And, sure, you can use itertools. On a serious note though, I'm doing this to get better with list comprehension, hence why I asked. — Richard, Apr 13 '18 at 15:05
It really seems like you're trying to build a dynamic truth table for this example. Possible duplicate of [python build a dynamic growing truth table](https://stackoverflow.com/questions/6336424/python-build-a-dynamic-growing-truth-table) — Sunny Patel, Apr 13 '18 at 15:16
If there's something you take away from this, it should be the knowledge that this is not something that should be done with list comprehensions. There isn't really such a thing as "getting better with list comprehensions". 99% of list comprehensions should be simple. Complex list comprehensions should be normal loops or a bunch of smaller list comprehensions instead. — Aran-Fey, Apr 13 '18 at 15:24
Note, don't use `print` in a list comprehension. These constructs should be free of side-effects. Otherwise, use a for-loop — juanpa.arrivillaga, Apr 13 '18 at 16:05

pensfute · Accepted Answer · 2018-04-13T15:31:48.160

1

You could use itertools.product if you are allowed to :

n=3
list(itertools.product(*[list(range(i)) for i in reversed(range(1, n+1))]))

edited Apr 13 '18 at 15:31

answered Apr 13 '18 at 15:15

pensfute

321
3
12

Well, this produces the correct combinations of integers, but reversed and not in the same order as the code in the question. – Aran-Fey Apr 13 '18 at 15:28
Great! Definitely headed in the right direction. I'm also trying to use itertools, with an added condition – Richard Apr 13 '18 at 15:30
I modified the code to work with the correct order ;) – pensfute Apr 13 '18 at 15:32
we can get the correct order if the range is switched up a bit: list(itertools.product(*[list(range(i)) for i in range(n,0,-1)])) – Richard Apr 13 '18 at 15:36

Mulan · Answer 2 · 2019-03-16T19:20:27.860

Someone recently asked a very similar question: "[How to] determine all combinations of flipping a coin without using itertools.product?" to which I provided an answer for. I wouldn't consider it a duplicate because I believe itertools.product is the best fit for your particular problem.

You may however be wondering how itertools.product does the trick. Or maybe you want to encode a different transformation in your recursive expansion. Below, I'll share one possible solution using Python's generators

def product (*iters):
  def loop (prod, first = [], *rest):
    if not rest:
      for x in first:
        yield prod + (x,)
    else:
      for x in first:
        yield from loop (prod + (x,), *rest)
  yield from loop ((), *iters)

for prod in product ("ab", "xyz"):
  print (prod)

# ('a', 'x')
# ('a', 'y')
# ('a', 'z')
# ('b', 'x')
# ('b', 'y')
# ('b', 'z')

Because product accepts a a list of iterables, any iterable input can be used in the product. They can even be mixed as demonstrated here

print (list (product (['@', '%'], range (2), "xy")))
# [ ('@', 0, 'x')
# , ('@', 0, 'y')
# , ('@', 1, 'x')
# , ('@', 1, 'y')
# , ('%', 0, 'x')
# , ('%', 0, 'y')
# , ('%', 1, 'x')
# , ('%', 1, 'y')
# ]

We could make a program foo that provides the output posted in your question

def foo (n):
  def build_ranges (m):
    if m == 0:
      return []
    else:
      return [ range (m) ] + build_ranges (m - 1)
  yield from product (*build_ranges (n))


for prod in foo (3):
  print (prod)

# (0, 0, 0)
# (0, 1, 0)
# (1, 0, 0)
# (1, 1, 0)
# (2, 0, 0)
# (2, 1, 0)

Or use destructuring assignment to create bindings for individual elements of the product

for (x,y,z) in foo (3):
  print ("x", x, "y", y, "z", z)

# x 0 y 0 z 0
# x 0 y 1 z 0
# x 1 y 0 z 0
# x 1 y 1 z 0
# x 2 y 0 z 0
# x 2 y 1 z 0

Other qualities of this product implementation are discussed in my answer to the question I linked. If you're interested to see how to do this without generators, I provide a purely functional solution to the problem as well.

python: recursive expanding list comprehension

2 Answers2