474,003 Members | 9,596 Online

# simple recursion help

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()

-d
Jul 18 '05 #1
20 3167
"drs" <dr*@remove-to-send-mail-ecpsoftware.com > wrote in message
news:Gp******** ***********@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
Jul 18 '05 #2
drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:

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/Coo.../Recipe/190465

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

Steve

Jul 18 '05 #3
drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:
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:
def f(chars, n): .... 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

Jul 18 '05 #4
drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:

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

Jul 18 '05 #5
Steven Bethard <st************ @gmail.com> wrote:
drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:

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.

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
Jul 18 '05 #6
In article <ma************ *************** ***********@pyt hon.org>,
Steven Bethard <st************ @gmail.com> wrote:
drs <drs <at> remove-to-send-mail-ecpsoftware.com > writes:

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.

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
Jul 18 '05 #7
Michael J. Fromberger <Mi************ ******@Clothing .Dartmouth.EDU>
wrote:
...
I am looking for a list of all unique strings of length x whose
elements are from the set a, b, and c.
... 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[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
Jul 18 '05 #8
Steven Bethard <st************ @gmail.com> wrote:
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. ---------------------------------------------------
al*****@yahoo.c om (Alex Martelli) wrote: 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 "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
Jul 18 '05 #9
Hung Jung Lu wrote:
... 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. :)
Jul 18 '05 #10

This thread has been closed and replies have been disabled. Please start a new discussion.