counting using variable length string as base
Grimsqueaker
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
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
using it incorrectly?
casti...@gmail.com
> 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()
--
Steven
Grimsqueaker
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:
>>> 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
casti...@gmail.com
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
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
escribió:
> On Mar 27, 11:01 am, Peter Otten <__pete...@web.de> 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
David Fraser
wrote:
> En Mon, 31 Mar 2008 09:30:00 -0300, Graeme Glass <graemegl...@gmail.com>
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
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.