number distribution without repeatable numbers

Question

we have a problem in which we need to order/distribute the given set/s such that the numbers are not repeatable

here is an example ,say i have 4 sets

{A,A,A,A,A,A}
   {B,B}
   {C}
   {D,D,D}

the resultant should be something like A,D,A,B,A,D,C,A,D,A,B,A with no repeatable occurrence.

any thoughts,Algorithms..could be appreciated.

EDIT : sorry for not being clear, by occurrence I meant patterns like AA or BB or CC shouldn't in the resultant it's OK to have ADAD

Thanks Dee

Answer 1

A moment's consideration yielded this algorithm:

Let A be the symbol repeated the most times.
Let N be the number of occurrences of A.
Let Rest be the concatenation of the remaining symbols, in order.
Let Buckets be a list of length N, where each element Buckets[i] is an array containing a single A.

Iterate over Buckets: for each index i, pop an element from Rest and append it to Buckets[i]. When you reach the end of Buckets, start from the first index again. When you reach the end of Rest, you are done.

The answer is the concatenation of the contents of Buckets.

Your example:

Let A = 'A'.
Let N = 6.
Let Rest = [B, B, C, D, D, D].
Let Buckets = [[A], [A], [A], [A], [A], [A]].

After iterating, Buckets is [[A, B], [A, B], [A, C], [A, D], [A, D], [A, D]]. The output is ABABACADADAD.

Answer 2

Always pick the bucket with the most amount left.

My rusty Matlab skills did this:

generate a random distribution:

symbols = ceil(rand()*10)+1 maxn = ceil(rand()*20) distribution= [floor(rand(1,symbols)*maxn);(1:symbols)]'

last = -1;
sequence=[];   #output vector
while sum(distribution(:,1))>0 ;   #while something is left
    distribution= sortrows(distribution);   #sort the matrix
    if last == distribution(end,2) #pick the one with the one with the second most elements
        if a(end-1,1) ==0  #this means there are no fillers left
            break
        end
        last = distribution(end-1,2);
        distribution(end-1,1)--;
    else #pick the one with the most elements
        last = distribution(end,2);
        distribution(end,1) --;
    endif
    sequence(end+1)=last;
end
sequence
rest = distribution'

Note: My symbols are numbers instead of letters.

Edit: Here is some (beautified) output from the script.