在n log n时间内混合链表的算法

Question

我正在尝试使用分而治之算法来混合链表,该算法随后在线性(n log n)时间和对数(log n)额外空间中随机混洗链表.

我知道我可以做一个类似于可以在一个简单的数组中使用的Knuth shuffle,但是我不知道如何用分而治之的方式做到这一点.我的意思是,我实际上分裂了什么？我只是划分到列表中的每个单独节点,然后使用一些随机值将列表随机组合在一起？

或者我给每个节点一个随机数,然后根据随机数在节点上进行合并？

Answer 1

以下怎么样？执行与合并排序相同的过程.合并时,不是从排序顺序的两个列表中选择一个元素(逐个),而是翻转硬币.根据硬币翻转的结果选择是从第一个列表还是从第二个列表中选择元素.

算法.

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元素.

虚拟节点的要点是认识到插入和移除虚设元素使得元素的分布保持均匀.

分析. 为什么分布均匀？在最终合并之后,P_i(n)任何给定数字在该位置结束的概率i如下.它是:

• 在i它自己的列表中的第一个位置,并且列表第一次赢得硬币投掷i,这是概率1/2^i;
• 在i-1它自己的列表中的-st位置,并且列表赢得了包括最后一个并丢失一次的硬币折腾i-1时间,这是时间的概率;(i-1) choose 11/2^i
• 在i-2它自己的列表中的位置,并且列表赢得了包括最后一个和丢失两次的硬币折腾i-2时间,这是次的概率;(i-1) choose 21/2^i
• 等等.

所以概率

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-bit二进制数的数量,即2^{i-1}.所以我们得到了

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是偶数,并且两个列表均匀地进行了混洗.这是通过添加(然后删除)虚拟节点来实现的.

PS我原来的直觉远没有严格,但我列举以防万一.想象一下,我们将1和n之间的数字随机分配给列表的元素.现在我们对这些数字进行合并排序.在合并的任何给定步骤中,它需要确定两个列表中的哪个头部较小.但是一个大于另一个的概率应该恰好是1/2,所以我们可以通过掷硬币来模拟这个.

PPS有没有办法在这里嵌入LaTeX？

Answer 2

码

向上洗牌方法

从foxcub的答案中改进了此（lua）版本，以消除对虚拟节点的需要。

为了稍微简化此答案中的代码，此版本假定您的列表知道其大小。如果没有，您总是可以及时找到它O(n)，但更好的是：可以对代码进行一些简单的修改，而无需事先计算（例如，一分为二而不是第一和第二半） 。

