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