simple recursion help

[drs]

Hi, I am trying to find all lists of length x with elements a, b, and c.
To this end, I have created the class below, but it is not quite working and
I am having trouble figuring out what to change. Does anyone have any
insight?

class c:
def __init__(self):
self.traits = 4 # number of list elements
self.types = 3 # elements can be 0, 1, or 2

def a(self):
l = []
for i in range(self.traits):
l.append(self.b(str(i)))
return l

def b(self, s):
if len(s) == self.types:
return s
for i in range(self.traits):
return self.b(s + str(i))


i = c()
lst = i.a()


Thanks in advance,

-d

 

[drs]

I didn't state what I am doing quite so clearly (or correctly), so I'll try
again. I am looking for a list of all unique strings of length x whose
elements are from the set a, b, and c.

So, for example, in this case it would be

aaa, aab, aac, aba, abb, abc, aca, acb, acc, ... cca, ccb, ccc

but I need for the length and the number of elements to be variable.

I understand this will get out of hand very quickly for large numbers, but I
only need it for small length/numbers.

Thanks,

-d

 

[Steven Bethard]

Hi, I am trying to find all lists of length x with elements a, b, and c.

I'm not sure exactly what you're looking for here. It would help if you gave an
example of some input and the output you want to produce.

Seems you might be looking for the permutations of a list. If so, check the
ASPN Cookbook:

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

If this is not what you're looking for, please give us a little more info on the
problem.

Steve

 

[Steven Bethard]

I am looking for a list of all unique strings of length x whose
elements are from the set a, b, and c.

So, for example, in this case it would be

aaa, aab, aac, aba, abb, abc, aca, acb, acc, ... cca, ccb, ccc

but I need for the length and the number of elements to be variable.

Much clearer, thanks. Is this what you're looking for:
.... for char in chars:
.... if n == 1:
.... yield char
.... else:
.... for string in f(chars, n-1):
.... yield char + string
....

