counting using variable length string as base

Discussion in 'Python' started by Grimsqueaker, Mar 27, 2008.

  1. Grimsqueaker

    Grimsqueaker Guest

    Hi, I'm fairly new to Python and to this list. I have a problem that
    is driving me insane, sorry if it seems simple to everyone, I've been
    fighting with it for a while. :))

    I want to take a variable length string and use it as a base for
    counting, eg. given the string 'abc' the sequence would be:

    a
    b
    c
    aa
    ba
    ca
    ab
    bb
    cb
    ....
    ccc

    Basically I want to find every possible order of every combination.
    Its easy if you know how many characters there will be in your string
    (use nested for loops), but I am stuck with the variable length
    string. I think I have to use a generator but I'm not sure exactly
    how.

    Can anyone give me a pointer in the right direction?

    Thanks
    Daniel Browne
    Grimsqueaker, Mar 27, 2008
    #1
    1. Advertising

  2. Grimsqueaker

    Dan Bishop Guest

    On Mar 27, 1:15 am, Grimsqueaker <> wrote:
    > Hi, I'm fairly new to Python and to this list. I have a problem that
    > is driving me insane, sorry if it seems simple to everyone, I've been
    > fighting with it for a while. :))
    >
    > I want to take a variable length string and use it as a base for
    > counting, eg. given the string 'abc' the sequence would be:
    >
    > a
    > b
    > c
    > aa
    > ba
    > ca
    > ab
    > bb
    > cb
    > ...
    > ccc
    >
    > Basically I want to find every possible order of every combination.
    > Its easy if you know how many characters there will be in your string
    > (use nested for loops), but I am stuck with the variable length
    > string. I think I have to use a generator but I'm not sure exactly
    > how.
    >
    > Can anyone give me a pointer in the right direction?


    def cartesian_product(*args):
    """Iterates over the Cartesian product of args[0], args[1], ..."""
    if not args:
    return
    elif len(args) == 1:
    for item in args[0]:
    yield (item,)
    else:
    for item in args[0]:
    for item2 in cartesian_product(*args[1:]):
    yield (item,) + item2

    def string_cartesian_product(*args):
    return (''.join(combo) for combo in cartesian_product(*args))
    Dan Bishop, Mar 27, 2008
    #2
    1. Advertising

  3. Grimsqueaker

    Grimsqueaker Guest

    That seems to give me the items in the list back in an iterator. Am I
    using it incorrectly?
    Grimsqueaker, Mar 27, 2008
    #3
  4. Grimsqueaker

    Guest

    On Mar 27, 2:33 am, Grimsqueaker <> wrote:
    > That seems to give me the items in the list back in an iterator. Am I
    > using it incorrectly?


    Use list( it ).
    , Mar 27, 2008
    #4
  5. Grimsqueaker schrieb:
    > That seems to give me the items in the list back in an iterator. Am I
    > using it incorrectly?


    No. Just put a list() around it.

    Diez
    Diez B. Roggisch, Mar 27, 2008
    #5
  6. On Thu, 27 Mar 2008 00:33:21 -0700, Grimsqueaker wrote:

    > That seems to give me the items in the list back in an iterator. Am I
    > using it incorrectly?


    Given an iterator, you use it like this:

    for item in iterator:
    print item # or do something else


    If you're sure that the iterator is relatively small, you can do this:

    give_me_everything_at_once = list(iterator)


    but don't try that with this one:


    def ones(): # never-ending series of ones
    while True:
    yield 1

    iterator = ones()


    --
    Steven
    Steven D'Aprano, Mar 27, 2008
    #6
  7. Grimsqueaker

    Grimsqueaker Guest

    OK, got that. If I use:

    for x in string_cartesian_product('abc'):
    print x

    I get:

    a
    b
    c

    What am I not understanding?

    Thank you
    Grimsqueaker, Mar 27, 2008
    #7
  8. Grimsqueaker

    Peter Otten Guest

    Grimsqueaker wrote:

    > That seems to give me the items in the list back in an iterator. Am I
    > using it incorrectly?


    With Dan's functions in cartesian.py you can do the following:

    >>> from cartesian import *
    >>> def count(digits):

    .... args = []
    .... while 1:
    .... args.append(digits)
    .... for n in string_cartesian_product(*args):
    .... yield n
    ....
    >>> from itertools import islice
    >>> print " ".join(islice(count("abc"), 30))

    a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc baa bab
    bac bba bbb bbc bca bcb bcc

    Peter
    Peter Otten, Mar 27, 2008
    #8
  9. Grimsqueaker

    Guest

    On Mar 27, 4:01 am, Peter Otten <> wrote:
    > Grimsqueaker wrote:
    > > That seems to give me the items in the list back in an iterator. Am I
    > > using it incorrectly?

    >
    > With Dan's functions in cartesian.py you can do the following:
    >
    > >>> from cartesian import *
    > >>> def count(digits):

    >
    > ...     args = []
    > ...     while 1:
    > ...             args.append(digits)
    > ...             for n in string_cartesian_product(*args):
    > ...                     yield n
    > ...>>> from itertools import islice
    > >>> print " ".join(islice(count("abc"), 30))

    >
    > a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc baa bab
    > bac bba bbb bbc bca bcb bcc


    For the base, we Arabics use the cardinal; what letters you count in
    doesn't change anything. Don't just spell out numbers, unless: Are
    you reading marked-tally. Or do you want to yield a word and see the
    number that it spells out to? Be there or be around. I'm bad at
    spelling, but I can rearrange linear.
    , Mar 27, 2008
    #9
  10. Grimsqueaker

    Graeme Glass Guest

    On Mar 27, 11:01 am, Peter Otten <> wrote:
    > Grimsqueaker wrote:
    > > That seems to give me the items in the list back in an iterator. Am I
    > > using it incorrectly?

    >
    > With Dan's functions in cartesian.py you can do the following:
    >
    > >>> from cartesian import *
    > >>> def count(digits):

    >
    > ... args = []
    > ... while 1:
    > ... args.append(digits)
    > ... for n in string_cartesian_product(*args):
    > ... yield n
    > ...>>> from itertools import islice
    > >>> print " ".join(islice(count("abc"), 30))

    >
    > a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc baa bab
    > bac bba bbb bbc bca bcb bcc
    >
    > Peter


    Here is a cool solution we came up with during a little interactive
    session at our local meet up.
    (http://www.python.org.za/pugs/cape-town/cape-town)

    s = 'abcdef'
    ["".join([s[j] for j in range(len(s)) if x & (1 << j)]) for x in
    range(1,2**len(s)) ]
    http://groups.google.com/group/ctpug/browse_thread/thread/986aab83f9782f6c

    Regards,

    Graeme
    Graeme Glass, Mar 31, 2008
    #10
  11. En Mon, 31 Mar 2008 09:30:00 -0300, Graeme Glass <>
    escribió:

    > On Mar 27, 11:01 am, Peter Otten <> wrote:
    >> a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc
    >> baa bab
    >> bac bba bbb bbc bca bcb bcc

    >
    > Here is a cool solution we came up with during a little interactive
    > session at our local meet up.
    > (http://www.python.org.za/pugs/cape-town/cape-town)
    >
    > s = 'abcdef'
    > ["".join([s[j] for j in range(len(s)) if x & (1 << j)]) for x in
    > range(1,2**len(s)) ]


    But it's doesn't generate the right sequence, and a lot of elements are
    missing. For 'abc':
    ['a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
    It lacks ba, bb, ca, cb, cc, all b??, all c?? - see the sequence quoted
    above.

    --
    Gabriel Genellina
    Gabriel Genellina, Mar 31, 2008
    #11
  12. Grimsqueaker

    David Fraser Guest

    On Mar 31, 8:18 pm, "Gabriel Genellina" <>
    wrote:
    > En Mon, 31 Mar 2008 09:30:00 -0300, Graeme Glass <>
    > escribió:
    >
    > > On Mar 27, 11:01 am, Peter Otten <> wrote:
    > >> a b c aa ab ac ba bb bc ca cb cc aaa aab aac aba abb abc aca acb acc
    > >> baa bab
    > >> bac bba bbb bbc bca bcb bcc

    >
    > > Here is a cool solution we came up with during a little interactive
    > > session at our local meet up.
    > > (http://www.python.org.za/pugs/cape-town/cape-town)

    >
    > > s = 'abcdef'
    > > ["".join([s[j] for j in range(len(s)) if x & (1 << j)]) for x in
    > > range(1,2**len(s)) ]

    >
    > But it's doesn't generate the right sequence, and a lot of elements are
    > missing. For 'abc':
    > ['a', 'b', 'ab', 'c', 'ac', 'bc', 'abc']
    > It lacks ba, bb, ca, cb, cc, all b??, all c?? - see the sequence quoted
    > above.


    Indeed, the following shold do the trick although it's fairly
    inefficient:
    n=(len(s)+1) ; z = [''] + list(s) ; all =
    sorted(dict.fromkeys("".join(z[(x/(n**j))%n] for j in range(n)) for x
    in range(1,n**n)))

    Cheers
    David
    David Fraser, Apr 1, 2008
    #12
  13. Grimsqueaker

    Paul Rubin Guest

    Grimsqueaker <> writes:
    > Basically I want to find every possible order of every combination.
    > Its easy if you know how many characters there will be in your string
    > (use nested for loops), but I am stuck with the variable length
    > string. I think I have to use a generator but I'm not sure exactly how.
    >
    > Can anyone give me a pointer in the right direction?


    The basic idea is to use recursion to get the effect of nested for loops
    except to an arbitrary depth. You don't need a generator.
    Paul Rubin, Apr 1, 2008
    #13
  14. Grimsqueaker

    rootkill Guest

    On Mar 27, 8:15 am, Grimsqueaker <> wrote:
    > Hi, I'm fairly new to Python and to this list. I have a problem that
    > is driving me insane, sorry if it seems simple to everyone, I've been
    > fighting with it for a while. :))
    >
    > I want to take a variable length string and use it as a base for
    > counting, eg. given the string 'abc' the sequence would be:
    >
    > a
    > b
    > c
    > aa
    > ba
    > ca
    > ab
    > bb
    > cb
    > ...
    > ccc
    >
    > Basically I want to find every possible order of every combination.
    > Its easy if you know how many characters there will be in your string
    > (use nested for loops), but I am stuck with the variable length
    > string. I think I have to use a generator but I'm not sure exactly
    > how.
    >
    > Can anyone give me a pointer in the right direction?
    >
    > Thanks
    > Daniel Browne


    Since you didn't ask for the smallest solution I'll opt for the
    clearest one ;)

    I'll use the very usefull baseconvert,
    http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/111286

    def baseconvert(number, fromdigits, todigits):
    if str(number)[0] == '-':
    number = str(number)[1:]
    neg = 1
    else:
    neg = 0

    # make an integer out of the number
    x = long(0)
    for digit in str(number):
    x = x * len(fromdigits) + fromdigits.index(digit)

    # create the result in base 'len(todigits)'
    res = ''
    if x == 0:
    res = todigits[0]

    while x > 0:
    digit = x % len(todigits)
    res = todigits[digit] + res
    x /= len(todigits)

    if neg:
    res = '-' + res

    return res

    BASE10 = '0123456789'
    s = 'abcdef'
    n = len(s)

    for i in xrange(n**n):
    print baseconvert(str(i), BASE10, s)

    You can also convert back, baseconvert('abaa', s, BASE10).
    Hope it helps.

    Regards, Louis.
    rootkill, Apr 1, 2008
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Sam
    Replies:
    3
    Views:
    14,091
    Karl Seguin
    Feb 17, 2005
  2. pembed2003
    Replies:
    8
    Views:
    4,776
    Default User
    Jun 7, 2004
  3. Replies:
    5
    Views:
    662
    John W. Kennedy
    Jan 11, 2007
  4. Sandman
    Replies:
    7
    Views:
    199
    Anno Siegel
    Aug 3, 2004
  5. edwardfredriks

    counting up instead of counting down

    edwardfredriks, Sep 6, 2005, in forum: Javascript
    Replies:
    6
    Views:
    197
    Dr John Stockton
    Sep 7, 2005
Loading...

Share This Page