How to combine N non-comparable arrays up to an output limit in a fair way?

Question

Given N non-comparable arrays of different sizes, what is the best method to combine them into one output array?

Since the input arrays are non-comparable, a metric is needed to represent how frequently the value on top of the array in question is appended to the output array. Lets call it weight and let it be an arbitrary value from 1 to 10.

Here is an example data set with weights:

numbers = [1, 2, 3, 4, 5]
numbers_weight = 3

books = ['The Lord of the Rings', 
         'The Hitchhikers Guide to the Galaxy', 
         'Enders Game',
         '1984']
books_weight = 5

words = ['polar', 'fiendish', 'percussive']
words_weight = 10

A naive solution would be generate a random number and then ask each array if it passes or fails based on its weight. If it passes, append it to the end of the output array. Then generate a new random number and begin again until some maximum limit is reached.

Here is the naive solution acting on the sample data:

def join_arrays(arrays, weights, weight_min, weight_max, output_limit):
    output = []
    while True:
        rnd = random.randint(weight_min, weight_max)
        for i in range(len(arrays)):
            if rnd <= weights[i] and len(arrays[i]) > 0:
                output.append(arrays[i].pop(0))
                if len(output) >= output_limit:
                    return output

And here is how the function is called, again using the sample data:

arrays = [numbers, books, words]
weights = [numbers_weight, books_weight, words_weight]

random.seed(time.time())
output = join_arrays(arrays, weights, 1, 10, 6)

The problem that I have with this type of round-robin style implementation is that if the size of arrays is vastly larger than output_limit, those towards the back of arrays will appear less frequently than their weight would suggest, or not at all, because there will be instances where they simply were not asked if they pass, and thus not appended to output.

Is there a solution to this problem that is allows for all input arrays inside of arrays to be asked if they pass or fail, thereby being fair, while still allowing for an output_limit?

Are the use of weights even appropriate for this type of combining?

Answer 1

It sounds like the thing you want to do is this:

1. Pick an array from the weighted list of non-empty arrays
2. Pop a value from that array and add it to the output array
3. Repeat some number of times

You seem to be having some trouble doing step 1 in a fair way. My suggestion is to flatten the weighted list into a list containing each array <array-weight> times, and choose fairly from that.

In the code below, I repeat each array <weight> times and add it to the overall list of arrays. Note that this approach creates a list of N references to the original arrays. That way, when you pop from any one of the references, you're doing it to the one object that backs all of them.

For safety, I also delete the list if the randomly chosen one was empty. This covers me in the edge case where the number of requested items is more than the total number of items in the input lists. In that case, I end up returning a semi-shuffled merger of all the items in the input arrays.

def join_arrays(arrays, weights, output_limit):
    data = []
    for array, weight in zip(arrays, weights):
        data.extend([array]*weight)
    output = []
    while data and len(output) < output_limit:
        value = random.choice(data)
        if value:
            output.append(value.pop())
        else:
            data.remove(value)
    return output