2

我想生成一个混洗合并列表，以保持列表的内部顺序。

例如：

列表 A：11 22 33

清单 B：6 7 8

有效结果：11 22 6 33 7 8

无效结果：22 11 7 6 33 8

4

7 回答 7

2

只需随机选择一个列表（例如，生成 0 和 1 之间的随机数，如果 < 0.5 列表 A，否则列表 B），然后从该列表中取出元素并将其添加到新列表中。重复，直到每个列表中都没有元素。

于 2011-01-02T09:56:12.867 回答
2

在区间 [0, )中生成A.Length随机整数。B.Length对随机数进行排序，然后i从0..A.Length添加A[i]到中的位置r[i]+i进行迭代B。这+i是因为您在B插入值时将原始值向右移动A.

这将与您的 RNG 一样随机。

于 2011-01-02T10:02:33.660 回答
2

如果您需要均匀分布输出，则此页面中提供的答案均无效。

为了说明我的示例，假设我们正在合并两个列表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 -均匀分布

为了总结这个问题的答案，你必须抽样 |B| set 中的元素（均匀随机且不重复）{0,1,..|A|+|B|-1}，对结果进行排序，然后将其索引减去此新列表中的每个元素。结果是r可以在@marcog 的答案中用于替换的列表。

于 2019-05-08T21:07:35.077 回答
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;
            }
    }
于 2011-01-02T09:58:41.243 回答
0

这可以通过根据每个列表中剩余的元素数量调整概率来完成，而不是生成索引列表。在每次迭代中，A 将剩余 A_size 个元素，B 将剩余 B_size 个元素。从 1..(A_size + B_size) 中选择一个随机数 R。如果 R <= A_size，则使用 A 中的一个元素作为输出中的下一个元素。否则使用 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");

随着列表变小，从中选择元素的概率会降低。

这可以扩展到多个列表。例如，给定大小为 A_size、B_size 和 C_size 的列表 A、B 和 C，请在 1..(A_size+B_size+C_size) 中选择 R。如果 R <= A_size，使用 A 中的元素。否则，如果 R <= A_size+B_size 使用 B 中的元素。否则 C。

于 2019-09-14T01:14:39.107 回答
0

这是一个确保输出均匀分布的解决方案，并且很容易推理。这个想法是首先生成一个标记列表，其中每个标记表示特定列表的一个元素，而不是特定元素。例如，对于两个具有 3 个元素的列表，我们生成这个标记列表：0、0、0、1、1、1。然后我们打乱标记。最后，我们为每个标记产生一个元素，从相应的原始列表中选择下一个元素。

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

使用示例：

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

输出：

ABCDaEFGHIb@cJKLd

于 2019-09-14T02:17:58.310 回答
0

这可能更容易，假设您有一个包含三个值的列表，以便匹配另一个表中的 3 个值。您还可以使用身份 (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
于 2021-12-02T15:57:15.897 回答