iterator? way of generating all possible combinations?

[akameswaran]

Ok, this is really irritating me. I'm sure there are different ways of
doing this - I'm interested in the algo, not the practical solution,
I'm more trying to play with iterators and recursion. I want to create
a program that generates every possible combination of a set of a n
dice, with s sides.

so I started with an iterator

class die(object):
def __init__(self,sides):
self.sides = range(1,sides+1)
def __iter__(self):
return self
def next(self):
self.sides = self.sides[1:] + [self.sides[0]]
return self.sides[-1]


now my thought was to create a recursive function to iterate through
all the dice combinations. Unfortunately... I'm coming up with a dead
end. I've tried working it out with different version of the die, ie
one that doesn't loop infinitely, but instead takes a starting
position. A vaiety of things, and yet I can't find a nice recursive
function that falls out of the die class.

Any ideas? or better terms to google? cuz I've tried.

Thanks

 

[Raymond Hettinger]

Ok, this is really irritating me. I'm sure there are different ways of
doing this - I'm interested in the algo, not the practical solution,
I'm more trying to play with iterators and recursion. I want to create
a program that generates every possible combination of a set of a n
dice, with s sides. . . .
Any ideas? or better terms to google? cuz I've tried.

There are several interesting tidbits in the ASPN Cookbook:


http://aspn.activestate.com/ASPN/search?query=combinations&section=PYTHONCKBK&type=Subsection

http://tinyurl.com/frxqz



Raymond

 

[Terry Reedy]

Ok, this is really irritating me. I'm sure there are different ways of
doing this - I'm interested in the algo, not the practical solution,
I'm more trying to play with iterators and recursion. I want to create
a program that generates every possible combination of a set of a n
dice, with s sides.

Are the dice identical or distinguishable (marked). In other words, with 2
dice, is 1,2 the same as 2,1 or different? Note that in most dice games,
such as craps, the dice are not distinguished, but probability calculations
must treast them as if they were to get the elementary events.

Terry Jan Reedy

 

[akameswaran]

Are the dice identical or distinguishable (marked). In other words, with 2
dice, is 1,2 the same as 2,1 or different? Note that in most dice games,
such as craps, the dice are not distinguished, but probability calculations
must treast them as if they were to get the elementary events.

they are distinct. This isn't necessarily about simulating a game. So
yes the dice are marked and I want to track those different
possibilties.

 

[akameswaran]

hmmm, just needed better search words, thanks

 

[Terry Reedy]

they are distinct. This isn't necessarily about simulating a game. So
yes the dice are marked and I want to track those different
possibilties.

Then your dice problem is equivalent to generating all n-digit base-d
numbers, which is also the n-fold cartesian product of a set with itself.
Sequential generation amounts to a 'plus-1' operation.

tjr

 

[akameswaran]

Well thanks for the mathematical restatement of my problem. I had
forgotten the proper terms. Searching on those terms generates some
interesting results.

However, none of the algo's I have checked will work with generated
sequences, or iterable classes, as posited in my first post.

While appropriate to the current domain, ie dice. What if you want
combinations of extrememely large lists, say 3 sets of 10 mil items.
In such a case, I really do want my sets to be generators rather than
lists or set objects.

This is what had me stumped before, and still has me stumped.

 

[Diez B. Roggisch]

Well thanks for the mathematical restatement of my problem. I had
forgotten the proper terms. Searching on those terms generates some
interesting results.

However, none of the algo's I have checked will work with generated
sequences, or iterable classes, as posited in my first post.

While appropriate to the current domain, ie dice. What if you want
combinations of extrememely large lists, say 3 sets of 10 mil items.
In such a case, I really do want my sets to be generators rather than
lists or set objects.

This is what had me stumped before, and still has me stumped.

def combinations(l, depth):
if depth == 1:
for element in l:
yield (element,)
else:
for element in l:
for rest in combinations(l, depth -1 ):
yield (element,) + rest

HTH,

Diez

 

[Scott David Daniels]

However, none of the algo's I have checked will work with generated
sequences, or iterable classes, as posited in my first post.

