variable number of dependent nested loops

Question

Given two integers n and d, I would like to construct a list of all nonnegative tuples of length d that sum up to n, including all permutations. This is similar to the integer partitioning problem, but the solution is much simpler. For example for d==3:

[
    [n-i-j, j, i]
    for i in range(n+1)
    for j in range(n-i+1)
]

This can be extended to more dimensions quite easily, e.g., d==5:

[
    [n-i-j-k-l, l, k, j, i]
    for i in range(n+1)
    for j in range(n-i+1)
    for k in range(n-i-j+1)
    for l in range(n-i-j-l+1)
]

I would now like to make d, i.e., the number of nested loops, a variable, but I'm not sure how to nest the loops then.

Any hints?

I'm not sure if this is possible in a list comprehension as such but perhaps you could keep track of the subtracted values somehow so then all your loops look like for val in range(n - sum(vals) + 1) and then loop over that d times while building the list. — mattjegan
– mattjegan, Commented Jul 27, 2017 at 10:41
Possible duplicate of Next Composition of n into k parts - does anyone have a working algorithm? — Nico Schlömer
– Nico Schlömer, Commented Aug 2, 2017 at 12:12

Nico Schlömer · Accepted Answer · 2017-07-27 10:47:15Z

9

Recursion to the rescue: First create a list of tuples of length d-1 which runs through all ijk, then complete the list with another column n-sum(ijk).

def partition(n, d, depth=0):
    if d == depth:
        return [[]]
    return [
        item + [i]
        for i in range(n+1)
        for item in partition(n-i, d, depth=depth+1)
        ]


# extend with n-sum(entries)
n = 5
d = 3
lst = [[n-sum(p)] + p for p in partition(n, d-1)]

print(lst)

edited Jul 27, 2017 at 10:47

answered Jul 27, 2017 at 10:40

Nico Schlömer

59.7k35 gold badges216 silver badges291 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

mattjegan Over a year ago

Nice, I don't know why I was thinking of doing it iteratively.

Nico Schlömer Over a year ago

Yeah, same. Thinking about this iteratively had me stuck for the better part of the day.

Collectives™ on Stack Overflow

variable number of dependent nested loops

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related