[Tutor] Algorithm Question
Gregor Lingl
glingl@aon.at
Thu, 10 Jan 2002 00:05:15 +0100
>
> 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:
>
An alternate solution could be attained using a similar appraoch as to
teresa:
(yes, I know, soon it will be enough of this (albeit seemingly powerful)
stuff)
def codelist(chars, length):
codes = []
makecodes(chars, length, '', codes)
return codes
def makecodes(chars, length, begin, codes):
if length == 0:
codes.append(begin) # this begin is now the end
return
for char in chars:
makecodes(chars, length-1, begin + char, codes)
>>> codelist('01', 3)
['000', '001', '010', '011', '100', '101', '110', '111']
>>> codelist('01', 4)
['0000', '0001', '0010', '0011', '0100', '0101', '0110', '0111', '1000',
'1001', '1010', '1011', '1100', '1101', '1110', '1111']
>>> codelist('ABC', 3)
['AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ABC', 'ACA', 'ACB', 'ACC', 'BAA',
'BAB', 'BAC', 'BBA', 'BBB', 'BBC', 'BCA', 'BCB', 'BCC', 'CAA', 'CAB', 'CAC',
'CBA', 'CBB', 'CBC', 'CCA', 'CCB', 'CCC']
>>> codelist('wxyz', 2)
['ww', 'wx', 'wy', 'wz', 'xw', 'xx', 'xy', 'xz', 'yw', 'yx', 'yy', 'yz',
'zw', 'zx', 'zy', 'zz']
>>>
Gregor