While appropriate to the current domain, ie dice. What if you want
combinations of extrememely large lists, say 3 sets of 10 mil items.
In such a case, I really do want my sets to be generators rather than
lists or set objects.

This is what had me stumped before, and still has me stumped.

class Counter(object):
def __init__(self, digits, iterable=None):
self.digits = digits
self.iterable = iterable
def __iter__(self):
for digit in self.digits:
single = digit,
if self.iterable is None:
yield single
else:
for rest in self.iterable:
yield single + rest

for v in Counter('ab', Counter('cd', Counter('ef', Counter('gh')))):
print v

This works with "iterables" (and produces), rather than "iterators",
which is vital to the operation.

--Scott David Daniels
(e-mail address removed)

 

[akameswaran]

This would only work for combinations of identical sets, and also does
not seem to work with generated sets, or iterators. Forgetting dice
for a moment. Say I have 3 very long files, and i want to generate the
combinations of lines in the files. This provides a well known
iterator for the example.

file1 = open('foo.txt')
file2 = open('bar.txt')
file3 = open('baz'.xt')

All examples I have seen and all attempts I have written generally do
something similar - which is they only iterates through the possible
combinations for the last element and do nothing for all other
elements.

I saw an interesting example that generates a nested function for the
given number of sets. While the example still didn't work with
generators as input, I think a little tweaking would make it work.

This should fulfill my requirements with a rather harsh limit of
python's max nesting depth (20?)

 

[akameswaran]

This works with "iterables" (and produces), rather than "iterators",
which is vital to the operation.

--Scott David Daniels
(e-mail address removed)

Sorry, it doesn't. It works with strings. It doesn't work with file,
it doesn't work with iterators I have created.

I have been using file objects as my test iterables for now - forgoing
any complications in my own iterables. such that my test bed has been:


f = open('word.txt')
f2 = open('word2.txt')
f3 = open('word3.txt')

for combo in [testable function here]
print combo


Each file contains the letter a through g on, with each letter on a
line. At least I don't feel as bad anymore. My first attempts
generate the same output, and a couple of my earlier attempts work
quite nicely with lists, and similar things. But I can't find anthing
that works generically with any iterable, nor anything that works with
generators.

 

[Scott David Daniels]

Sorry, it doesn't. It works with strings. It doesn't work with file,
it doesn't work with iterators I have created.

Sorry, "re-iterables". A file re-iterable is:

class FileReIterable(object):
def __init__(self, file):
if isinstance(file, basestring):
self.file = open(file, 'rU')
else:
self.file = file
def __iter__(self):
self.file.seek(0)
return iter(self.file)

This works if-and-only-if it is only in use once at a time.
If you have multiple simultaneous accesses, you need to do
something like:

class FileReIterable2(object):
def __init__(self, file):
if isinstance(file, basestring):
self.file = open(file, 'rU')
else:
self.file = file
def __iter__(self):
self.file.seek(0)
for line in self.file:
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

--Scott David Daniels
(e-mail address removed)

 

[akameswaran]

Sorry, "re-iterables". A file re-iterable is:

class FileReIterable(object):
def __init__(self, file):
if isinstance(file, basestring):
self.file = open(file, 'rU')
else:
self.file = file
def __iter__(self):
self.file.seek(0)
return iter(self.file)

This works if-and-only-if it is only in use once at a time.
If you have multiple simultaneous accesses, you need to do
something like:

class FileReIterable2(object):
def __init__(self, file):
if isinstance(file, basestring):
self.file = open(file, 'rU')
else:
self.file = file
def __iter__(self):
self.file.seek(0)
for line in self.file:
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

--Scott David Daniels
(e-mail address removed)

Since I was doing this as a self education excercise. When you say is
in use once and only once, you mean I can only use a single instance of
the class? I haven't even tested these yet, but I am very curious
about that statement. Why is it necessary to return a generator object
in the second example? If it's a real long explanation, feel free to
point me to some relvant texts. My practical problem was solved about
10 posts ago... but I am still trying to understand the behavior.

Thank you for you time.

AK

 

[Scott David Daniels]

Since I was doing this as a self education excercise. When you say is
in use once and only once, you mean I can only use a single instance of
the class?

No. This works:

f1 = FileReIterable("one.file")
f2 = FileReIterable("another.file")
... free uses of ...

This does not "work":

gen = FileReIterable("one.file")

for a in gen:
for b in gen:
print a, b

This does "work":

gen = FileReIterable2("one.file")

for a in gen:
for b in gen:
print a, b

That is, any instance of FileReIterable must not be used in a
context where it may be in the midst of iterating a file, gets
used to produce a result, and then must produce a result from
the original iteration.

If you think about what must happen to the file read pointer,
the reason for all of this should become clear.

--Scott David Daniels
(e-mail address removed)

 

[akameswaran]

No. This works:

f1 = FileReIterable("one.file")
f2 = FileReIterable("another.file")
... free uses of ...

This does not "work":

gen = FileReIterable("one.file")

for a in gen:
for b in gen:
print a, b

This does "work":

gen = FileReIterable2("one.file")

for a in gen:
for b in gen:
print a, b

That is, any instance of FileReIterable must not be used in a
context where it may be in the midst of iterating a file, gets
used to produce a result, and then must produce a result from
the original iteration.

If you think about what must happen to the file read pointer,
the reason for all of this should become clear.

--Scott David Daniels
(e-mail address removed)

Thanks for the explanation, the issue of the file pointer was pretty
clear - it's why I created multiple files. I just misunderstood what
you meant by use only one. What I did miss at first was the fact that
the file object is not re-iterable. Just plain dumb oversite.

Of course in the end I'm actually more concerned with writing my own
iterators or generators. I was to busy thinking my errors were in the
recursion to look at the iterable/reiterable issue. This is a working
version of the die class I started this thread with.

class die(object):
def __init__(self,sides):
self.sides=sides

self.next = 1
def next(self):
if self.next <= self.sides:
current = self.next
self.next +=1
return current
else:
self.next=1
raise StopIteration
def __iter__(self):
return self

 

[Jim Segrave]

This works if-and-only-if it is only in use once at a time.
If you have multiple simultaneous accesses, you need to do
something like:

class FileReIterable2(object):
def __init__(self, file):
if isinstance(file, basestring):
self.file = open(file, 'rU')
else:
self.file = file
def __iter__(self):
self.file.seek(0)
for line in self.file:
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

Hmm - I tried this with 'one.file' being just the lower case letters,
one per line:

class FileReIterable2(object):
def __init__(self, file):
if isinstance(file, basestring):
self.file = open(file, 'rU')
else:
self.file = file


def __iter__(self):
self.file.seek(0)
for line in self.file:
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)


