[Tutor] Algorithm Question
Kirby Urner
urnerk@qwest.net
Tue, 08 Jan 2002 19:44:12 -0800
> find all possible arrangements :
>(0001,0010,0100,1000,1001,1011,1111,0000,0110,1010,0101,1100, etc)
Don't forget 0000 (maybe not legal in bank world).
In this case, doing binary, the simplest approach is to
just increment in base 2.
A lot of these permutation generators can be thought of
as counting problems, where you have a sequence with a
defined order, i.e. lowest to highest. If you can think
of a rule which defines the increment, and repeat it...
For example, if you wanted all permutations of 0,1,2,3,4,
with 3 slots to fill, then you could just increment
in base 5:
def base(n,b):
"""
Convert n in base 10 to list of digits
in some positive integral base b < 10
"""
digits = []
while n>0:
r = n%b
n = n//b
digits = [r] + digits
return digits
>>> ["".join(map(str,([0,0,0]+base(i,5)))[-3:]) for i in range(125)]
will give:
['000', '001', '002', '003', '004', '010', '011', '012',
'013', '014'
<<SNIP>>
'412', '413', '414', '420', '421', '422', '423', '424', '430',
'431', '432', '433', '434', '440', '441', '442', '443', '444']
Kirby