FAQ
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

Search Discussions

  • Drs at Oct 23, 2004 at 8:10 pm
    "drs" <drs at remove-to-send-mail-ecpsoftware.com> wrote in message
    news:Gpyed.320058$bp1.6526 at twister.nyroc.rr.com...
    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 at Oct 23, 2004 at 8:30 pm

    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
  • Steven Bethard at Oct 23, 2004 at 8:56 pm

    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
  • Alex Martelli at Oct 23, 2004 at 9:40 pm

    Steven Bethard 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
  • Hung Jung Lu at Oct 24, 2004 at 3:16 am

    Steven Bethard 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.
    ---------------------------------------------------
    aleaxit at yahoo.com (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 "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 at Oct 24, 2004 at 4:55 am

    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. :)
  • Alex Martelli at Oct 24, 2004 at 8:26 am

    Stephen Waterbury wrote:

    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. :)
    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
  • Thorsten Kampe at Nov 14, 2004 at 1:23 pm
    * Hung Jung Lu (2004-10-24 04:16 +0100)
    Steven Bethard 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.
    ---------------------------------------------------
    aleaxit at yahoo.com (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 "permutation".
    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
  • Hung Jung Lu at Nov 15, 2004 at 6:05 am

    Thorsten Kampe wrote:
    (1) "Variation" is the same as "permutation".
    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:
    (1) "Variation" is the same as "permutation".
    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
  • Thorsten Kampe at Nov 15, 2004 at 11:24 am
    * Hung Jung Lu (2004-11-15 07:05 +0100)
    Thorsten Kampe wrote:
    (1) "Variation" is the same as "permutation".
    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:
    (1) "Variation" is the same as "permutation".
    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
  • Hung Jung Lu at Nov 15, 2004 at 11:12 am

    Thorsten Kampe wrote:
    * Hung Jung Lu (2004-10-24 04:16 +0100)
    (1) "Variation" is the same as "permutation".
    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 at Nov 15, 2004 at 11:40 am
    * Hung Jung Lu (2004-11-15 12:12 +0100)
    Thorsten Kampe wrote:
    * Hung Jung Lu (2004-10-24 04:16 +0100)
    (1) "Variation" is the same as "permutation".
    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.
    It's not "my" preferred term. This guy Guido van Rossum (creator of
    the Python language and Benevolent Dictator for Life) uses permutation
    in the same sense:
    http://www.python.org/doc/current/ref/indentation.html .

    And it really isn't possible to use one word (permutation) in one
    field (combinatorics) with two totally distinct meanings. If you don't
    like "variation" then call it string or "unordered combinations" or
    whatever. But please not "permutation". You will confuse everyone
    including yourself.

    Thorsten
  • Thorsten Kampe at Nov 14, 2004 at 2:32 pm
    * Hung Jung Lu (2004-10-24 04:16 +0100)
    Steven Bethard 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.
    ---------------------------------------------------
    aleaxit at yahoo.com (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 "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:
    util.cartes(util.cartes(l, l), l, 'triple')
    Thorsten

    [1] cvp = "combinations, variations and permutations"
    http://www.thorstenkampe.de/python/util.py
  • Michael J. Fromberger at Oct 23, 2004 at 9:49 pm
    In article <mailman.5375.1098565018.5135.python-list at python.org>,
    Steven Bethard 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
  • Alex Martelli at Oct 23, 2004 at 10:24 pm
    Michael J. Fromberger 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(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
  • Michael J. Fromberger at Oct 24, 2004 at 11:58 am
    In article <1gm4vyt.1eykww1d7p0i8N%aleaxit at yahoo.com>,
    aleaxit at yahoo.com (Alex Martelli) wrote:
    Michael J. Fromberger wrote:
    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[i] 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

    --
    Michael J. Fromberger | Lecturer, Dept. of Computer Science
    http://www.dartmouth.edu/~sting/ | Dartmouth College, Hanover, NH, USA
  • Alex Martelli at Oct 24, 2004 at 1:51 pm
    Michael J. Fromberger wrote:
    ...
    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].
    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 at Oct 24, 2004 at 9:39 pm
    "drs" <drs at remove-to-send-mail-ecpsoftware.com> wrote in message
    news:VUyed.320061$bp1.273357 at twister.nyroc.rr.com...
    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 at Nov 14, 2004 at 2:39 pm
    * Steven Bethard (2004-10-23 21:56 +0100)
    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?
    "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
  • Steven Bethard at Oct 23, 2004 at 8:16 pm

    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/Cookbook/Python/Recipe/190465

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

    Steve

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedOct 23, '04 at 7:37p
activeNov 15, '04 at 11:40a
posts21
users8
websitepython.org

People

Translate

site design / logo © 2022 Grokbase