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.trai ts):
l.append(self.b (str(i)))
return l

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


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


Thanks in advance,

-d

[drs]

Re: simple recursion help

"drs" <drs@remove-to-send-mail-ecpsoftware.com > wrote in message
news:Gpyed.3200 58$bp1.6526@twi ster.nyroc.rr.c om...
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]

Re: simple recursion help

drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:[color=blue]
>
> Hi, I am trying to find all lists of length x with elements a, b, and c.[/color]

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]

Re: simple recursion help

drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:
[color=blue]
> 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.[/color]


Much clearer, thanks. Is this what you're looking for:
[color=blue][color=green][color=darkred]
>>> def f(chars, n):[/color][/color][/color]
.... for char in chars:
.... if n == 1:
.... yield char
.... else:
.... for string in f(chars, n-1):
.... yield char + string
....[color=blue][color=green][color=darkred]
>>> list(f('abc', 1))[/color][/color][/color]
['a', 'b', 'c'][color=blue][color=green][color=darkred]
>>> list(f('abc', 2))[/color][/color][/color]
['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc'][color=blue][color=green][color=darkred]
>>> list(f('abc', 3))[/color][/color][/color]
['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]

Re: simple recursion help

drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:[color=blue]
>
> I am looking for a list of all unique strings of length x whose
> elements are from the set a, b, and c.[/color]

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]

Re: simple recursion help

Steven Bethard <steven.bethard @gmail.com> wrote:
[color=blue]
> drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:[color=green]
> >
> > I am looking for a list of all unique strings of length x whose
> > elements are from the set a, b, and c.[/color]
>
> 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.[/color]

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]

Re: simple recursion help

In article <mailman.5375.1 098565018.5135. python-list@python.org >,
Steven Bethard <steven.bethard @gmail.com> wrote:
[color=blue]
> drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:[color=green]
> >
> > I am looking for a list of all unique strings of length x whose
> > elements are from the set a, b, and c.[/color]
>
> 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.[/color]

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

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

[Alex Martelli]

Re: simple recursion help

Michael J. Fromberger <Michael.J.From berger@Clothing .Dartmouth.EDU>
wrote:
...[color=blue][color=green][color=darkred]
> > > I am looking for a list of all unique strings of length x whose
> > > elements are from the set a, b, and c.[/color][/color][/color]
...[color=blue]
> 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][/color]

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[i] 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[i] 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[i] for i in ixs)
for pos in reversed(xrange (x)):
...

or, after a 'from itertools import imap':

yield ''.join(imap(al ph.__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(ge talph, 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]

Re: simple recursion help

Steven Bethard <steven.bethard @gmail.com> wrote:[color=blue]
> 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.[/color]
---------------------------------------------------
aleaxit@yahoo.c om (Alex Martelli) wrote:[color=blue]
> 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.[/color]
---------------------------------------------------

(1) "Variation" is the same as "permutatio n". 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
"permutatio n" 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]

Re: simple recursion help

Hung Jung Lu wrote:[color=blue]
> ... 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), [''])[/color]

Wow! Grand prize for elegance. :)

[Alex Martelli]

Re: simple recursion help

Stephen Waterbury <golux@comcast. net> wrote:
[color=blue]
> Hung Jung Lu wrote:[color=green]
> > ... 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), [''])[/color]
>
> Wow! Grand prize for elegance. :)[/color]

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("ab c",3)'
10000 loops, best of 3: 144 usec per loop
$ python -m timeit -s'import ov' 'ov.strings("ab c",3)'
10000 loops, best of 3: 142 usec per loop

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


Alex

[Michael J. Fromberger]

Re: simple recursion help

In article <1gm4vyt.1eykww 1d7p0i8N%aleaxi t@yahoo.com>,
aleaxit@yahoo.c om (Alex Martelli) wrote:
[color=blue]
> Michael J. Fromberger <Michael.J.From berger@Clothing .Dartmouth.EDU>
> wrote:[color=green]
> >
> > 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][/color]
>
> 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...:[/color]

Hi, Alex,

Thanks for the feedback, you make some good points.
[color=blue]
> In 2.4 one can do a bit better for the yield, with
>
> yield ''.join(alph[i] for i in reversed(ixs))
>
> [generator expression vs list comprehension, and reversed built-in vs
> reversal by slicing].[/color]

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

--
Michael J. Fromberger | Lecturer, Dept. of Computer Science
http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA

[Alex Martelli]

Re: simple recursion help

Michael J. Fromberger <Michael.J.From berger@Clothing .Dartmouth.EDU>
wrote:
...[color=blue][color=green]
> > In 2.4 one can do a bit better for the yield, with
> >
> > yield ''.join(alph[i] for i in reversed(ixs))
> >
> > [generator expression vs list comprehension, and reversed built-in vs
> > reversal by slicing].[/color]
>
> 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.[/color]

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_?
[color=blue]
> In any case, thank you for the helpful comments on both sides of the 2.4
> divide.[/color]

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]

Re: simple recursion help


"drs" <drs@remove-to-send-mail-ecpsoftware.com > wrote in message
news:VUyed.3200 61$bp1.273357@t wister.nyroc.rr .com...[color=blue]
> 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[/color]

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]

Re: simple recursion help

* Hung Jung Lu (2004-10-24 04:16 +0100)[color=blue]
> Steven Bethard <steven.bethard @gmail.com> wrote:[color=green]
>> 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.[/color]
> ---------------------------------------------------
> aleaxit@yahoo.c om (Alex Martelli) wrote:[color=green]
>> 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.[/color]
> ---------------------------------------------------
>
> (1) "Variation" is the same as "permutatio n".[/color]

Sorry, no.
[color=blue]
> It's matter of semantics.[/color]

It's a matter of definition and the definitions of both don't have
anything in common.
[color=blue]
> 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
> "permutatio n" is reserved for the special case V(n, n).[/color]

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 "combinatio ns".

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