随机排列链接列表

Question

我有一个带有随机方法的自定义LinkedList类。对我来说，它看起来是正确的，但结果似乎并没有真正洗牌。

public class LinkedList<T>
{
    public class Node<T>
    {
        public T data;
        public Node<T> next;
    }
    private Node<T> _lastNode;
    private Node<T> _headNode;
    private int _count;
} 

例：

输入：1,2,3,4,5,6,7,8

输出 1：2,1,8,6,7,4,5,3

输出 2：2,1,8,7,5,6,4,3

输出 3：2,1,7,8,6,5,3,4

我知道Random使用日期时间，所以我在不同的结果之间等待几秒钟。我想洗牌方法有思维错误吗？

随机播放方法：

public void Shuffle()
{
    if (_headNode != null)
    {
        Random Rand = new Random();
        Node<T> nLast = _lastNode;          
        Node<T> nFirst = _headNode;
        foreach (Node<T> item in Nodes)
        {
            T dTemp = item.data;
            if (Rand.Next(0, 2) == 0)
            {
                item.data = nLast.data;
                nLast.data = dTemp;
            }
            else
            {
                item.data = nFirst.data;
                nFirst.data = dTemp;
            }
        }
    }
}

基本上我遍历 LinkedList 并将当前值与第一个/最后一个节点的值交换

问题：我的方法有错误吗？或者甚至有没有其他算法更适合对LinkedList进行排序？

Answer 1

看起来费

舍尔-耶茨洗牌的"由内而外"版本可以根据您的情况进行调整。

public void Shuffle(Random random = null)
{
    if (_count < 2) return;
    if (random == null) random = new Random();
    var result = new Node[_count];
    int i = 0;
    for (var node = _headNode; node != null; node = node.next)
    {
        int j = random.Next(i + 1);
        if (i != j)
            result[i] = result[j];
        result[j] = node;
        i++;
    }
    _headNode = _lastNode = result[0];
    for (i = 1; i < result.Length; i++)
        _lastNode = _lastNode.next = result[i];
    _lastNode.next = null;
}

第一次遍历填充随机节点数组，然后第二遍更新链接，最终得到 O（N） 时间和空间复杂性。

测试：

using System;
using System.Collections.Generic;
using System.Linq;
namespace Tests
{
    class Program
    {
        static void Main(string[] args)
        {
            var list = new LinkedList<int>();
            for (int n = 1; n <= 8; n++)
                list.Add(n);
            Action<string> dump = info => Console.WriteLine("{0,-10}({1})", info, string.Join(",", list.Nodes.Select(n => n.data.ToString())));
            dump("Input");
            var random = new Random();
            for (int i = 1; i <= 10; i++)
            {
                list.Shuffle(random);
                dump("Output " + i);
            }
            Console.ReadLine();
        }
    }
    public class LinkedList<T>
    {
        public class Node
        {
            public T data;
            public Node next;
        }
        private Node _lastNode;
        private Node _headNode;
        private int _count;
        public void Add(T data)
        {
            var node = new Node { data = data };
            if (_lastNode != null) _lastNode.next = node; else _headNode = node;
            _lastNode = node;
            _count++;
        }
        public IEnumerable<Node> Nodes { get { for (var node = _headNode; node != null; node = node.next) yield return node; } }
        public void Shuffle(Random random = null)
        {
            if (_count < 2) return;
            if (random == null) random = new Random();
            var result = new Node[_count];
            int i = 0;
            for (var node = _headNode; node != null; node = node.next)
            {
                int j = random.Next(i + 1);
                if (i != j)
                    result[i] = result[j];
                result[j] = node;
                i++;
            }
            _headNode = _lastNode = result[0];
            for (i = 1; i < result.Length; i++)
                _lastNode = _lastNode.next = result[i];
            _lastNode.next = null;
        }
    }
}

结果：

Input     (1,2,3,4,5,6,7,8)
Output 1  (6,4,8,5,7,2,3,1)
Output 2  (4,1,2,6,3,8,7,5)
Output 3  (6,7,8,2,1,5,4,3)
Output 4  (7,1,6,5,8,4,3,2)
Output 5  (1,7,6,4,8,5,3,2)
Output 6  (6,7,1,4,5,2,3,8)
Output 7  (1,7,6,8,5,2,4,3)
Output 8  (3,8,5,7,6,4,2,1)
Output 9  (5,2,3,6,7,4,1,8)
Output 10 (3,7,4,6,8,2,1,5)

Answer 2

问题是你的洗牌算法不是特别擅长洗牌。如果我理解正确，您将查看每个元素，然后将其与第一个或最后一个元素交换。主要问题是，这只剩下少数可能的结束状态。从数学上讲，它只为列表中的每个项目提供两个选项或2^n可能性。这甚至不包括任何潜在的重复结果，这将进一步减少选项的数量，但我不想弄清楚有多少这样的结果。随机集的总可能选项为 n! 。

在你的例子中，你有 10 个项目，所以你的算法给出了2 ^ 10 = 1024可能的结果，而总共有 10! = 3628800 种实际可能性。如果你实现一个更好的算法，你会看到更多样化的结果。例如，这里有一个可能更好的算法。

在 1 和 n 之间选择一个随机数，从起始列表中删除该元素并将其添加为随机列表中的第一个元素，然后用 1 到 n-1 之间的数字重复此过程（因为起始列表现在小了一个元素）。这样做，直到您用完起始列表中的元素。这给出了洗牌列表的所有可能结果，并且结果完全不依赖于起始列表的顺序。如果内存是一个问题，还有一种方法可以做到这一点，如果你愿意，我可以编写伪代码向你展示它是如何工作的。

附言如果有人发现我的计算有问题，请告诉我，我会解决它

编辑：我刚刚意识到您是在LinkedList而不是List上执行此操作，但我相信可以应用相同的算法，或者您可以在进行随机播放之前将LinkedList转换为List