All geek questions in one place

How to shuffle or randomize a linked list

I'm trying to shuffle or randomize LinkedList images in this case, but the way I set it up, it seems to continue indefinitely

shuffling is pretty simple, you have a list, pay attention to the last entry, then take the first entry and put it in a random place on the list, and then the next first entry, etc. until the top entry becomes the entry that you marked as last, you put this entry in a random place on the list, and the list is shuffled.

here is my code:

class ShuffleClass
{
    private LinkedList<Image> library;
    private Image lastCard;
    private Image topCard;
    private Random rng;
    private int place;
    private LinkedListNode<Image> node;

    public LinkedList<Image> shuffle(LinkedList<Image> library)
    {
        this.library = library;
        lastCard = library.Last.Value;
        rng = new Random();

        while (library.First.Value != lastCard)
        {
            topCard = library.First.Value;
            library.RemoveFirst();
            place = rng.Next(1,library.Count+1);

            if (place == library.Count)
            {
                library.AddBefore(library.Last, topCard);
            }
            else
            { 
                node = library.Find(library.ElementAt(place));
                library.AddBefore(node, topCard);
            }

        }
        topCard = library.First.Value;
        library.RemoveFirst();
        place = rng.Next(0,library.Count+1);
        if(place == library.Count)
        {
            library.AddBefore(library.Last, topCard);
        }
        else
        {
            node = library.Find(library.ElementAt(place));
            library.AddBefore(node, topCard);
        }
        return library;
    }
}
+4
source share
2 answers

You can use a random class to shuffle the list:

public static void Shuffle()
{
    Random Rand = new Random();
    LinkedList<int> list = new LinkedList<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20 });

    foreach (int i in list)
        Console.Write("{0} ", i);

    Console.WriteLine();
    int size = list.Count;

    //Shuffle the list
    list =  new LinkedList<int>(list.OrderBy((o) =>
    {
        return (Rand.Next() % size);
    }));

    foreach (int i in list)
        Console.Write("{0} ", i);

    Console.WriteLine();
}

The output could be something like this:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
10 2 17 7 9 15 8 14 1 12 13 16 4 18 3 5 11 20 19 6
+1

, , , , , . AddBefore(), , , , .

, , , , .

, , , Fisher-Yates, swap , ( Fisher-Yates).

, , , , , ( ).

, , . :

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> test = new LinkedList<int>(Enumerable.Range(0, 10)),
            shuffled = Shuffle(test);

        Console.WriteLine(string.Join(", ", shuffled));
    }

    static LinkedList<T> Shuffle<T>(LinkedList<T> source)
    {
        LinkedList<T> result = new LinkedList<T>();
        int[] choices = Enumerable.Range(0, source.Count).ToArray();

        ShuffleArray(choices);
        foreach (int choice in choices)
        {
            result.AddLast(ElementAt(source, choice));
        }

        return result;
    }

    static void ShuffleArray<T>(T[] array)
    {
        // Naturally, in real code you'd want to reuse the same Random object
        // across multiple calls, by making it static readonly
        Random random = new Random();

        for (int i = array.Length; i > 1; i--)
        {
            int j = random.Next(i);

            if (i - 1 != j)
            {
                T t = array[i - 1];

                array[i - 1] = array[j];
                array[j] = t;
            }
        }
    }

    static T ElementAt<T>(LinkedList<T> source, int index)
    {
        LinkedListNode<T> current = source.First;

        while (index-- > 0)
        {
            current = current.Next;
        }

        return current.Value;
    }
}

/ , - :

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> test = new LinkedList<int>(Enumerable.Range(0, 10));

        ShuffleLinkedList(test);
        Console.WriteLine(string.Join(", ", test));
    }

    static void ShuffleLinkedList<T>(LinkedList<T> list)
    {
        // Naturally, in real code you'd want to reuse the same Random object
        // across multiple calls, by making it static readonly
        Random random = new Random();

        for (int i = list.Count; i > 1; i--)
        {
            SwapNodes(list, i - 1, random.Next(i));
        }
    }

    static void SwapNodes<T>(LinkedList<T> list, int i, int j)
    {
        if (i != j)
        {
            LinkedListNode<T> node1 = NodeAt(list, i), node2 = NodeAt(list, j),
                nodeBefore1 = node1.Previous, nodeBefore2 = node2.Previous;

            if (nodeBefore1 == node2)
            {
                list.Remove(node1);
                AddAfter(list, nodeBefore2, node1);
            }
            else if (nodeBefore2 == node1)
            {
                list.Remove(node2);
                AddAfter(list, nodeBefore1, node2);
            }
            else
            {
                list.Remove(node1);
                list.Remove(node2);
                AddAfter(list, nodeBefore2, node1);
                AddAfter(list, nodeBefore1, node2);
            }
        }
    }

    static void AddAfter<T>(LinkedList<T> list, LinkedListNode<T> after, LinkedListNode<T> add)
    {
        if (after != null)
        {
            list.AddAfter(after, add);
        }
        else
        {
            list.AddFirst(add);
        }
    }

    static LinkedListNode<T> NodeAt<T>(LinkedList<T> source, int index)
    {
        LinkedListNode<T> current = source.First;

        while (index-- > 0)
        {
            current = current.Next;
        }

        return current;
    }
}

, . , , , .

, , . , , , , , . , , .

:

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> test = new LinkedList<int>(Enumerable.Range(0, 10));

        ShuffleLinkedList(test);
        Console.WriteLine(string.Join(", ", test));
    }

    static void ShuffleLinkedList<T>(LinkedList<T> list)
    {
        // Naturally, in real code you'd want to reuse the same Random object
        // across multiple calls, by making it static readonly
        Random random = new Random();

        for (int i = list.Count; i > 1; i--)
        {
            LinkedListNode<T> node = NodeAt(list, random.Next(i));

            if (list.Last != node)
            {
                list.Remove(node);
                list.AddLast(node);
            }
        }
    }

    static LinkedListNode<T> NodeAt<T>(LinkedList<T> source, int index)
    {
        LinkedListNode<T> current = source.First;

        while (index-- > 0)
        {
            current = current.Next;
        }

        return current;
    }
}

node.

, (O (n) O (n ^ 2)) , , :

class Program
{
    static void Main(string[] args)
    {
        LinkedList<int> test = new LinkedList<int>(Enumerable.Range(0, 10));

        Shuffle(test);
        Console.WriteLine(string.Join(", ", test));
    }

    static void Shuffle<T>(LinkedList<T> source)
    {
        T[] choices = new T[source.Count];

        for (int i = 0; i < choices.Length; i++)
        {
            choices[i] = source.First.Value;
            source.RemoveFirst();
        }

        ShuffleArray(choices);

        foreach (T choice in choices)
        {
            source.AddLast(choice);
        }
    }

    static void ShuffleArray<T>(T[] array)
    {
        // Naturally, in real code you'd want to reuse the same Random object
        // across multiple calls, by making it static readonly
        Random random = new Random();

        for (int i = array.Length; i > 1; i--)
        {
            int j = random.Next(i);

            if (i - 1 != j)
            {
                T t = array[i - 1];

                array[i - 1] = array[j];
                array[j] = t;
            }
        }
    }
}
+1

Source: https://habr.com/ru/post/1653401/

More articles:


All Articles