interesting exercise

[Michael Tobis]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt

 

[James Stroud]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt

1. You oughtta go ahead and post it.
2. Have you checked out xpermutations?

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/190465

James

 

[Gabriel Genellina]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

This is what I come, no tricks, no special optimizations, just plain
Python (including your constraints):

def permute(values, n):

def _permute(values, n):
if n==1:
for letter in values:
yield [letter]
else:
for letter in values:
for others in _permute(values, n-1):
yield [letter]+others

if not sorted(values): raise ValueError("unsorted values")
if len(set(values))!=len(values): raise ValueError("duplicate values")
return list(''.join(item) for item in _permute(values, n))

 

[Steven D'Aprano]

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don't need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.

Hang on... stupid crystal ball... that's somebody else's code. Maybe you
should just post your code here, so we can look at it?

In the meantime, here's a simple generator to do permutations with
repetition:

def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail


It doesn't do a test for the sequence containing duplicates, and I leave
it as an exercise to do selections of fewer items.

 

[Steven D'Aprano]

if not sorted(values): raise ValueError("unsorted values")

sorted() doesn't return a flag telling if the values are sorted, it
returns a new list containing values sorted. So this line will raise an
exception only on an empty sequence.

 

[castironpi]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt

Post yours.

 

[Gabriel Genellina]

En Tue, 08 May 2007 01:33:51 -0300, Steven D'Aprano

sorted() doesn't return a flag telling if the values are sorted, it
returns a new list containing values sorted. So this line will raise an
exception only on an empty sequence.

Ouch!

 

[castironpi]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]

permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

thanks
mt

Post yours.

Oh well, as I'm not the first.
def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
a = sorted( set( a ) )
return [i+j for i in a for j in p(a,b-1)]

p('abc',3)
#fb: ['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']
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p("13579",3))
#fb: 125
edit()

 

[castironpi]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.
For example
permute("abc",2)
should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]
and permute("13579",3) should return a list of 125 elements
["111","113", ... ,"997","999"]
permute("axc",N) or permute("2446",N) should raise ValueError as the
alphabet is not strictly sorted.
I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?
thanks
mt

Post yours.

Oh well, as I'm not the first.
[working solution snip]

Or even,
def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
return [i+j for i in list(a) for j in p(a,b-1)]

p('abc',3)
#fb: ['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']
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p("13579",3))
#fb: 125
edit()

 

[sherry]

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don't need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.

Hang on... stupid crystal ball... that's somebody else's code. Maybe you
should just post your code here, so we can look at it?

In the meantime, here's a simple generator to do permutations with
repetition:

def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail

It doesn't do a test for the sequence containing duplicates, and I leave
it as anexerciseto do selections of fewer items.

Dear Steven
I ran into your message quite accidentally while researching about
some details on 'Exercise' and thought of sharing some of my
findings.
I've read at 'http://www.medical-health-care-information.com/Health-
living/exercise/index.asp
that Swimming, cycling, jogging, skiing, aerobic dancing, walking or
any of dozens of other activities can help your heart. Whether it's
included in a structured exercise program or just part of your daily
routine, all physical activity adds up to a healthier heart.
I hope the above is of some help to you as well. Regards, Sherrybove.

 

[Alex Martelli]

def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
return [i+j for i in list(a) for j in p(a,b-1)]

