n log 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 shuffle，但我不确定如何使用分而治之.我的意思是，我实际上在分裂什么?我是否只是划分到列表中的每个单独节点，然后使用一些随机值将列表随机组合在一起?

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-nd 位置在自己的列表中，并且列表赢得了i-2次包括最后一次的抛硬币em>并且输了两次，这个概率是(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 choose 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.

附言我最初的直觉远非严格，但我将其列出以防万一.想象一下，我们将 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 log n 时间打乱链表的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！