fab-da-boy - 22 days ago 7
Python Question

# Lock Combinations for dynamic lock size in python

In the following I will give two examples that have different dimension values.

Lock-1

``````# numbers are the shown values on the so in this case: 0,1,2
numbers = 5
# fields are those things i can turn to change my combination
fields = 4
``````

so what I would expect for all of my posibilities is

``````0   0   0   5
0   0   1   4
0   0   2   3
0   0   3   2
0   0   4   1
0   0   5   0
0   1   0   4
0   1   1   3
0   1   2   2
0   1   3   1
0   1   4   0
0   2   0   3
0   2   1   2
0   2   2   1
0   2   3   0
0   3   0   2
0   3   1   1
0   3   2   0
0   4   0   1
0   4   1   0
0   5   0   0
1   0   0   4
1   0   1   3
1   0   2   2
1   0   3   1
1   0   4   0
1   1   0   3
1   1   1   2
1   1   2   1
1   1   3   0
1   2   0   2
1   2   1   1
1   2   2   0
1   3   0   1
1   3   1   0
1   4   0   0
2   0   0   3
2   0   1   2
2   0   2   1
2   0   3   0
2   1   0   2
2   1   1   1
2   1   2   0
2   2   0   1
2   2   1   0
2   3   0   0
3   0   0   2
3   0   1   1
3   0   2   0
3   1   0   1
3   1   1   0
3   2   0   0
4   0   0   1
4   0   1   0
4   1   0   0
5   0   0   0
``````

My second lock has the following values:

``````numbers = 3
values = 3
``````

so what I would expect as my posibilities would look like this

``````0   0   3
0   1   2
0   2   1
0   3   0
1   0   2
1   1   1
1   2   0
2   0   1
2   1   0
3   0   0
``````

I know this can be done with
`itertools.permutations`
and so on, but I want to generate the rows by building them and not by overloading my RAM. I figured out that the last 2 rows are always building up the same way.
So i wrote a funtion which builds it for me:

``````def posibilities(value):
all_pos = []

for y in range(value + 1):
posibility = []
posibility.append(y)
posibility.append(value)

all_pos.append(posibility)

value -= 1

return all_pos
``````

Now I want some kind of way to fit the other values dynamically around my function, so e.g. Lock - 2 would now look like this:

``````0   posibilities(3)
1   posibilities(2)
2   posibilities(1)
3   posibilities(0)
``````

I know I should use a
`while`
loops and so on, but I can't get the solution for dynamic values.

You could do this recursively, but it's generally best to avoid recursion in Python unless you really need it, eg, when processing recursive data structures (like trees). Recursion in standard Python (aka CPython) is not very efficient because it cannot do tail call elimination. Also, it applies a recursion limit (which is by default 1000 levels, but that can be modified by the user).

The sequences that you want to generate are known as weak compositions, and the Wikipedia article gives a simple algorithm which is easy to implement with the help of the standard `itertools.combinations` function.

``````#!/usr/bin/env python3

''' Generate the compositions of num of a given width

Algorithm from
https://en.wikipedia.org/wiki/Composition_%28combinatorics%29#Number_of_compositions

Written by PM 2Ring 2016.11.11
'''

from itertools import combinations

def compositions(num, width):
m = num + width - 1
last = (m,)
first = (-1,)
for t in combinations(range(m), width - 1):
yield [v - u - 1 for u, v in zip(first + t, t + last)]

# test

for t in compositions(5, 4):
print(t)

print('- ' * 20)

for t in compositions(3, 3):
print(t)
``````

output

``````[0, 0, 0, 5]
[0, 0, 1, 4]
[0, 0, 2, 3]
[0, 0, 3, 2]
[0, 0, 4, 1]
[0, 0, 5, 0]
[0, 1, 0, 4]
[0, 1, 1, 3]
[0, 1, 2, 2]
[0, 1, 3, 1]
[0, 1, 4, 0]
[0, 2, 0, 3]
[0, 2, 1, 2]
[0, 2, 2, 1]
[0, 2, 3, 0]
[0, 3, 0, 2]
[0, 3, 1, 1]
[0, 3, 2, 0]
[0, 4, 0, 1]
[0, 4, 1, 0]
[0, 5, 0, 0]
[1, 0, 0, 4]
[1, 0, 1, 3]
[1, 0, 2, 2]
[1, 0, 3, 1]
[1, 0, 4, 0]
[1, 1, 0, 3]
[1, 1, 1, 2]
[1, 1, 2, 1]
[1, 1, 3, 0]
[1, 2, 0, 2]
[1, 2, 1, 1]
[1, 2, 2, 0]
[1, 3, 0, 1]
[1, 3, 1, 0]
[1, 4, 0, 0]
[2, 0, 0, 3]
[2, 0, 1, 2]
[2, 0, 2, 1]
[2, 0, 3, 0]
[2, 1, 0, 2]
[2, 1, 1, 1]
[2, 1, 2, 0]
[2, 2, 0, 1]
[2, 2, 1, 0]
[2, 3, 0, 0]
[3, 0, 0, 2]
[3, 0, 1, 1]
[3, 0, 2, 0]
[3, 1, 0, 1]
[3, 1, 1, 0]
[3, 2, 0, 0]
[4, 0, 0, 1]
[4, 0, 1, 0]
[4, 1, 0, 0]
[5, 0, 0, 0]
- - - - - - - - - - - - - - - - - - - -
[0, 0, 3]
[0, 1, 2]
[0, 2, 1]
[0, 3, 0]
[1, 0, 2]
[1, 1, 1]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[3, 0, 0]
``````

FWIW, the above code can generate the 170544 sequences of `compositions(15, 8)` in around 1.6 seconds on my old 2GHz 32bit machine, running on Python 3.6 or Python 2.6.

FWIW, here's a recursive version taken from this answer by user3736966. I've modified it to use the same argument names as my code, to use lists instead of tuples, and to be compatible with Python 3.

``````def compositions(num, width, parent=[]):
if width > 1:
for i in range(num, -1, -1):
yield from compositions(i, width - 1, parent + [num - i])
else:
yield parent + [num]
``````

If your version of Python doesn't understand `yield from`, you can do this:

``````def compositions(num, width, parent=[]):
if width > 1:
for i in range(num, -1, -1):
for t in compositions(i, width - 1, parent + [num - i]):
yield t
else:
yield parent + [num]
``````

To generate the compositions in descending order, simply reverse the `range` call, i.e. `for i in range(num + 1):`.

Finally, here's an unreadable one-line version. :)

``````def c(n, w, p=[]):
yield from(t for i in range(n,-1,-1)for t in c(i,w-1,p+[n-i]))if w-1 else[p+[n]]
``````