c# - c# shuffle list determining percentage

Question

I am using a function to shuffle and return the passing list:

    public static List<E> ShuffleList<E>(List<E> inputList)
    {
        var randomList = new List<E>();

        var r = new Random();
        var randomIndex = 0;
        while (inputList.Count > 0)
        {
            randomIndex = r.Next(0, inputList.Count); 
            randomList.Add(inputList[randomIndex]);                 
            inputList.RemoveAt(randomIndex); 
        }

        return randomList;
    }

The challenge I face is to determine "how randomized" is the shuffled list after. How could I ensure that at least the 50% of the elements are not in their initial position?

Again, the goal is to shuffle the list and at least the 50% of the list elements to swap position.

Any help is welcome.

标签： c#list

Answer 1

I've done a little fix on your code to start with:

private static Random r = new Random();
public static List<E> ShuffleList<E>(List<E> inputList)
{
    var working = new List<E>(inputList);

    var randomList = new List<E>();

    var randomIndex = 0;
    while (working.Count > 0)
    {
        randomIndex = r.Next(0, working.Count);
        randomList.Add(working[randomIndex]);
        working.RemoveAt(randomIndex);
    }

    return randomList;
}

Now I can test it.

void Main()
{
    var size = 100;
    var loops = 1000000;
    var original = Enumerable.Range(0, size).ToList();
    var counter = 0;
    var collisions = 0;
    while (counter++ < loops)
    {
        var shuffled = ShuffleList(original);
        collisions += shuffled.Select((x, n) => x == n).Where(x => x).Count();
    }
    Console.WriteLine((double)collisions / counter / size);
}

That's displaying the average number of elements that are in the same position after the sorting. I'm getting results like 0.00998599001400999 or 0.01000271999728 running this code.

Your code successfully moves 99% of the numbers in a list of 100 to a new location.

Just to make your life easier you can also rewrite your code as:

private static Random r = new Random();

public static List<E> ShuffleList<E>(List<E> inputList)
    => inputList.OrderBy(x => r.Next()).ToList();