How to merge 2 sorted listed into one shuffled list while keeping internal order in c#

I want to generate a shuffled merged list that will keep the internal order of the lists.

For exam开发者_StackOverflow中文版ple:

list A: 11 22 33

list B: 6 7 8

valid result: 11 22 6 33 7 8

invalid result: 22 11 7 6 33 8

Just randomly select a list (e.g. generate a random number between 0 and 1, if < 0.5 list A, otherwise list B) and then take the element from that list and add it to you new list. Repeat until you have no elements left in each list.

Generate A.Length random integers in the interval [0, B.Length). Sort the random numbers, then iterate i from 0..A.Length adding A[i] to into position r[i]+i in B. The +i is because you're shifting the original values in B to the right as you insert values from A.

This will be as random as your RNG.

None of the answers provided in this page work if you need the outputs to be uniformly distributed.

To illustrate my examples, assume we are merging two lists A=[1,2,3], B=[a,b,c]

In the approach mentioned in most answers (i.e. merging two lists a la mergesort, but choosing a list head randomly each time), the output [1 a 2 b 3 c] is far less likely than [1 2 3 a b c]. Intuitively, this happens because when you run out of elements in a list, then the elements on the other list are appended at the end. Because of that, the probability for the first case is 0.5*0.5*0.5 = 0.5^3 = 0.125, but in the second case, there are more random random events, since a random head has to be picked 5 times instead of just 3, leaving us with a probability of 0.5^5 = 0.03125. An empirical evaluation also easily validates these results.

The answer suggested by @marcog is almost correct. However, there is an issue where the distribution of r is not uniform after sorting it. This happens because original lists [0,1,2], [2,1,0], [2,1,0] all get sorted into [0,1,2], making this sorted r more likely than, for example, [0,0,0] for which there is only one possibility.

There is a clever way of generating the list r in such a way that it is uniformly distributed, as seen in this Math StackExchange question: https://math.stackexchange.com/questions/3218854/randomly-generate-a-sorted-set-with-uniform-distribution

To summarize the answer to that question, you must sample |B| elements (uniformly at random, and without repetition) from the set {0,1,..|A|+|B|-1}, sort the result and then subtract its index to each element in this new list. The result is the list r that can be used in replacement at @marcog's answer.

Original Answer:

static IEnumerable<T> MergeShuffle<T>(IEnumerable<T> lista, IEnumerable<T> listb)
{
    var first = lista.GetEnumerator();
    var second = listb.GetEnumerator();

    var rand = new Random();
    bool exhaustedA = false;
    bool exhaustedB = false;
    while (!(exhaustedA && exhaustedB))
    {
        bool found = false;
        if (!exhaustedB && (exhaustedA || rand.Next(0, 2) == 0))
        {
             exhaustedB = !(found = second.MoveNext());
            if (found)
                yield return second.Current;
        }
        if (!found && !exhaustedA)
        {
            exhaustedA = !(found = first.MoveNext());
            if (found)
                yield return first.Current;
        }
    }                
}

Second answer based on marcog's answer

    static IEnumerable<T> MergeShuffle<T>(IEnumerable<T> lista, IEnumerable<T> listb)
    {
        int total = lista.Count() + listb.Count();
        var random = new Random();
        var indexes = Enumerable.Range(0, total-1)
                                .OrderBy(_=>random.NextDouble())
                                .Take(lista.Count())
                                .OrderBy(x=>x)
                                .ToList();

        var first = lista.GetEnumerator();
        var second = listb.GetEnumerator();

        for (int i = 0; i < total; i++)
            if (indexes.Contains(i))
            {
                first.MoveNext();
                yield return first.Current;
            }
            else
            {
                second.MoveNext();
                yield return second.Current;
            }
    }

Rather than generating a list of indices, this can be done by adjusting the probabilities based on the number of elements left in each list. On each iteration, A will have A_size elements remaining, and B will have B_size elements remaining. Choose a random number R from 1..(A_size + B_size). If R <= A_size, then use an element from A as the next element in the output. Otherwise use an element from B.

int A[] = {11, 22, 33}, A_pos = 0, A_remaining = 3;
int B[] = {6, 7, 8}, B_pos = 0, B_remaining = 3;

while (A_remaining || B_remaining) {
  int r = rand() % (A_remaining + B_remaining);

  if (r < A_remaining) {
    printf("%d ", A[A_pos++]);
    A_remaining--;
  } else {
    printf("%d ", B[B_pos++]);
    B_remaining--;
  }
}

printf("\n");

As a list gets smaller, the probability an element gets chosen from it will decrease.

This can be scaled to multiple lists. For example, given lists A, B, and C with sizes A_size, B_size, and C_size, choose R in 1..(A_size+B_size+C_size). If R <= A_size, use an element from A. Otherwise, if R <= A_size+B_size use an element from B. Otherwise C.

Here is a solution that ensures a uniformly distributed output, and is easy to reason why. The idea is first to generate a list of tokens, where each token represent an element of a specific list, but not a specific element. For example for two lists having 3 elements each, we generate this list of tokens: 0, 0, 0, 1, 1, 1. Then we shuffle the tokens. Finally we yield an element for each token, selecting the next element from the corresponding original list.

public static IEnumerable<T> MergeShufflePreservingOrder<T>(
    params IEnumerable<T>[] sources)
{
    var random = new Random();
    var queues = sources
        .Select(source => new Queue<T>(source))
        .ToArray();
    var tokens = queues
        .SelectMany((queue, i) => Enumerable.Repeat(i, queue.Count))
        .ToArray();
    Shuffle(tokens);
    return tokens.Select(token => queues[token].Dequeue());

    void Shuffle(int[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            int j = random.Next(i, array.Length);
            if (i == j) continue;
            if (array[i] == array[j]) continue;
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    }
}

Usage example:

var list1 = "ABCDEFGHIJKL".ToCharArray();
var list2 = "abcd".ToCharArray();
var list3 = "@".ToCharArray();
var merged = MergeShufflePreservingOrder(list1, list2, list3);
Console.WriteLine(String.Join("", merged));

Output:

ABCDaEFGHIb@cJKLd

This might be easier, assuming you have a list of three values in order that match 3 values in another table. You can also sequence with the identity using identity (1,2)

Create TABLE #tmp1 (ID int identity(1,1),firstvalue char(2),secondvalue char(2))
Create TABLE #tmp2 (ID int identity(1,1),firstvalue char(2),secondvalue char(2))

Insert into #tmp1(firstvalue,secondvalue) Select firstvalue,null secondvalue from firsttable

Insert into #tmp2(firstvalue,secondvalue) Select null firstvalue,secondvalue from secondtable

Select a.firstvalue,b.secondvalue from #tmp1 a join #tmp2 b on a.id=b.id

DROP TABLE #tmp1
DROP TABLE #tmp2