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,s ides):
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]

ak*********@gma il.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

[Terry Reedy]

<ak*********@gm ail.com> wrote in message
news:11******** **************@ i40g2000cwc.goo glegroups.com.. .

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]

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.

[akameswaran]

hmmm, just needed better search words, thanks :)

[Terry Reedy]

<ak*********@gm ail.com> wrote in message
news:11******** **************@ j73g2000cwa.goo glegroups.com.. .

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

[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]

ak*********@gma il.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

[Scott David Daniels]

ak*********@gma il.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***********@a cm.org

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