loop until all elements have been accessed N times in python

Question

I have a group of buckets, each with a certain number of items in them. I want to make combinations with one item from each bucket. The loop should keep making different combinations until each item has participated in at least some defined number.

I can easily see how to run the loop and stop once a single element has been accessed a certain number of times. However I can't see how to set a minimum cutoff point beyond searching through all the elements in all the buckets to check their access number after every iteration of the loop.

Answer 1

itertools.product is one way (a very systematic one) to make the "combinations" you request (don't confuse with the .combinations function of course) -- or you could make them randomly with random.choose from each bucket; not sure which one is for you since I don't know what your real purpose is.

Anyway, I'd keep track of how many combos each item has been in with a dict (or one dict per bucket, if there can be overlap in items among buckets). Or, you could use a collections.Counter in Python 2.7, if that's your version.

At any rate, one possibility to do what you request is: the moment an item's count reaches N, remove that item from its bucket (or all buckets, if there's overlap and that's the semantics you require) -- except that if this leaves the bucket empty, restore the bucket's contents and mark that bucked as "done" (you don't need to remove items from a done bucket) e.g. by adding the bucket's index to a set.

You're done when all buckets are done (whether it be randomly or systematically).

Need some code to explain this better? Then please specify the overlap semantics (if overlap is possible) and the systematic-or-random requirements you have.

Answer 2

try

visits = defaultdict(int)

# do at each node visiting
    visits[n] += 1
    if visits[n] >= MAX_VISITS:
        break

print 'done'

Answer 3

Use a dictionary with the items as keys. Every time the item is used, update its count. Then check to see whether all the values are at least above the threshold, ie:

counter = dict()
while min(counter.values) < threshold:
   # make a combination
   # and update the dictionary

Answer 4

In vanilla Python, this seems to do the job:

buckets = [ [1,2,3],[4],[5,6],[7,8,9,0] ]

def combo(b, i = 0, pref = []):
  if len(b) > i:
    c = b[i]
    for v in c:
      combo(b, i + 1, pref + [v])
  else:
    print pref

combo(buckets)

Output:

[1, 4, 5, 7]
[1, 4, 5, 8]
[1, 4, 5, 9]
[1, 4, 5, 0]
[1, 4, 6, 7]
[1, 4, 6, 8]
[1, 4, 6, 9]
[1, 4, 6, 0]
[2, 4, 5, 7]
[2, 4, 5, 8]
[2, 4, 5, 9]
[2, 4, 5, 0]
[2, 4, 6, 7]
[2, 4, 6, 8]
[2, 4, 6, 9]
[2, 4, 6, 0]
[3, 4, 5, 7]
[3, 4, 5, 8]
[3, 4, 5, 9]
[3, 4, 5, 0]
[3, 4, 6, 7]
[3, 4, 6, 8]
[3, 4, 6, 9]
[3, 4, 6, 0]

There is no doubt a more Pythonic way of doing it.