472,809 Members | 3,993 Online

# iterator? way of generating all possible combinations?

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

May 27 '06 #1
16 3467

ak*********@gmail.com wrote:
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/sea...ype=Subsection

http://tinyurl.com/frxqz

Raymond

May 27 '06 #2

<ak*********@gmail.com> wrote in message
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

May 27 '06 #3

Terry Reedy wrote:

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.

May 27 '06 #4
hmmm, just needed better search words, thanks :)

May 27 '06 #5

<ak*********@gmail.com> wrote in message

Terry Reedy wrote:

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.

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

May 27 '06 #6

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.

May 30 '06 #7
ak*********@gmail.com wrote:

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
May 30 '06 #8
ak*********@gmail.com wrote:
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
sc***********@acm.org
May 30 '06 #9
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?)

May 30 '06 #10

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

--Scott David Daniels
sc***********@acm.org

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.

May 30 '06 #11
ak*********@gmail.com wrote:
Scott David Daniels wrote:
This works with "iterables" (and produces), rather than "iterators",
which is vital to the operation.

--Scott David Daniels
sc***********@acm.org

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
sc***********@acm.org
May 30 '06 #12

Scott David Daniels wrote:
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
sc***********@acm.org

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

May 30 '06 #13
ak*********@gmail.com wrote:
Scott David Daniels wrote:
Sorry, "re-iterables". A file re-iterable is:

class FileReIterable(object): ...
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 __iter__(self):
self.file.seek(0)
for line in self.file:
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

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
sc***********@acm.org
May 30 '06 #14

Scott David Daniels wrote:
ak*********@gmail.com wrote:
Scott David Daniels wrote:
Sorry, "re-iterables". A file re-iterable is:

class FileReIterable(object): ...
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 __iter__(self):
self.file.seek(0)
for line in self.file:
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

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
sc***********@acm.org

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

May 31 '06 #15
In article <44********@nntp0.pdx.net>,
Scott David Daniels <sc***********@acm.org> wrote:

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:
if line == '': raise StopIteration
nextpos = self.file.tell()
yield line
self.file.seek(nextpos)

--
Jim Segrave (je*@jes-2.demon.nl)

May 31 '06 #16
Jim Segrave wrote:
In article <44********@nntp0.pdx.net>,
Scott David Daniels <sc***********@acm.org> wrote:
class FileReIterable2(object):
...
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 ... 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:
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
sc***********@acm.org
May 31 '06 #17

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 38 by: Grant Edwards | last post by: In an interview at http://acmqueue.com/modules.php?name=Content&pa=showpage&pid=273 Alan Kay said something I really liked, and I think it applies equally well to Python as well as the languages... 0 by: sks_cpp | last post by: I am trying to wrap the map iterator for keys and values. However, I seem to run into problems with the values for const_iterator - it works for all other combinations. Below I list my code and... 2 by: Lorenzo Castelli | last post by: This is an old problem of mine. Basically I have an abstract base class which represents a generic iterator over a collection of elements, and various derived classes that implement the... 8 by: Mir Nazim | last post by: Hello, I need to write scripts in which I need to generate all posible unique combinations of an integer list. Lists are a minimum 12 elements in size with very large number of possible... 1 by: mrajanikrishna | last post by: Hi friends, I am generating combinations from a set with different sub sets. Here is my code. For this example, actually I need to get 56 combinations but I am getting 35 only. Can anybody... 6 by: py_genetic | last post by: Hi, I'm looking to generate x alphabetic strings in a list size x. This is exactly the same output that the unix command "split" generates as default file name output when splitting large... 4 by: RSH | last post by: Okay my math skills aren't waht they used to be... With that being said what Im trying to do is create a matrix that given x number of columns, and y number of possible values i want to generate... 14 by: bjorklund.emil | last post by: Hello pythonistas. I'm a newbie to pretty much both programming and Python. I have a task that involves writing a test script for every possible combination of preference settings for a software... 13 by: Yosifov Pavel | last post by: Whats is the way to clone "independent" iterator? I can't use tee(), because I don't know how many "independent" iterators I need. copy and deepcopy doesn't work... --pavel 0 by: linyimin | last post by: Spring Startup Analyzer generates an interactive Spring application startup report that lets you understand what contributes to the application startup time and helps to optimize it. Support for... 0 by: erikbower65 | last post by: Here's a concise step-by-step guide for manually installing IntelliJ IDEA: 1. Download: Visit the official JetBrains website and download the IntelliJ IDEA Community or Ultimate edition based on... 0 by: kcodez | last post by: As a H5 game development enthusiast, I recently wrote a very interesting little game - Toy Claw ((http://claw.kjeek.com/))。Here I will summarize and share the development experience here, and hope it... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 6 Sept 2023 starting at 18:00 UK time (6PM UTC+1) and finishing at about 19:15 (7.15PM) The start time is equivalent to 19:00 (7PM) in Central... 14 by: DJRhino1175 | last post by: When I run this code I get an error, its Run-time error# 424 Object required...This is my first attempt at doing something like this. I test the entire code and it worked until I added this - If... 0 by: Rina0 | last post by: I am looking for a Python code to find the longest common subsequence of two strings. I found this blog post that describes the length of longest common subsequence problem and provides a solution in... 0 by: lllomh | last post by: How does React native implement an English player? 0 by: Mushico | last post by: How to calculate date of retirement from date of birth 2 by: DJRhino | last post by: Was curious if anyone else was having this same issue or not.... I was just Up/Down graded to windows 11 and now my access combo boxes are not acting right. With win 10 I could start typing...