No need for 2/3 of the list(...) calls. sorted(a) and sorted(list(a))
will ALWAYS be the same sequence; "for i in a" and "for i in list(a)"
will always iterate on the same sequence [as long as you're not changing
a inside the iteration, which, in this case, you aren't].


Alex

 

[castironpi]

...

def p(a,b):
if list( a ) != sorted( list( a ) ): raise ValueError, "String not
ordered."
if not b: return ['']
return [i+j for i in list(a) for j in p(a,b-1)]

No need for 2/3 of the list(...) calls. sorted(a) and sorted(list(a))
will ALWAYS be the same sequence; "for i in a" and "for i in list(a)"
will always iterate on the same sequence [as long as you're not changing
a inside the iteration, which, in this case, you aren't].

Alex

Ah quite true. list( a ) != sorted( a ). ...for i in a for...

 

[Christopher Cormie]

I want a list of all ordered permutations of a given length of a set
of tokens. Each token is a single character, and for convenience, they
are passed as a string in ascending ASCII order.

For example

permute("abc",2)

should return ["aa","ab","ac","ba","bb","bc","ca","cb","cc"]

If N is constant and small (e.g hard-coded N of 2), list comprehensions
provide a concise solution:

a = "abc"
b = [(x,y) for x in a for y in a]
c = ["".join(z) for z in b]
print b
print c

Gives:

[('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', ' a'), ('c',
'b'), ('c', 'c')]

['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']

Cheers,
Chris

 

[James Stroud]

I have a reasonably elegant solution but it's a bit verbose (a couple
dozen lines which I'll post later if there is interest). Is there some
clever Pythonism I didn't spot?

Peering into my crystal ball, I see that your algorithm does the wrong
thing, and contains bugs too. You certainly don't need to partion the
sequence into three sub-sequences, or do that trick with the metaclass,
and it is more efficient to use list.extend() than sum.

Hang on... stupid crystal ball... that's somebody else's code. Maybe you
should just post your code here, so we can look at it?

In the meantime, here's a simple generator to do permutations with
repetition:

def permute_with_repetitions(seq):
if len(seq) <= 1:
yield list(seq)
else:
for i, item in enumerate(seq):
for tail in permute_with_repetitions(seq[:i] + seq[i+1:]):
yield [item] + tail

It doesn't do a test for the sequence containing duplicates, and I leave
it as anexerciseto do selections of fewer items.

Dear Steven
I ran into your message quite accidentally while researching about
some details on 'Exercise' and thought of sharing some of my
findings.
I've read at 'http://www.medical-health-care-information.com/Health-
living/exercise/index.asp
that Swimming, cycling, jogging, skiing, aerobic dancing, walking or
any of dozens of other activities can help your heart. Whether it's
included in a structured exercise program or just part of your daily
routine, all physical activity adds up to a healthier heart.
I hope the above is of some help to you as well. Regards, Sherrybove.

This takes annoying past annoying to some new level of hell to which
even satan himself wouldn't venture.

 

[Carsten Haese]

[snip Steven's response about a programming exercise...]

[snip Sherrybove's spam about physical exercise...]

And today's award for the most conspicuous failure of the Turing test
goes to the Spambot posting as Sherrybove! (*applause*) Fortunately,
it's not programmed to deliver acceptance speeches, so it will accept
the award silently.

I-know-this-isn't-on-topic-either-but-I-couldn't-resist'ly yours,

Carsten.

 

[Steven D'Aprano]

This takes annoying past annoying to some new level of hell to which
even satan himself wouldn't venture.

And thank you for sharing that piece of spam with us again. It was so much
less enjoyable to see it the second time.

Seriously James, with more and more people using automated spam filters,
it might not be such a wise idea to keep having your name associated with
spam content.

 

[James Stroud]

And thank you for sharing that piece of spam with us again. It was so much
less enjoyable to see it the second time.

Seriously James, with more and more people using automated spam filters,
it might not be such a wise idea to keep having your name associated with
spam content.

Thank you for the tip.

James

 

[castironpi]

Thank you for the tip.

James

We also have:

p=lambda a,n: [ ''.join( y ) for y in eval('[%%s %s]'%' '.join(['for x
%i in a'%i for i in range(n)]) %'(%s)'%','.join(['x%i'%i for i in
range(n)]) ) ]
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p('13579',3))
#fb: 125
edit()

File under obscurities. acb

 

[castironpi]

Thank you for the tip.

James

We also have:

p=lambda a,n: [ ''.join( y ) for y in eval('[%%s %s]'%' '.join(['for x
%i in a'%i for i in range(n)]) %'(%s)'%','.join(['x%i'%i for i in
range(n)]) ) ]
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p('13579',3))
#fb: 125
edit()

File under obscurities. acb

Slightly clearer:
p=lambda a,n:[ ''.join( y ) for y in eval('[(%s) %s]'%(','.join(['x
%i'%i for i in range(n)]),' '.join(['for x%i in a'%i for i in
range(n)])))]
p('abc',2)
#fb: ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
len(p('13579',3))
#fb: 125
edit()

where for n=4:
('[(%s) %s]'%(','.join(['x%i'%i for i in range(n)]),' '.join(['for x%i
in a'%i for i in range(n)])))
#fb: '[(x0,x1,x2,x3) for x0 in a for x1 in a for x2 in a for x3 in a]'

 

[Michael Tobis]

Thanks castironpi and alex, for this:

def p(a,b):
if not b: return ['']
return [i+j for i in a for j in p(a,b-1)]

That is a thing of beauty! As usual you guys didn't disappoint.

(Validity check of alphabet removed; you didn't check for duplicate
characters.)

Here is the bloated mess I came up with. I did see that it had to be
recursive, and was proud of myself for getting it pretty much on the
first try, but the thing still reeks of my sorry old fortran-addled
mentality.

def validAlphabet(alphabet):
if not isinstance(alphabet,str):
return False
if len(alphabet) > 256:
return False
for index in range(len(alphabet)-1):
if not alphabet[index] < alphabet[index+1]:
return False
return True

def nextword(word,alphabet):
if len(word) == 1:
index = alphabet.find(word)
if index < 0:
raise ValueError("bad token found %s" % word)
if index == len(alphabet) -1:
return None
else:
return alphabet[index+1]
else:
a = nextword(word[1:],alphabet)
if a:
return word[0] + a
else:
b = nextword(word[0],alphabet)
if b:
return b + (len(word) - 1) * alphabet[0]
else:
return None

def allwords(length,alphabet="01"):
if not validAlphabet(alphabet):
raise ValueError("bad token list %s" % alphabet)
word = length * alphabet[0]
result = [word]
while word < length * alphabet[-1]:
word = nextword(word,alphabet))
result.append(word)
return result

######

if __name__ == "__main__":
for item in allwords(5,"abc"):
print item