25

我正在尝试使用分治算法对链表进行洗牌，该算法在线性（n log n）时间和对数（log n）额外空间中随机洗牌链表。

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

还是我给每个节点一个随机数，然后根据随机数对节点进行合并排序？

4

7 回答 7

36

下面的呢？执行与归并排序相同的过程。合并时，不是按排序顺序从两个列表中选择一个元素（一个接一个），而是掷硬币。根据掷硬币的结果，选择是从第一个列表还是从第二个列表中选择一个元素。

编辑（2022-01-12）：正如 GA1 在下面的答案中指出的那样，该算法不会随机均匀地产生排列。

算法。

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 个元素。

虚拟节点的要点是实现插入和删除虚拟元素保持元素分布均匀。

编辑（2022-01-12）：正如莱利在评论中指出的那样，下面的分析是有缺陷的。

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

  • 在i自己的列表中排在第-th位，并且该列表第一次掷硬币获胜i，这个概率是1/2^i；
  • 在自己的列表中的-st位置，并且该列表赢得了包括最后一个在内的i-1掷硬币i-1次数和输一次，这个概率是次数；(i-1) choose 11/2^i
  • 在自己的列表中排在第-nd位，并且该列表赢得了包括最后一个在内的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位二进制数的数量，即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？

于 2012-08-28T22:03:43.433 回答
7

代码

上洗牌方法

这个（lua）版本是从 foxcub 的回答中改进的，以消除对虚拟节点的需要。

为了稍微简化此答案中的代码，此版本假设您的列表知道它们的大小。如果他们不这样做，你总是可以及时找到它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

测试

完整的源代码在我的 listShuffle.lua Gist中。

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

这是一个使用（非 2 的幂）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
于 2014-03-05T18:56:30.057 回答
7

我会说，那个狐狸的答案是错误的。为了证明我将为一个完美的混洗列表引入一个有用的定义（称它为数组或序列或任何你想要的）。

定义：假设我们有一个 ListL包含元素a1, a2 ... an和索引1, 2, 3..... n。如果我们将 暴露L给一个 shuffle 操作（我们无法访问其内部结构）L当且仅当通过知道一些 k ( k< n) 元素的索引我们不能推断出剩余n-k元素的索引时，它才会被完美地洗牌。也就是说，其余n-k元素同样有可能在任何剩余n-k索引处显示。

示例：如果我们有一个四元素列表[a, b, c, d]，并且在对其进行洗牌后，我们知道它的第一个元素是a( )，而不是任何元素出现在[a, .., .., ..]的概率，比如说，第三个单元格等于。b, c, d1/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概率是，这是正确的。aLshuffledp = 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等于。这结束了算法不正确性的证明。11/21/2 != 1/3

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

给定一个n元素列表，对于每个索引k( <n)，对于每个元素ak：在对列表时间进行洗牌之后m，如果我们计算ak了索引上出现的次数k，这个计数将趋向于m/n概率，m趋向于无穷大。

于 2015-02-27T12:31:09.830 回答
5

你实际上可以做得更好：最好的列表洗牌算法是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中所述，这仅留下恒定数量的信息。

于 2014-12-23T16:18:29.510 回答
1

这是一种可能的解决方案：

#include <stdlib.h>

typedef struct node_s {
   struct node_s * next;
   int data;
} node_s, *node_p;

void shuffle_helper( node_p first, node_p last ) {
   static const int half = RAND_MAX / 2;
   while( (first != last) && (first->next != last) ) {
      node_p firsts[2] = {0, 0};
      node_p *lasts[2] = {0, 0};
      int counts[2] = {0, 0}, lesser;
      while( first != last ) {
         int choice = (rand() <= half);
         node_p next = first->next;
         first->next = firsts[choice];
         if( !lasts[choice] ) lasts[choice] = &(first->next);
         ++counts[choice];
         first = next;
      }

      lesser = (counts[0] < counts[1]);

      if( !counts[lesser] ) {
         first = firsts[!lesser];
         *(lasts[!lesser]) = last;
         continue;
      }

      *(lasts[0]) = firsts[1];
      *(lasts[1]) = last;

      shuffle_helper( firsts[lesser], firsts[!lesser] );

      first = firsts[!lesser];
      last = *(lasts[!lesser]);
   }
}

void shuffle_list( node_p thelist ) { shuffle_helper( thelist, NULL ); }

这基本上是快速排序，但没有枢轴，并且具有随机分区。

外部while循环替换了递归调用。

内部while循环将每个元素随机移动到两个子列表之一中。

在内while循环之后，我们将子列表相互连接起来。

然后，我们在较小的子列表上递归，并在较大的子列表上循环。

由于较小的子列表永远不会超过初始列表大小的一半，因此最坏情况下的递归深度是元素数量的以二为底的对数。所需的内存量是递归深度的 O(1) 倍。

平均运行时间和调用次数rand()为 O(N log N)。

更精确的运行时分析需要理解“几乎肯定”这个短语。

于 2016-10-26T01:26:10.800 回答
0

自下而上的合并排序没有比较。合并时不做任何比较只是交换元素。

于 2016-09-07T05:13:40.523 回答
0

您可以遍历列表，在每个节点随机生成 0 或 1。

如果为 1，则删除该节点并将其作为列表的第一个节点。如果为 0，则什么也不做。

循环这个直到你到达列表的末尾。

于 2020-05-25T04:05:59.977 回答