Draw where the name cannot be drawn more than once

Question

I need to make a simple drawing software, but I don’t know how to take the names that were entered in the list box and draw one among them. The same name cannot be drawn more than once. How to do this part?

Answer 1

Implementation of the Fisher-Yates shuffle algorithm:

A simple way out of your case would be to produce a scrambled copy of the list of names, so you can go on removing the same one by one.

This can be done with a very short and efficient function:

   static Random _random = new Random();
   public static void Shuffle<T>(T[] array)
   {
      var random = _random;
      for (int i = array.Length; i > 1; i--)
      {
         int j = random.Next(i);
         T tmp = array[j];
         array[j] = array[i - 1];
         array[i - 1] = tmp;
      }
   }

Characteristics:

• Is of order O(n).

• If you need to draw the whole list, it ends up being more efficient than drawing individual items one by one and controlling what has already been drawn,

• This function is easily adaptable to other collections as well as arrays.

Complete code for testing:

using System;
public class Sorteio
{
   // Esta é a função de embaralhamento que você deve implementar no seu código:
   static Random _random = new Random();

   public static void Shuffle<T>(T[] array)
   {
      var random = _random;
      for (int i = array.Length; i > 1; i--)
      {
         int j = random.Next(i);
         T tmp = array[j];
         array[j] = array[i - 1];
         array[i - 1] = tmp;
      }
   }
   // Teste do algoritmo:
   public static void Main()
   {
      // Aqui você deve pegar os valores da sua lista:
      string[] array = { "Alaor", "Joseval", "Salustiano", "Gomide", "Castro" };
      // Embaralhamos a lista...
      Shuffle(array);
      // ... e, uma vez embaralhada a lista, não precisa sortear novamente.
      // basta ir pegando os resultados um por um, que os nomes não se repetirão:
      foreach (string value in array)
      {
         Console.WriteLine(value);
      }      
   }
}

See the result in IDEONE: http://ideone.com/aki905

_{Implementation adapted from http://www.dotnetperls.com/fisher-yates-shuffle}

Answer 2

I decided to put another answer since someone may need a shuffle without changing the original enumeration.

I took the opportunity to improve, after doing some tests, and saw that any enumeration can be used in this case.

I’ve removed the range of items that will be shuffled that have restricted utility. But I added an example to get a smaller amount of results after the shuffle. Of course a for simple or pick up individual elements manually. In this case you would have to manipulate the structure enumerator IEnumerable generated.

It may seem like a worse algorithm and in fact it’s a little slower than the algorithm that changes the data collection directly, but this new algorithm still has O(n complexity).

using static System.Console;
using System.Collections.Generic;
using System.Linq;

public static class Sorteio {
    public static void Main() {
        var lista = new List<string>() { "Alaor", "Joseval", "Salustiano", "Gomide", "Castro" };
        foreach (string value in lista.Shuffle()) {
            WriteLine(value);
        }
        WriteLine("////////");
        foreach (string value in lista.Shuffle().Take(3)) {
            WriteLine(value);
        }
    }
}

namespace System.Collections.Generic {
    public static class IEnumerableExt {
        static Random r = new Random(DateTime.Now.Millisecond);
        
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> list) {
            T[] array = list.ToArray();
            for (int i = array.Length - 1; i > 0; i--) {
                int j = r.Next(i + 1);
                T tmp = array[j];
                array[j] = array[i];
                array[i] = tmp;
            }
            foreach(var item in array) {
                yield return item;
            }
        }
    }
}

Behold working in the ideone. And in the .NET Fiddle. Also put on the Github for future reference.

Answer 3

I have an alternative to implementing Bacco with some advantages:

• Allows the use of any list, including a array which is a list. It may be more suitable for your specific use.
• Random generation uses a different seed from the pattern.
• Allows partial shuffling of the elements of the list (if never needed can be easily removed to decrease the code size).
• The method allows a more regular syntax and facilitating the Intellisense (is like the Shuffle was part of any declared list).

Maybe you need something that is just the middle between one solution and another. You may not need

You said nothing if the list can be changed in-place. If you can’t, you need one modified algorithm.

using static System.Console;
using System.Collections.Generic;

