n次登录n次混洗链表的算法 [英] Algorithm for Shuffling a Linked List in n log n time

问题描述

我正在尝试使用分治法将随机列表在线性时间（n log n）时间和对数（log n）额外空间中随机排序的分治算法来洗改链表。

I'm trying to shuffle a linked list using a divide-and-conquer algorithm that randomly shuffles a linked list in linearithmic (n log n) time and logarithmic (log n) extra space.

我知道我可以进行类似于在简单值数组中使用的Knuth改组，但是我不确定如何使用分治法来实现。我的意思是，我实际上是在划分什么？我是只划分列表中的每个节点，然后使用某个随机值将列表随机组合在一起？

I'm aware that I can do a Knuth shuffle similar to that could be used in a simple array of values, but I'm not sure how I would do this with divide-and-conquer. What I mean is, what am I actually dividing? Do I just divide to each individual node in the list and then randomly assemble the list back together using some random value?

还是我给每个节点一个随机数，然后

Or do I give each node a random number and then do a mergesort on the nodes based on the random numbers?

推荐答案

该怎么办？执行与合并排序相同的过程。合并时，不要从两个列表中按排序的顺序选择元素（一个一个），而是掷硬币。根据硬币翻转的结果选择从第一个列表中选择元素还是从第二个列表中选择元素。

What about the following? Perform the same procedure as merge sort. When merging, instead of selecting an element (one-by-one) from the two lists in sorted order, flip a coin. Choose whether to pick an element from the first or from the second list based on the result of the coin flip.

算法。

shuffle(list):
    if list contains a single element
        return list

    list1,list2 = [],[]
    while list not empty:
        move front element from list to list1
        if list not empty: move front element from list to list2

    shuffle(list1)
    shuffle(list2)

    if length(list2) < length(list1):
        i = pick a number uniformly at random in [0..length(list2)]             
        insert a dummy node into list2 at location i 

    # merge
    while list1 and list2 are not empty:
        if coin flip is Heads:
            move front element from list1 to list
        else:
            move front element from list2 to list

    if list1 not empty: append list1 to list
    if list2 not empty: append list2 to list

    remove the dummy node from list

空间的关键是将列表分为两部分不需要任何额外的空间。我们唯一需要的额外空间是在递归过程中在堆栈上维护log n个元素。

The key point for space is that splitting the list into two does not require any extra space. The only extra space we need is to maintain log n elements on the stack during recursion.

虚拟节点的要点是要意识到插入和删除虚拟元素可以使元素的分布保持一致。

The point with the dummy node is to realize that inserting and removing a dummy element keeps the distribution of the elements uniform.

分析。
为什么分布均匀？最终合并之后，任何给定数字出现在位置 i 中的概率 P_i（n）如下。要么是：

Analysis. Why is the distribution uniform? After the final merge, the probability P_i(n) of any given number ending up in the position i is as follows. Either it was:

• 在其自身列表的第 i 位中，并且列表赢得了硬币，这是第一次 i 次，其概率为 1/2 ^ i ;
在自己列表中的 i-1 -st位置上的

• ，列表赢得了抛硬币 i -1 乘以，包括最后一个，一次输了，这的概率是（i-1）选择1 次 1/2 ^ i ;


• 在 i-2 -在自己的列表中排名第二，该列表赢得了抛硬币 i-2 次（包括最后一个），并输了两次，这种可能性是（i-1）选择2 乘以 1/2 ^ i ;


• 依此类推。

• in the i-th place in its own list, and the list won the coin toss the first i times, the probability of this is 1/2^i;
• in the i-1-st place in its own list, and the list won the coin toss i-1 times including the last one and lost once, the probability of this is (i-1) choose 1 times 1/2^i;
• in the i-2-nd place in its own list, and the list won the coin toss i-2 times including the last one and lost twice, the probability of this is (i-1) choose 2 times 1/2^i;
• and so on.

所以概率

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2).

归纳地，您可以显示 P_i（n）= 1 / n 。我让您验证基本情况，并假设 P_j（n / 2）= 2 / n 。项 \sum_ {j = 0} ^ {i-1}（i-1选择j）恰好是 i-1的数量位二进制数字，即 2 ^ {i-1} 。因此我们得到

Inductively, you can show that P_i(n) = 1/n. I let you verify the base case and assume that P_j(n/2) = 2/n. The term \sum_{j=0}^{i-1} (i-1 choose j) is exactly the number of i-1-bit binary numbers, i.e. 2^{i-1}. So we get

P_i(n) = \sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n
       = 2/n * 1/2^i * \sum_{j=0}^{i-1} (i-1 choose j)
       = 1/n * 1/2^{i-1} * 2^{i-1}
       = 1/n

我希望这是有道理的。我们唯一需要的假设是 n 是偶数，并且两个列表被统一地改组。通过添加（然后删除）虚拟节点来实现。

I hope this makes sense. The only assumption we need is that n is even, and that the two lists are shuffled uniformly. This is achieved by adding (and then removing) the dummy node.

P.S。我最初的直觉远未达到严格的要求，但为防万一。想象一下，我们将1到n之间的数字随机分配给列表的元素。现在，我们针对这些数字进行合并排序。在合并的任何给定步骤中，它都需要确定两个列表中哪个头较小。但是一个比另一个大的概率应该恰好是1/2，因此我们可以通过掷硬币来模拟。

P.S. My original intuition was nowhere near rigorous, but I list it just in case. Imagine we assign numbers between 1 and n at random to the elements of the list. And now we run a merge sort with respect to these numbers. At any given step of the merge, it needs to decide which of the heads of the two lists is smaller. But the probability of one being greater than the other should be exactly 1/2, so we can simulate this by flipping a coin.

P.P.S。有没有办法在这里嵌入LaTeX？

P.P.S. Is there a way to embed LaTeX here?

这篇关于n次登录n次混洗链表的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！