function listUpShuffle (l)
    local lsz = #l
    if lsz <= 1 then return l end

    local lsz2 = math.floor(lsz/2)
    local l1, l2 = {}, {}
    for k = 1, lsz2     do l1[#l1+1] = l[k] end
    for k = lsz2+1, lsz do l2[#l2+1] = l[k] end

    l1 = listUpShuffle(l1)
    l2 = listUpShuffle(l2)

    local res = {}
    local i, j = 1, 1
    while i <= #l1 or j <= #l2 do
        local rem1, rem2 = #l1-i+1, #l2-j+1
        if math.random() < rem1/(rem1+rem2) then
            res[#res+1] = l1[i]
            i = i+1
        else
            res[#res+1] = l2[j]
            j = j+1
        end
    end
    return res
end

为了避免使用虚拟节点，您必须通过改变每个列表中选择的概率来补偿两个中间列表可以具有不同长度的事实。通过针对从第一个列表弹出的节点与弹出的节点总数（在两个列表中）的比率测试[0,1]统一随机数，可以完成此操作。

向下洗牌方法

在递归细分时，您也可以随机播放，在我的卑鄙测试中，这显示了稍好（但始终如一）的性能。它可能来自较少的指令，或者另一方面，它可能是由于luajit中的缓存预热而出现的，因此您必须针对用例进行分析。

function listDownShuffle (l)
    local lsz = #l
    if lsz <= 1 then return l end

    local lsz2 = math.floor(lsz/2)
    local l1, l2 = {}, {}
    for i = 1, lsz do
        local rem1, rem2 = lsz2-#l1, lsz-lsz2-#l2
        if math.random() < rem1/(rem1+rem2) then
            l1[#l1+1] = l[i]
        else
            l2[#l2+1] = l[i]
        end
    end

    l1 = listDownShuffle(l1)
    l2 = listDownShuffle(l2)

    local res = {}
    for i = 1, #l1 do res[#res+1] = l1[i] end
    for i = 1, #l2 do res[#res+1] = l2[i] end
    return res
end

测验

完整的源代码在我的列表Shuffle.lua Gist中。

它包含的代码在执行后将打印一个矩阵，该矩阵表示输入列表的每个元素在指定的运行次数后出现在输出列表的每个位置的次数。一个相当均匀的矩阵可以“显示”字符分布的均匀性，因此可以显示随机播放的均匀性。

这是一个使用（3的幂）3个元素列表进行1000000次迭代的示例：

>> luajit listShuffle.lua 1000000 3
Up shuffle bias matrix:
333331 332782 333887
333377 333655 332968
333292 333563 333145
Down shuffle bias matrix:
333120 333521 333359
333435 333088 333477
333445 333391 333164

Answer 3

你实际上可以做得比这更好：最好的列表洗牌算法是O(n log n) 时间和O(1) 空间。（您还可以通过为列表构造一个指针数组，在O(n) 时间和O(n) 空间中混洗，使用 Knuth 将其混洗到位并相应地重新线程化列表。）

复杂性证明

要了解为什么 O(n log n) 时间对于 O(1) 空间最小，请观察：

• 对于 O(1) 空间，更新任意列表元素的后继元素必然需要 O(n) 时间。
• Wlog，你可以假设每当你更新一个元素时，你也会更新所有其他元素（如果你愿意，可以保持它们不变），因为这也只需要 O(n) 时间。
• 对于 O(1) 空间，最多有 O(1) 个元素可供您更新的任何元素的后继元素选择（这些特定元素显然取决于算法）。
• 因此，所有元素的单个 O(n) 时间更新可能导致最多 c^n 个不同的列表排列。
• 既然有 n! = O(n^n) = O(c^(n log n)) 可能的列表排列，您至少需要 O(log n) 次更新。

链表数据结构（因为 Python）

import collections

class Cons(collections.Sequence):
    def __init__(self, head, tail=None):
        self.head = head
        self.tail = tail

    def __getitem__(self, index):
        current, n = self, index
        while n > 0:
            if isinstance(current, Cons):
                current, n = current.tail, n - 1
            else:
                raise ValueError("Out of bounds index [{0}]".format(index))
        return current

    def __len__(self):
        current, length = self, 0
        while isinstance(current, Cons):
            current, length = current.tail, length + 1
        return length

    def __repr__(self):
        current, rep = self, []
        while isinstance(current, Cons):
            rep.extend((str(current.head), "::"))
            current = current.tail
        rep.append(str(current))
        return "".join(rep)

合并式算法

这是一个基于迭代归并排序的 O(n log n) 时间和 O(1) 空间算法。基本思想很简单：先打乱左半部分，然后打乱右半部分，然后通过从两个列表中随机选择来合并它们。有两点值得注意：

1. 通过使算法迭代而不是递归，并在每个合并步骤结束时返回一个指向新的最后一个元素的指针，我们将空间需求减少到 O(1)，同时保持最小的时间成本。
2. 为确保所有输入大小的所有可能性都相等，我们在合并时使用来自 Gilbert–Shannon–Reeds 模型 riffle shuffle 的概率（参见http://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon %E2%80%93Reeds_model）。

import random

def riffle_lists(head, list1, len1, list2, len2):
    """Riffle shuffle two sublists in place. Returns the new last element."""
    for _ in range(len1 + len2):
        if random.random() < (len1 / (len1 + len2)):
            next, list1, len1 = list1, list1.tail, len1 - 1
        else:
            next, list2, len2 = list2, list2.tail, len2 - 1
        head.tail, head = next, next
    head.tail = list2
    return head

def shuffle_list(list):
    """Shuffle a list in place using an iterative merge-style algorithm."""
    dummy = Cons(None, list)
    i, n = 1, len(list)
    while (i < n):
        head, nleft = dummy, n
        while (nleft > i):
            head = riffle_lists(head, head[1], i, head[i + 1], min(i, nleft - i))
            nleft -= 2 * i
        i *= 2
    return dummy[1]

另一种算法

另一个有趣的 O(n log n) 算法会产生不完全均匀的洗牌，它涉及简单地对列表进行 3/2 log_2(n) 次洗牌。如http://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model 中所述，这仅留下恒定数量的信息位。

Answer 4

我会说，foxcub的回答是错误的。为了证明我将为完美混排的列表引入有用的定义（将其称为数组或序列或任何您想要的名称）。

定义：假设我们有一个L包含元素a1, a2 ... an和索引的列表1, 2, 3..... n。如果仅当通过了解某些k（）元素的索引我们无法推断剩余元素的索引时，如果将暴露L给shuffle操作（内部没有访问权限）就L被完美地改组。也就是说，其余元素同样有可能在其余任何索引处显示。k< nn-kn-kn-k

示例：如果我们有一个包含四个元素的列表，[a, b, c, d]并且经过改组，我们知道它的第一个元素为a（[a, .., .., ..]），而不是任何元素b, c, d出现在其中的概率，比方说，第三个单元格等于1/3。

现在，算法无法满足其定义的最小列表包含三个元素。但是该算法还是将其转换为4元素列表，因此我们将尝试显示4元素列表的不正确性。

考虑一个输入L = [a, b, c, d]在算法的第一次运行之后，L将被分为l1 = [a, c]和l2 = [b, d]。在将这两个子列表混排之后（但在合并为四元素结果之前），我们可以获得四个等概率的2元素列表：

l1shuffled = [a , c]     l2shuffled = [b , d]
l1shuffled = [a , c]     l2shuffled = [d , b]
l1shuffled = [c , a]     l2shuffled = [b , d]
l1shuffled = [c , a]     l2shuffled = [d , b]

现在尝试回答两个问题。
1.合并到最终结果中之后成为a列表第一元素的概率是多少。
简而言之，我们可以看到上面的四对中的两对（再次，同样可能）可以给出这样的结果（p1 = 1/2）。对于这些对中的每对，都heads必须在合并例程（p2 = 1/2）中的第一次翻转期间绘制。因此，对于具有的概率a为一体的第一个元素Lshuffled是p = p1*p2 = 1/4，这是正确的。

2.知道a处于的第一个位置时LshuffledcbdLshuffled
，根据上述完全改组列表的定义，在 Now 的第二个位置上拥有（我们可以选择或不失一般性）的概率是多少？答案应该是1/3，因为在列表中剩余的三个单元格中要放入三个数字，
让我们看看算法是否可以保证这一点。
在选择1作为的第一个元素之后，Lshuffled我们现在将具有：
l1shuffled = [c] l2shuffled = [b, d]
或： 两种情况下
l1shuffled = [c] l2shuffled = [d, b]
的选择概率3等于翻转heads（p3 = 1/2）的概率，因此具有3作为的第二个元素的概率Lshuffled，知道何时该第一元件元件Lshuffled是1平等1/2。1/2 != 1/3这样就证明了算法的不正确性。

有趣的是，该算法满足了完美混洗的必要（但不充分）条件，即：

给定一个n元素列表，对于每个索引k（<n），对于每个元素ak：在对列表m次数进行改组之后，如果我们已经ak对出现在k索引上的时间进行了计数，则该计数将趋于m/n概率，m趋于无穷大。