counting using variable length string as base

[Grimsqueaker]

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

 

[Dan Bishop]

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

 

[Grimsqueaker]

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

 

[castironpi]

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

Use list( it ).

 

[Diez B. Roggisch]

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

 

[Steven D'Aprano]

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

 

[Grimsqueaker]

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

 

[Peter Otten]

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:
.... args = []
.... while 1:
.... args.append(digits)
.... for n in string_cartesian_product(*args):
.... yield n
....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

 

[castironpi]

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:

...     args = []
...     while 1:
...             args.append(digits)
...             for n in string_cartesian_product(*args):
...                     yield n
...>>> from itertools import islice
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.

 

[Graeme Glass]

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:

... args = []
... while 1:
... args.append(digits)
... for n in string_cartesian_product(*args):
... yield n
...>>> from itertools import islice
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

 

[Gabriel Genellina]

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.

 

[David Fraser]

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

 

[Paul Rubin]

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.

 

[rootkill]

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.