Python generating all nondecreasing sequences

2019-08-12 07:35发布

问题:

I am having trouble finding a way to do this in a Pythonic way. I assume I can use itertools somehow because I've done something similar before but can't remember what I did.

I am trying to generate all non-decreasing lists of length L where each element can take on a value between 1 and N. For example if L=3 and N=3 then [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3], etc.

回答1:

You can do this using itertools.combinations_with_replacement:

>>> L, N = 3,3
>>> cc = combinations_with_replacement(range(1, N+1), L)
>>> for c in cc: print(c)
(1, 1, 1)
(1, 1, 2)
(1, 1, 3)
(1, 2, 2)
(1, 2, 3)
(1, 3, 3)
(2, 2, 2)
(2, 2, 3)
(2, 3, 3)
(3, 3, 3)

This works because c_w_r preserves the order of the input, and since we're passing a nondecreasing sequence in, we only get nondecreasing tuples out.

(It's easy to convert to lists if you really need those as opposed to tuples.)