gen = FileReIterable2("one.file")

for a in gen:
for b in gen:
print " ", a.strip(), b.strip()


gen = FileReIterable2("one.file")
for a in gen:
for b in gen:
print a.strip(), b.strip()

which didn't produce lines 'a a', 'a b', etc. It produced the single
line 'a a', then stopped. A judicious proint or two showed that after
the first execution of 'for line in self.file:', the file pointer was
at EOF, not at 2, as one would expect.

Rewriting the __iter__ method to not internally iterate over the file
object, as follows, works - it now generates
a a
....
a z
b a
....
z z


class FileReIterable2(object):
def __init__(self, file):
self.file = open(file, 'rU')

def __iter__(self):
self.file.seek(0)
while True:
line = self.file.readline()
if line == '': raise StopIteration
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

 

[Scott David Daniels]

Hmm - I tried this with 'one.file' being ... letters, one per line:

gen = FileReIterable2("one.file")
for a in gen:
for b in gen:
print a.strip(), b.strip()

which didn't produce lines 'a a', 'a b', etc. It produced the single
line 'a a', then stopped....

Oops. This works in Python 2.5 (and later) because the file.tell and
file.seek code are aware of the file iteration buffering. Since I am
trying to test all of my stuff on 2.5, that is what I am using by
default.

Rewriting the __iter__ method to not internally iterate over the file
object, as follows, works ....

class FileReIterable2(object):
...
def __iter__(self):
self.file.seek(0)
while True:
line = self.file.readline()
if line == '': raise StopIteration
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

This fix does in fact provide working behavior for Pythons before 2.5.

--Scott David Daniels
(e-mail address removed)