Elements mixing algorithm

Question 1

I think the solution is pretty easy.

Start with an array x initialised to empty values such that there is one space for each item you need to place.

Then, for each (item, frequency) pair in descending order of frequency, assign item values to x in alternating slots starting from the first empty slot.

Here's how it works for your example:

20*A    A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A
10*B    ABABABABABABABABABABA_A_A_A_A_A_A_A_A_A
 5*C    ABABABABABABABABABABACACACACACA_A_A_A_A
 2*E    ABABABABABABABABABABACACACACACAEAEA_A_A
 1*F    ABABABABABABABABABABACACACACACAEAEAFA_A

At this point we fail, since x still has an empty slot. Note that we could have identified this right from the start since we need at least 19 slots between the As, but we only have 18 other items.

UPDATE

Leonidas has now explained that the items should be distributed "evenly" (that is, if we have k items of a particular kind, and n slots to fill, each "bucket" of n/k slots must contain one item of that kind.

We can adapt to this constraint by spreading out our allocations rather than simply going for alternating slots. In this case (and let's assume 2 Fs so we can solve this), we would have

20*A    A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A_A
10*B    ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA_ABA
 5*C    ABACABA_ABACABA_ABACABA_ABACABA_ABACABA
 2*E    ABACABAEABACABA_ABACABAEABACABA_ABACABA
 2*F    ABACABAEABACABAFABACABAEABACABAFABACABA

Question 2

You can solve this problem recursively:

def generate(lastChar, remDict):
    res = []
    for i in remDict:
        if i!=lastChar):
            newRemDict = remDict
            newRemDict[i]-=1
            subres = generate(i,newRemDict)
            res += [i+j for j in subres]
    return res

Note that I am leaving out corner conditions and many checks that need to be done. But only the core recursion is shown. You can also quit pursuing a branch if more than half+1 of the remaining letters is a same letter.

Question 3

I ran into a similar problem, and after evaluating various metrics, I came up with the idea of grabbing the first item for which the proportion through the source array is less than the proportion through the result array. There is a case where all of these values may come out as 1, for instance when halfway through merging a group of even arrays - everything's exactly half done - so I grab something from the first array in that case.

This solution does use the source array order, which is something that I wanted. If the calling routine wants to merge arrays A, B, and C, where A has 3 elements but B and C have 2, we should get A,B,C,A,B,C,A, not A,C,B,A,C,B,A or other possibilities. I find that choosing the first of my source arrays that's "overdue" (by having a proportion that's lower than our overall progress), I get a nice spacing with all arrays.

Source in Python: @classmethod def intersperse_arrays(cls, arrays: list): # general idea here is to produce a result with as even a balance as possible between all the arrays as we go down.

    # Make sure we don't have any component arrays of length 0 to worry about.
    arrays = [array for array in arrays if len(array) > 0]

    # Handle basic cases:
    if len(arrays) == 0:
        return []
    if len(arrays) == 1:
        return arrays[0]

    ret = []
    num_used = []
    total_count = 0
    for j in range(0, len(arrays)):
        num_used.append(0)
        total_count += len(arrays[j])

    while len(ret) < total_count:
        first_overdue_array = None
        first_remaining_array = None
        overall_prop = len(ret) / total_count

        for j in range(0, len(arrays)):
            # Continue if this array is already done.
            if len(arrays[j]) <= num_used[j]:
                continue
            current_prop = num_used[j] / len(arrays[j])
            if current_prop < overall_prop:
                first_overdue_array = j
                break
            elif first_remaining_array is None:
                first_remaining_array = j

        if first_overdue_array is not None:
            next_array = first_overdue_array
        else:
            # Think this only happens in an exact tie.  (Halfway through all arrays, for example.)
            next_array = first_remaining_array

        if next_array is None:
            log.error('Internal error in intersperse_arrays')
            break   # Shouldn't happen - hasn't been seen.

        ret.append(arrays[next_array][num_used[next_array]])
        num_used[next_array] += 1

    return ret

When used on the example given, I got:

ABCADABAEABACABDAFABACABADABACDABAEABACABAD

(Seems reasonable.)