CODEWITHSUNDEEP
algorithmmathdistributionprobability
John
John

Reputation: 48

Random distribution between evenly sized buckets without repetition

Problem

I have N items of various types evenly distributed into their own buckets determined by type. I want to create a new list that:

  1. randomly picks from each bucket
  2. does not pick from the same bucket twice in a row
  3. each bucket must have (if possible) an equal amount of representation in the final list
  4. not using language specific libraries (not easily implemented in another language)

Example

I have 12 items of 4 distinct types which means I have 4 buckets:

Bucket A - [a, a, a]
Bucket B - [b, b, b]
Bucket C - [c, c, c]
Bucket D - [d, d, d]

What I want

A list of the above items in a random distribution without any characters repeating with a size between 1 and N.

12 Items: a, d, c, a, b, a, c, d, c, b, d, b

8 Items: c, a, d, a, b, d, c, b

4 Items: c, b, d, a

3 Items: b, c, a (Skipping D)

I was trying to do this with a while loop that generates random integers until the next bucket isn't equal to the previously used bucket, but that seems inefficient, and was hoping someone else might have a better algorithm to solve this problem.

Upvotes: 0

Views: 1688

Answers (2)

Hooked
Hooked

Reputation: 88228

Edited in response to the constraint that no draw must be consecutive from each bucket. It's simple to throw away permutations that don't meet your criteria. Now that this will fail (as is) if two buckets have identical "labels".

A little hack with itertools and random.sample for a permutation:

import random
import itertools as itr
from math import ceil

def buckets_choice(N,labels):
    items = int(ceil(float(N)/len(labels)))
    b = list(itr.chain(*(labels for _ in xrange(items))))

    while True:
        p = random.sample(b,len(b))
        cond = map( (lambda x,y: x==y), p[1:], p[:1])
        if not sum(cond):  return p[:N]

L = ['a','b','c','d']
for _ in xrange(5):
    print buckets_choice(3,L), buckets_choice(8,L), buckets_choice(12,L)

A sample run gives (quote marks removed for clarity):

(a, b, d) (b, d, c, a, d, a, b, c) (b, c, d, c, d, a, d, b, a, c, b, a)
(b, a, d) (d, a, c, c, a, b, b, d) (c, b, a, b, a, c, b, d, d, a, d, c)
(b, d, a) (b, c, c, a, b, a, d, d) (a, d, a, d, c, b, d, c, a, b, c, b)
(d, c, b) (c, d, a, b, c, b, a, d) (c, b, a, a, b, c, d, c, b, a, d, d)
(b, d, a) (c, b, b, d, c, a, d, a) (c, b, d, a, d, b, b, d, c, a, a, c)

Upvotes: 1

Choker
Choker

Reputation: 875

You could generate a random list of the buckets, and then randomly pick from then in order, removing the bucket from the list when you pick from it. When the list is empty, regenerate a random list of buckets, repeating until you pick the desired number of items.

Can you repeat items from the buckets? So if you pick the 1st "a" from bucket A the first time around, can you pick it a 2nd time? That'll change the solution.

Upvotes: 1

Related Questions