list(f('abc', 1)) ['a', 'b', 'c']
list(f('abc', 2)) ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
list(f('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']

Steve

 

[Steven Bethard]

I am looking for a list of all unique strings of length x whose
elements are from the set a, b, and c.

Does anyone know what this operation is called? It's not permutations or
combinations as I understand them since permutations and combinations do not
allow repetition. I assume there was already a solution for this somewhere, but
I didn't know what term to google for.

Thanks,

Steve

 

[Alex Martelli]

Does anyone know what this operation is called? It's not permutations or
combinations as I understand them since permutations and combinations do
not allow repetition. I assume there was already a solution for this
somewhere, but I didn't know what term to google for.

There's been a recent thread where the OP called them 'permutations',
somebody commented they're 'variations'. In that thread you'll find a
bazillion solutions, recursive and non, with or without itertools, &c.


Alex

 

[Michael J. Fromberger]

Does anyone know what this operation is called? It's not
permutations or combinations as I understand them since permutations
and combinations do not allow repetition. I assume there was already
a solution for this somewhere, but I didn't know what term to google
for.

The task you're describing is generation of all strings over a given
alphabet. Fortunately, there is a fairly simple technique for doing
this -- here is a Python generator to do it:

def lexgen(alph, maxlen = None):
"""Generate all the possible strings over the given alphabet in
lexicographic order. Stop after generating the strings of maxlen,
if provided; otherwise, generate forever."""

ixs = []

while maxlen is None or len(ixs) <= maxlen:
while True:
yield str.join('', [ alph[ixs[x]] for x in
xrange(len(ixs) - 1, -1, -1) ])

for pos in xrange(len(ixs)):
ixs[pos] = (ixs[pos] + 1) % len(alph)
if ixs[pos] <> 0:
break

if sum(ixs) == 0:
break

ixs += [0]

Cheers,
-M

 

[Alex Martelli]

Michael J. Fromberger <[email protected]>
wrote:
...

...
The task you're describing is generation of all strings over a given
alphabet. Fortunately, there is a fairly simple technique for doing
this -- here is a Python generator to do it:

def lexgen(alph, maxlen = None):
"""Generate all the possible strings over the given alphabet in
lexicographic order. Stop after generating the strings of maxlen,
if provided; otherwise, generate forever."""

ixs = []

while maxlen is None or len(ixs) <= maxlen:
while True:
yield str.join('', [ alph[ixs[x]] for x in
xrange(len(ixs) - 1, -1, -1) ])

for pos in xrange(len(ixs)):
ixs[pos] = (ixs[pos] + 1) % len(alph)
if ixs[pos] <> 0:
break

if sum(ixs) == 0:
break

ixs += [0]

Nice, and different from what was offered in the other recent thread
(and from what the OP asked for) since you generate all strings of
length up to maxlen, while the request was for just those of length
exactly x. Still, this can easily be restricted, and maybe a few
Pythonic tweaks with it...:

def lexgen_n(alph, x):
ixs = [0] * x
while True:
yield ''.join([alph for i in ixs[::-1]])
for pos in xrange(x):
ixs[pos] += 1
if ixs[pos] < len(alph):
break
ixs[pos] = 0
else:
break

the 'else: break' at the end executes if the for terminates normally
(this makes it needless to test sum(ixs), or max(ixs), again).

In 2.4 one can do a bit better for the yield, with

yield ''.join(alph for i in reversed(ixs))

[generator expression vs list comprehension, and reversed built-in vs
reversal by slicing]. Of course, instead of reversing in the yield, one
can reverse in the for -- so in 2.4 one might have (variant...):

yield ''.join(alph for i in ixs)
for pos in reversed(xrange(x)):
...

or, after a 'from itertools import imap':

yield ''.join(imap(alph.__getitem__, ixs))

It's important to remember that Python does no constant-expression
hoisting; there may be important efficiencies in hoisting constants
oneself (that len(alph) in the inner loop, for example). E.g, sticking
to 2.4 (what one should use if one cares for speed anyway), another
variant:

def lexgen_n(alph, x):
# hoistings for speed
from itertools import imap
getalph = alph.__getitem__
lenalph_m1 = len(alph) - 1

# and now, to work
ixs = [0] * x
while True:
yield ''.join(imap(getalph, reversed(ixs)))
for pos, ix in enumerate(ixs):
if ix == lenalph_m1:
ixs[pos] = 0
else:
ixs[pos] = ix + 1
break
else:
break


Alex

 

[Hung Jung Lu]

Does anyone know what this operation is called? It's not permutations or
combinations as I understand them since permutations and combinations do
not allow repetition. I assume there was already a solution for this
somewhere, but I didn't know what term to google for.

---------------------------------------------------

There's been a recent thread where the OP called them 'permutations',
somebody commented they're 'variations'. In that thread you'll find a
bazillion solutions, recursive and non, with or without itertools, &c.

---------------------------------------------------

(1) "Variation" is the same as "permutation". It's matter of
semantics. Some people use the notation V(n, k), some people use the
notation P(n, k). For people that use the term "variation", the term
"permutation" is reserved for the special case V(n, n). Neither name
is right for the original question.

(2) I too googled for the name of the operation of the original
poster. One name I found is "string" (see
http://mathworld.wolfram.com/BallPicking.html). However, this name may
not be universally recognized.

(3) The functional version would be:

strings = lambda Xs, k: reduce(lambda r, i: [p + x for p in r for x
in Xs], range(k), [''])

print strings('abc', 2)

Hung Jung

 

[Stephen Waterbury]

... The functional version would be:

strings = lambda Xs, k: reduce(lambda r, i: [p + x for p in r for x
in Xs], range(k), [''])

Wow! Grand prize for elegance.

 

[Alex Martelli]

... The functional version would be:

strings = lambda Xs, k: reduce(lambda r, i: [p + x for p in r for x
in Xs], range(k), [''])

Wow! Grand prize for elegance.

And almost for performance -- it's an order of magnitude faster than
other ones I've timed. Of course, as usual, you can get another 10% or
so if you avoid reduce and lambda, implementing exactly the same
algorithm as:

def stringo(Xs, k):
r = ['']
for i in range(k):
r = [p+x for p in r for x in Xs]
return r

$ python -m timeit -s'import ov' 'ov.strings("abc",3)'
10000 loops, best of 3: 144 usec per loop
$ python -m timeit -s'import ov' 'ov.strings("abc",3)'
10000 loops, best of 3: 142 usec per loop

$ python -m timeit -s'import ov' 'ov.stringo("abc",3)'
10000 loops, best of 3: 126 usec per loop
$ python -m timeit -s'import ov' 'ov.stringo("abc",3)'
10000 loops, best of 3: 125 usec per loop


Alex

 

[Michael J. Fromberger]

def lexgen(alph, maxlen = None):
"""Generate all the possible strings over the given alphabet in
lexicographic order. Stop after generating the strings of maxlen,
if provided; otherwise, generate forever."""

ixs = []

while maxlen is None or len(ixs) <= maxlen:
while True:
yield str.join('', [ alph[ixs[x]] for x in
xrange(len(ixs) - 1, -1, -1) ])

for pos in xrange(len(ixs)):
ixs[pos] = (ixs[pos] + 1) % len(alph)
if ixs[pos] <> 0:
break

if sum(ixs) == 0:
break

ixs += [0]

Nice, and different from what was offered in the other recent thread
(and from what the OP asked for) since you generate all strings of
length up to maxlen, while the request was for just those of length
exactly x. Still, this can easily be restricted, and maybe a few
Pythonic tweaks with it...:

Hi, Alex,

Thanks for the feedback, you make some good points.

In 2.4 one can do a bit better for the yield, with

yield ''.join(alph for i in reversed(ixs))

[generator expression vs list comprehension, and reversed built-in vs
reversal by slicing].

Yes, I'm aware of both of those improvements, but since I do not yet
have Python 2.4, I did not use any of its new features in my solution.

In any case, thank you for the helpful comments on both sides of the 2.4
divide.

Cheers,
-M

 

[Alex Martelli]

Michael J. Fromberger <[email protected]>
wrote:
...

In 2.4 one can do a bit better for the yield, with

yield ''.join(alph for i in reversed(ixs))

[generator expression vs list comprehension, and reversed built-in vs
reversal by slicing].

Yes, I'm aware of both of those improvements, but since I do not yet
have Python 2.4, I did not use any of its new features in my solution.

Everybody's strongly urged to download and try 2.4 beta 1. We think
it's quite solid and speedy, but unless users validate that on their
huge variety of platforms and programs, how can we be _sure_?

In any case, thank you for the helpful comments on both sides of the 2.4
divide.

You're welcome! Also note that on the other branch of this thread a
non-recursive, list based solution was posted that's about an order of
magnitude faster for short alph and small values of k (not applicable to
the general problem of yielding an unbounded sequence of strings, but
useful for the original problem where the sequence of strings was
specified to be reasonably small).


Alex

 

[Terry Reedy]

again. I am looking for a list of all unique strings of length x whose
elements are from the set a, b, and c.

So, for example, in this case it would be

aaa, aab, aac, aba, abb, abc, aca, acb, acc, ... cca, ccb, ccc

This is equivalent to finding all n digit base k numbers, where k is the
size of the set and where numbers are padded on the left with 0s. You
example above is equivalent to

000, 001, 002, 010, 011, 012, 020, 021, 022, ... 330, 331, 333

There are lots of related algorithms for this set/sequence of N=n**k
formatted numbers. Which you really want depends on questions like:

Do you *really*need character strings or would range(N) or xrange(N)
actually do as well? Since the latter is obviously trivial, think about
whether the application can be changed a bit to use numbers instead of
string representations thereof.

Do you need to use an arbitrary set of characters or would a standard set
'0', '1', ... do as well?

Do you you need the N=n**k strings all at once in an explicit list or set
or will a generator producing them one at a time do?

Do you need them ordered, and if so, in any particular order, whether in a
list or from a generator?

Terry J. Reedy

 

[Thorsten Kampe]

* Hung Jung Lu (2004-10-24 04:16 +0100)
Sorry, no.

It's matter of semantics.

It's a matter of definition and the definitions of both don't have
anything in common.

Some people use the notation V(n, k), some people use the notation
P(n, k). For people that use the term "variation", the term
"permutation" is reserved for the special case V(n, n).

That's misleading: the special case of a variation without repetition
of the nth degree is the same as a permutation without repetition of
that set. But the definitions of both are very different.

Variations /with/ repetition are also equal to the "cartesian product"
of the set with itself. But that doesn't mean that "cartesian product"
and variation (with repetition) are the same.

Let me explain:
In combinatorics there are two distinct kinds of "operations":
permutations and combinations[1].

PERMUTATIONS
____________
A permutation is a "bijective mapping on itself" which means that each
permutation has the same length and consists of all elements of the
original set.

Permutations are divided into
* permutations without repetition = n!
* permutations with repetition = n! / (s1! * ... * sr!)

For instance:
[11, 22, 33, 44, 55, 66, 77] has 7! = 5040 different permutations
(without repetition)

[11, 22, 22, 33, 44, 44, 44] has 7! / (2! * 3!) = 420 different
permutations (with repetition)

COMBINATIONS
____________
A combination is a subset of the original set (also sometimes
described as "ball picking". "Repetition" is sometimes called "putting
back").

Combinations are divided into
* unordered combinations without repetition
* unordered combinations with repetition
* ordered combinations without repetition
* ordered combinations with repetition

Of course that was too difficult to remember even for a mathematician
so it was decided (about one hundred years ago) that ordered
combinations should now be called "variations" and unordered
combinations should now be called "combinations".

So since then there are:
* combinations without repetition = n! / (k! * (n - k)!)
* combinations with repetition = (n + k - 1)! / ((n - 1)! * k!)
* variations without repetition = n! / (n - k)!
* variations with repetition = n ** k

And this is where the confusion starts:

* the binomial coefficient "(n over k) = n! / (k! * (n - k)!)" is
sometimes called C(n, k).

* "n! / (n - k)!" is sometimes called P(n, k)

So you can also give the number of different combinations and
variations like this:
* combinations without repetition = C(n, k)
* combinations with repetition = C(n + k - 1, k)
* variations without repetition = P(n, k)


Thorsten

[1] For a quick overview have a look at
http://www.eco.uc3m.es/stefan/phd-sum/probl2004.pdf

 

[Thorsten Kampe]

* Hung Jung Lu (2004-10-24 04:16 +0100)

---------------------------------------------------

---------------------------------------------------

(1) "Variation" is the same as "permutation". It's matter of
semantics. Some people use the notation V(n, k), some people use the
notation P(n, k). For people that use the term "variation", the term
"permutation" is reserved for the special case V(n, n). Neither name
is right for the original question.

Well in fact it's a variation with repetition of the length 3 (or the
cartesian product "['a', 'b', 'c'] ** 3").

With the cvp[1] utility you could generate that like:

l = ['a', 'b', 'c']
util.cvp(l, 3, '#vr') # make sure it doesn't grow too big 27
util.cvp(l, 3, 'vr')

[['a', 'a', 'a'],
['a', 'a', 'b'],
['a', 'a', 'c'],
['a', 'b', 'a'],
['a', 'b', 'b'],
['a', 'b', 'c'],
['a', 'c', 'a'],
['a', 'c', 'b'],
['a', 'c', 'c'],
['b', 'a', 'a'],
['b', 'a', 'b'],
['b', 'a', 'c'],
['b', 'b', 'a'],
['b', 'b', 'b'],
['b', 'b', 'c'],
['b', 'c', 'a'],
['b', 'c', 'b'],
['b', 'c', 'c'],
['c', 'a', 'a'],
['c', 'a', 'b'],
['c', 'a', 'c'],
['c', 'b', 'a'],
['c', 'b', 'b'],
['c', 'b', 'c'],
['c', 'c', 'a'],
['c', 'c', 'b'],
['c', 'c', 'c']]

Or like that:
Thorsten

[1] cvp = "combinations, variations and permutations"
http://www.thorstenkampe.de/python/util.py

 

[Thorsten Kampe]

* Steven Bethard (2004-10-23 21:56 +0100)

Does anyone know what this operation is called?

"variation with repetition"
(or the "cartesian product": ['a', 'b', 'c'] ** 3)

It's not permutations or combinations as I understand them since
permutations and combinations do not allow repetition.

Both of them do allow (because there are two kinds - with and without
repetition - for both of them) (see my other reply in the thread).

Thorsten

 

[Hung Jung Lu]

Sorry, no.

Sorry, yes. Please learn to accept the fact that a word
("permutation", in this case) can have several definitions. You are
not the Pope of mathematics, and there is none. Different people
define it different ways. Your definition is by no way the only
accepted definition. You have been raised one school of
notation/terminology, other people have been raised in another school
of notation/terminology. What the French call "body" ("corps"), the
American call it "field" ("champ") as in "the Real Number Field, the
Complex Number Field". Many examples like that.

* variations without repetition = P(n, k)

Funny, "variation" starts with the letter "v", where do you think the
"P" as in your "P(n, k)" come from? Surely not from "Pariation",
right? The fact that you see the "P(n, k)" notation shows you that
many people call this function "permutation". You simply were raised
in a particular school of terminology and were not aware that another
school of terminology existed.

What you have called ""variation with repetition", other people call
it "string". As I said, you are not the Pope of mathematics, and don't
expect other people will agree with your terminology.

Learn to accept the fact that what you call "variation", other people
call it "permutation". Like it or not, it's a fact. Now, re-read the
following sentence:

and try to understand what I was saying:

Your "variation" == Other people's "permutation"

is that clear, now?

Please check
http://mathworld.wolfram.com/BallPicking.html
which I have pointed out in my earlier message and which you did not
bother to read, at all. I would say the majority of students in the
U.S.A. are trained with the terminology convention I use. Surely the
usage of the term "variation" is also popular, but I would say that at
present it constitutes the minority, not the majority.

As I said, It's matter of semantics.

regards,

Hung Jung

 

[Hung Jung Lu]

* Hung Jung Lu (2004-10-24 04:16 +0100)

Sorry, no.

Sorry, yes.

Just to add some more information, see also:

(1) http://en.wikipedia.org/wiki/Combinatorics

(2) Download user manuals from any major scientific calculator maker
(HP, Casio, Texas Instruments, Sharp, etc.), and you will find them
all using the term "permutation" instead of "variation". E.g.:

http://www.hp.com/calculators/docs/guides/33sProbFact.pdf

You can promote your preferred term ("variation") as much as you want,
but to ignore the fact that the majority of people use the term
"permutation" is a bit strange, to say the least.

Hung Jung

 

[Thorsten Kampe]

* Hung Jung Lu (2004-11-15 07:05 +0100)

Sorry, yes. Please learn to accept the fact that a word
("permutation", in this case) can have several definitions. You are
not the Pope of mathematics, and there is none. Different people
define it different ways. Your definition is by no way the only
accepted definition. You have been raised one school of
notation/terminology, other people have been raised in another school
of notation/terminology. What the French call "body" ("corps"), the
American call it "field" ("champ") as in "the Real Number Field, the
Complex Number Field". Many examples like that.


Funny, "variation" starts with the letter "v", where do you think the
"P" as in your "P(n, k)" come from? Surely not from "Pariation",
right? The fact that you see the "P(n, k)" notation shows you that
many people call this function "permutation". You simply were raised
in a particular school of terminology and were not aware that another
school of terminology existed.

What you have called ""variation with repetition", other people call
it "string". As I said, you are not the Pope of mathematics, and don't
expect other people will agree with your terminology.

Learn to accept the fact that what you call "variation", other people
call it "permutation". Like it or not, it's a fact. Now, re-read the
following sentence:


and try to understand what I was saying:

Your "variation" == Other people's "permutation"

is that clear, now?

Please check
http://mathworld.wolfram.com/BallPicking.html
which I have pointed out in my earlier message and which you did not
bother to read, at all. I would say the majority of students in the
U.S.A. are trained with the terminology convention I use. Surely the
usage of the term "variation" is also popular, but I would say that at
present it constitutes the minority, not the majority.

Reading some articles in the Wikipedia I have to partly (well, maybe
even mostly) agree with you. Variations are in fact other peoples'
permutations in /popular/ math.

But I think the fact you're missing (and I tried to explain) is that
this use is deprecated and abandoned in scientific math for more than
a hundred years (since the rise of modern set theory).

Combinatorics (in its old use) is much older than set theory. It's
still one of the most applied fields (in its "ball picking" sense) for
gambling and other things. That's why the old habits die so slowly.
I've searched books from the fifties where variations still were
called "unordered combinations".

But combinatorics isn't "ball picking with and without 'putting back'"
anymore and so the old use of permutation isn't "official" anymore.

Two reasons for that are immediately understandable:

1. The old use of permutation always meant "unordered k-sets without
repetition". There simply was no name for "variations with
repetition".

That's why you stated 'For people that use the term "variation", the
term "permutation" is reserved for the special case V(n, n). Neither
name is right for the original question". And that's why people had to
invent names like "string" for this "thing without a name" - while in
scientific combinatorics it already had a name: variation with
repetition (or cartesian product in set theory).

2. Combinatorics isn't just "ball picking" anymore. It includes
"modern style" permutations (n!) - with and without repetition. That's
why the old use of permutation (that was used in "ball picking") isn't
used in scientific math and combinatorics anymore. There simply was no
way to teach combinatorics using "old" and "new" permutations.

And one word at the end: I'm not the pope of math. I did study math
for two years and even if I had a degree this wouldn't make me the
pope. I was trying to explain things, not to declare them.

Before I wrote my "cvp" program I did an exhaustive research (not on
the Internet) because I was very confused about the popular
terminology.

If you use (and think in) the new terminology combinatorics and it's
several cases are very clear and distinct: permutations, variations
and combinations with and without repetition. Six clearly categorized
cases.

And remember: the "new" use isn't that new (a hundred years and more).
If you continue to use the old terms of popular math you're
manifesting the existing confusion (and make people invent new names
like "string").

Thorsten