Lock Combinations for dynamic lock size

Question

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

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.

Why do you think itertools fills up your RAM? It's specifically designed to be a lazy iterator, it doesn't create all permutations at once. — jonrsharpe, Nov 10 '16 at 23:52
@jonrsharpe well actually we tried it out. And it took way longer then our own solutions. — fab-da-boy, Nov 10 '16 at 23:57
Am I the only one whom it took way too long to understand the question? — Right leg, Nov 11 '16 at 02:12
You really need to state explicitly if it's a requirement that the combinations you're returning *add up to* `numbers` (rather than that just being the maximum allowed value for each digit). That's not a normal requirement for a lock combination. Nor is is something that `itertools` will do for you directly. — Blckknght, Nov 11 '16 at 02:44
Good point @Blckknght The 2 sets of expected outputs do show that the OP wants compositions, but it would've made it a lot easier for readers to understand this question if the OP had stated that explicitly. — PM 2Ring, Nov 11 '16 at 02:56
True. My english isn't the best. Therefore it was kind of hard to explain my problem and so I tried to use as much examples as possible. Good thing that @PM2Ring understood what I was looking for. — fab-da-boy, Nov 11 '16 at 08:48
Do I understand your sentence right @Blckknght , that u mean that in my example it was harder, because i was saying i want it to be "0,0,0,0,5" instead of making it start at "5,0,0,0,0" ? Actually it doesnt really matter. I just wanted all possible combinations. :) — fab-da-boy, Nov 11 '16 at 09:00
If any digit can be any number from 0 to 5, then your problem is a very different one than what you've shown. For instance, the combination `5,5,5,5,5` would be allowed. I suspect you were having such bad performance from itertools because you were having it solve a different problem that has many more solutions than your actual problem. — Blckknght, Nov 11 '16 at 23:27
@Blckknght ok yeah you are right. :) maybe the lock was the wrong example here. — fab-da-boy, Nov 13 '16 at 22:32

score 5 · Accepted Answer · edited May 23 '17 at 12:30

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. (The timing information was obtained by using the Bash time command).

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]

Somewhat surprisingly, this one is a little faster than the original version, clocking in at around 1.5 seconds for compositions(15, 8).

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]]

Being an inveterate tinkerer, I couldn't stop myself from making yet another version. :) This is simply the original version combined with the code for combinations listed in the itertools docs. Of course, the real itertools.combinations is written in C so it runs faster than the roughly equivalent Python code shown in the docs.

def compositions(num, width):
    r = width - 1
    indices = list(range(r))
    revrange = range(r-1, -1, -1)
    first = [-1]
    last = [num + r]

    yield [0] * r + [num]
    while True:
        for i in revrange:
            if indices[i] != i + num:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield [v - u - 1 for u, v in zip(first + indices, indices + last)]

This version is about 50% slower than the original at doing compositions(15, 8): it takes around 2.3 seconds on my machine.

WoW! Thanks a lot mate. That is exactly what I was searching for. — fab-da-boy, Nov 11 '16 at 08:45
@fab-da-boy My pleasure! In case you're interested, I've added a recursive solution I found elsewhere on SO to my answer. Despite what I said earlier, that recursive solution should be ok. — PM 2Ring, Nov 11 '16 at 11:10
Dayum. Sickly well done! I am new to generators. But this is exactly what i was looking for! Thanks a lot, once again. — fab-da-boy, Nov 11 '16 at 11:18
@fab-da-boy Thanks! I'm a little surprised that that recursive version is so fast. FWIW, I've added another iterative solution. It's based on my original version but it generates the combinations internally, so it's slower than the original. — PM 2Ring, Nov 11 '16 at 13:30
@PM2Ring Nice. I am happy that I could hype you a little for this problem. :) Your solution basically confirms my statement, that a self written solution should be faster then itertools :) or am I understanding something wrong here? — fab-da-boy, Nov 11 '16 at 14:31

Lock Combinations for dynamic lock size

1 Answers1

Linked