Как объединить 2 отсортированных списка в один перемешанный список при сохранении внутреннего порядка в c #

Question

Я хочу создать перетасованный объединенный список, который будет сохранять внутренний порядок списков.

Например:

список A: 11 22 33

список B:6 7 8

действительный результат: 11 22 * ​​1010 * 6 33 7 8

неверный результат: 22 11 7 6 33 8

Answer 1

Оригинальный ответ:

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;
        }
    }                
}

Второй ответ на основе ответа Marcog

    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;
            }
    }

Answer 2

Просто случайным образом выберите список (например, сгенерируйте случайное число от 0 до 1, если <0.5 списка A, в противном случае список B), а затем выберите элемент из этого списка и добавьте его в новый список.Повторяйте до тех пор, пока в каждом списке не останется элементов. </p>

Answer 3

Ни один из ответов, представленных на этой странице, не работает, если вам нужно, чтобы выходные данные были равномерно распределены.

Чтобы проиллюстрировать мои примеры, предположим, что мы объединяем два списка A=[1,2,3], B=[a,b,c]

В подходе, упомянутом в большинстве ответов (т. Е. Объединение двух списков по принципу слияния, но каждый раз случайный выбор заголовка списка), вывод [1 a 2 b 3 c] гораздо менее вероятен, чем [1 2 3 a b c]. Интуитивно понятно, что это происходит потому, что когда у вас заканчиваются элементы в списке, элементы в другом списке добавляются в конце. Из-за этого вероятность для первого случая составляет 0.5*0.5*0.5 = 0.5^3 = 0.125, но во втором случае больше случайных случайных событий, так как случайная голова должна выбираться 5 раз вместо 3, что оставляет нам вероятность 0.5^5 = 0.03125. Эмпирическая оценка также легко подтверждает эти результаты.

Ответ, предложенный @marcog, почти правильный. Однако существует проблема, когда распределение r не является равномерным после сортировки. Это происходит потому, что исходные списки [0,1,2], [2,1,0], [2,1,0] все сортируются в [0,1,2], что делает сортировку r более вероятной, чем, например, [0,0,0], для которой существует только один возможность.

Существует умный способ создания списка r таким образом, чтобы он был равномерно распределен, как видно из этого вопроса Math StackExchange: https://math.stackexchange.com/questions/3218854/randomly-generate-a-sorted-set-with-uniform-distribution

Чтобы подвести итог ответа на этот вопрос, вы должны попробовать | B | элементы (равномерно наугад и без повторений) из набора {0,1,..|A|+|B|-1}, сортируют результат и затем вычитают его индекс для каждого элемента в этом новом списке. В результате получается список r, который можно использовать вместо ответа @ marcog.

Answer 4

Генерирует A.Length случайные целые числа в интервале [0, B.Length).Сортируйте случайные числа, затем итерируйте i из 0..A.Length, добавляя A[i] в положение r[i]+i в B.+i - потому что вы смещаете исходные значения в B вправо, когда вставляете значения из A.

Это будет так же случайно, как и ваш ГСЧ.

Answer 5

Просто перебирайте оба списка одновременно, случайным образом выбирая, из какого списка выбрать элементы.Затем вставьте их в другой список.Вот один из способов сделать это:

static IEnumerable<T> Shuffle<T>(IEnumerable<T> listB, IEnumerable<T> listA)
{
    var rng = new Random();
    var lists = new[] { new Queue<T>(listA), new Queue<T>(listB) };
    while (lists.Any(l => l.Any()))
    {
        int i = rng.Next(2);
        var selected = lists[i];
        if (!lists[i].Any())
            selected = lists[1-i];
        yield return selected.Dequeue();
    }
}