Randomly break up array into chunks of at least 3 with even distribution

Question

I have an array of size n, and would like to break it up into m chunks of size at least 3. For example, given the array

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

and m=3, we could break the it up into

a=[1,2,3,4][5,6,7][8,9,10]
b=[1,2,3][4,5,6,7][8,9,10]
c=[1,2,3][4,5,6][7,8,9,10]

We could think of these solutions as being represented by the pairs (4,3,3) (3,4,3) and (3,3,4). I would like a function that given an array, n, and m, returns a random solution AND returns these solutions with an even distribution (so that you are no more likely to get one particular solution than any other). (This function needs to work for n=50, so for performance reasons we cannot do this by calculating all possible solutions.)

So, in the case above, this method would return [4,3,3] a third of the time, [3,4,3] a third of the time, and [3,3,4] a third of the time.

What have you tried? You need to show some effort, and then we can help you fix any bugs you can't figure out. — forgivenson, Dec 23 '14 at 20:34
The return values in the case above would be [4,3,3], [3,4,3], and [3,3,4]. (It will always return a list of m integers that sum to n). — Jared Stewart, Dec 23 '14 at 20:40
To see what I have running currently, check out the rand_breaks_array() method of https://github.com/jaredjstewart/MultipleDepotVehicleRoutingProblem/blob/master/src/main/groovy/org/jaredstewart/MultipleTSPSolver.groovy I ported this code from a MATLAB script I found, and haven't been able to discern how this method works. Seems to me there ought to be a simpler way! — Jared Stewart, Dec 23 '14 at 20:40
So, the method linked above *works*, I just have a nagging suspicion that there exists an elegant solution to this problem which I have not yet discovered. — Jared Stewart, Dec 23 '14 at 20:52
If you want help reviewing working code, then you should ask this question on http://codereview.stackexchange.com/. — forgivenson, Dec 23 '14 at 20:55
I wasn't sure that codereview was the appropriate place for this post, because I am more interested in completely novel algorithms for this problem than in reworkings of the existing code. — Jared Stewart, Dec 23 '14 at 20:57
Regardless of where it's posted, you should include the code within the question rather than linking to a repo. — Reinstate Monica Please, Dec 24 '14 at 05:22

kha · Answer 1 · 2014-12-23T21:07:08.633

Just a thought:

Let's say m=3, n=20. What we can do is to do this:

Choose a number between m and n - 2*m (between 3 and 14)
Let's say we random 6. This will be the first set and let's call it p1
Choose a number between our new subset of [m, [n - m - p1]] i.e. the subset of [3, 20 - 6 - 3] or [3, 11]
Let's say we roll 10. This is p2
Size of the remainder (or p3) will be 20 -p1 -p2 = 4

Final set will be [6, 10, 4]

Would this work? It wouldn't need any sort of iteration over the original list either. Your only iteration will be over m and not dependent on n.

I can try to make this more generic for variable m (step 1will need to change slightly and steps 3 and 5 will be in a loop) but I'm sure you can work it out if this solution is acceptable to you. Example rewrite for step 1 would be:

Choose a number between m and n - [m - 1] * m

score 0 · Answer 2 · answered Dec 24 '14 at 00:57

Would this work?

def randomCollate(item, chunk) {
    def collated = item.collate( chunk )
    def remainder = collated.reverse().takeWhile { it.size() != chunk }.flatten()
    def randomIdx = new Random().nextInt( ( collated - remainder ).size() )
    collated[randomIdx] += remainder
    collated - [ remainder ]
}

randomCollate( 1..50, 3 )

score 0 · Answer 3 · answered Dec 24 '14 at 01:36

Another idea I just had

Calculate how many array you are going to have with size m and how many with size m+1 (or a different sice). Let's call these values x and y.
Calculate the amount of possible permutations [3,3,4],[3,4,3],[4,3,3] -> 3 permutations (x+y)Py (binomial coefficient)
Chose a random permutation from 0 - possible permutations. Lets call this Z.
From now on I don't exactly know how this could be done, but I would try this:
Imagine you got a binary number with n digits and y of those are zeros. Get the Zst possible binary number with exactly y zeros and x ones.
Example binary: 100101101
Your result would be [x,y,y,x,y,x,x,y,x]

I hope you understand what I mean.

score 0 · Answer 4 · answered Dec 24 '14 at 14:48

for each step allow a random range of n-m*min (min is 3 in your example); then pick a number from that range, add min, as r. if m is 2 return a list of r and n-r. otherwise return r and the result of the recursive call with n-r, m-1. shuffle this and you have the random sizes of the chunks.

rnd = new Random()

// build the chunk size list to randomly split `n` elements in `m` parts, 
// where each part is at least of size `min`
// needs a shuffle afterwards
def s(n,m,min=3) {
    def l = n-m*min // the range where we can pick a random offset
    def r = min + (l?rnd.nextInt(l):0) // result for this step with optional random part
    m==2 ? [r,n-r] : [r]+s(n-r,m-1) // only two remaining? pick result and remainder, or recurse
}

def tests = [[9,3,3],[10,3,3],[27,9,3],[4,2,2]]
1000.times{
    tests.each{ n,m,min ->
        def r = s(n,m,min) 
        assert r.sum()==n
        assert r.size()==m
        assert r.every{ it>= min }
    }
}

def items = (0..9).collect() // test list
def slices = s(items.size(),3) // get the chunk sizes
Collections.shuffle(slices) // shuffle the result
// create ranges and use them to get the slices; should be another one or two methods
println slices.inject([sum:0,result:[]]) { r,s -> r.result<<items[((r.sum)..(r.sum+s-1))]; r.sum+=s; r }.result
//=> e.g. [[0, 1, 2, 3], [4, 5, 6], [7, 8, 9]]

Randomly break up array into chunks of at least 3 with even distribution

4 Answers4