public static class Sorteio {
    public static void Main() {
        var lista = new List<string>() { "Alaor", "Joseval", "Salustiano", "Gomide", "Castro" };
        lista.Shuffle();
        foreach (var valor in lista) {
            WriteLine(valor);
        }
        WriteLine("//////////");
        string[] array = { "Alaor", "Joseval", "Salustiano", "Gomide", "Castro" };
        array.Shuffle(2);
        foreach (var valor in array) {
            WriteLine(valor);
        }
        WriteLine("//////////");
        int[] array2 = { 1, 2, 3, 4, 5 };
        array2.Shuffle(1,4);
        foreach (var valor in array2) {
            WriteLine(valor);
        }
    }
}

namespace System.Collections.Generic {
    public static class IListExt {
        static Random r = new Random(DateTime.Now.Millisecond);

        public static void Shuffle<T>(this IList<T> list, int lowerItem, int upperItem) {
            upperItem = upperItem > list.Count ? list.Count : upperItem;
            lowerItem = lowerItem < 0 ? 0 : lowerItem;
            for (int i = lowerItem; i < upperItem; i++) {
                int j = r.Next(i, upperItem);
                T tmp = list[j];
                list[j] = list[i];
                list[i] = tmp;
            }
        }

        public static void Shuffle<T>(this IList<T> list, int upperItem) {
            list.Shuffle(0, upperItem);
        }

        public static void Shuffle<T>(this IList<T> list) {
            list.Shuffle(0, list.Count);
        }
    }
}

Behold working in the ideone. And in the .NET Fiddle. Also put on the Github for future reference.

To leave the optional shuffle strip, simply delete the overloads, remove the additional parameters in the main method, the normalization lines of these parameters and use the value default directly.

If you need more security in generating random numbers. You have the option to use RNGCryptoServiceProvider but it already complicates a little more.

Answer 4

I’ve come to transcribe a more sophisticated algorithm to solve this problem. This algorithm has at least two advantages over Fisher-Yates:

• Do not change the original list (avoid a copy if preserving the original list is necessary)
• Makes fewer memory accesses (this may imply better performance, but I didn’t use any tool to measure performance so I’m not able to make comparisons)

Downside

• Does not change the original list (if it is necessary to go through the elements more than once it may be beneficial to use Fisher-Yates)
• It is more complicated to implement

This is an implementation of the algorithm described in this blog.

public static class Shuffler
{
    public static IEnumerable<int> Shuffle(this IList<int> items, int seed = 0)
    {
        int count = items.Count();
        int pow4 = 4;
        while (count > pow4)
        {
            pow4 *= 4;
        }

        int numBits = 0;
        int mask = pow4 - 1;
        while (mask != 0)
        {
            mask = mask >> 1;
            numBits++;
        }

        // calculate our left and right masks to split our indices for the feistel 
        // network
        int halfNumBits = numBits / 2;
        int rightMask = (1 << halfNumBits) - 1;
        int leftMask = rightMask << halfNumBits;

        for (int i = 0; i < pow4; ++i)
        {
            int shuffleIndex = EncryptIndex(i, halfNumBits, leftMask, rightMask, seed);

            // if we found a valid index, return success!
            if (shuffleIndex < count)
            {
                yield return items[shuffleIndex];
            }
        }
    }

    private static int MurmurHash2(int key, int seed)
    {
        // 'm' and 'r' are mixing constants generated offline.
        // They're not really 'magic', they just happen to work well.
        const int m = 0x5bd1e995;
        const int r = 24;

        // Initialize the hash to a 'random' value

        int h = seed ^ 4;

        // Mix 4 bytes at a time into the hash
        int k = key;

        k *= m; 
        k ^= k >> r; 
        k *= m; 

        h *= m; 
        h ^= k;

        // Do a few final mixes of the hash to ensure the last few
        // bytes are well-incorporated.

        h ^= h >> 13;
        h *= m;
        h ^= h >> 15;

        return h;
    }

    private static int EncryptIndex(int index, int halfNumBits, int leftMask, int rightMask, int seed)
    {

        int left = (index & leftMask) >> halfNumBits;
        int right = (index & rightMask);
        for (int i = 0; i < 4; ++i)
        {
            int newLeft = right;
            int newRight = left ^ (MurmurHash2(right, seed) & rightMask);
            left = newLeft;
            right = newRight;
        }

        // put the left and right back together to form the encrypted index
        return (left << halfNumBits) | right;
    }

}

Note: Call Shuffle with a seed different, or change the implementation to use a variable value such as Environment.TickCount