python - Lock Combinations for dynamic lock size -
in following give 2 examples have different dimension values.
lock-1
# numbers shown values on in case: 0,1,2 numbers = 5 # fields things can turn change combination fields = 4 so expect of 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 following values:
numbers = 3 values = 3 so expect posibilities 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 can done itertools.permutations , on, want generate rows building them , not overloading ram. figured out last 2 rows building same way. wrote funtion builds me:
def posibilities(value): all_pos = [] y in range(value + 1): posibility = [] posibility.append(y) posibility.append(value) all_pos.append(posibility) value -= 1 return all_pos now want kind of way fit other values dynamically around function, e.g. lock - 2 this:
0 posibilities(3) 1 posibilities(2) 2 posibilities(1) 3 posibilities(0) i know should use while loops , on, can't solution dynamic values.
you could recursively, it's best avoid recursion in python unless really need it, eg, when processing recursive data structures (like trees). recursion in standard python (aka cpython) not efficient because cannot tail call elimination. also, applies recursion limit (which default 1000 levels, can modified user).
the sequences want generate known weak compositions, , wikipedia article gives simple algorithm easy implement of standard itertools.combinations function.
#!/usr/bin/env python3 ''' generate compositions of num of given width algorithm https://en.wikipedia.org/wiki/composition_%28combinatorics%29#number_of_compositions written pm 2ring 2016.11.11 ''' itertools import combinations def compositions(num, width): m = num + width - 1 last = (m,) first = (-1,) t in combinations(range(m), width - 1): yield [v - u - 1 u, v in zip(first + t, t + last)] # test t in compositions(5, 4): print(t) print('- ' * 20) 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, above code can generate 170544 sequences of compositions(15, 8) in around 1.6 seconds on old 2ghz 32bit machine, running on python 3.6 or python 2.6. (the timing information obtained using bash time command).
fwiw, here's recursive version taken this answer user3736966. i've modified use same argument names code, use lists instead of tuples, , compatible python 3.
def compositions(num, width, parent=[]): if width > 1: in range(num, -1, -1): yield compositions(i, width - 1, parent + [num - i]) else: yield parent + [num] somewhat surprisingly, 1 little faster original version, clocking in @ around 1.5 seconds compositions(15, 8).
if version of python doesn't understand yield from, can this:
def compositions(num, width, parent=[]): if width > 1: in range(num, -1, -1): t in compositions(i, width - 1, parent + [num - i]): yield t else: yield parent + [num] to generate compositions in descending order, reverse range call, i.e. for in range(num + 1):.
finally, here's unreadable one-line version. :)
def c(n, w, p=[]): yield from(t in range(n,-1,-1)for t in c(i,w-1,p+[n-i]))if w-1 else[p+[n]] being inveterate tinkerer, couldn't stop myself making yet version. :) original version combined code combinations listed in itertools docs. of course, real itertools.combinations written in c runs faster equivalent python code shown in 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: in revrange: if indices[i] != + num: break else: return indices[i] += 1 j in range(i+1, r): indices[j] = indices[j-1] + 1 yield [v - u - 1 u, v in zip(first + indices, indices + last)] this version 50% slower original @ doing compositions(15, 8): takes around 2.3 seconds on machine.
Comments
Post a Comment