# Draw where the name can not be drawn more than once

10

I need to make a simple draw software, but I do not know how to get the names that were inserted in the list box and draw one among them. The same name can not be drawn more than once. How to do this part?

asked by anonymous 31.05.2014 / 06:19

12

## Implementation of Fisher-Yates Scrambling Algorithm:

A simple way out for your case would be to produce a scrambled copy of the list of names, so you can remove them 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;
}
}
``````

Features:

• Is of order O (n).

• If you need to raffle the entire list, it's more efficient than raffling individual items one by one and controlling what has been sorted out,

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

## Complete test code:

``````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);
}
}
}
``````

31.05.2014 / 07:07
7

I have an alternative to implementing Bacco with some advantages:

• Enables the use of any list , including an array which is a list. It may be more suitable for your specific use.
• Random generation uses a seed other than the default.
• Allows partial shuffling of the elements of the list (if certainly never ) can be easily removed to decrease the size of the code.
• The method allows a more regular syntax and makes Intellisense (like `Shuffle` a part of any declared list).

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

You have not said anything if the list can be changed in-place . If you can not, you need a 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);
}
}
}
``````

In order to abandon the optional scrambling strip, simply delete the overloads , remove the additional parameters in the main method, the normalization lines of these parameters and use the default value directly .

If you need greater security in generating random numbers. You have the option to use `RNGCryptoServiceProvider` but it's already complicated a bit more.

31.05.2014 / 17:39
7

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

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

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

It may seem like a worse algorithm and in fact is a bit slower than the algorithm that alters the data collection directly, but this new algorithm continues to have complexity O (n).

``````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;
}
}
}
}
``````

31.05.2014 / 21:26
3

I came 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 you preserve the original list if necessary)
• It makes less access to memory (this may imply better performance, but I did not use any tool to measure performance so I am not able to make comparisons)

• 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's more complicated to implement
``````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;
{
numBits++;
}

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

for (int i = 0; i < pow4; ++i)
{

// 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 the Shuffle with a different% of%, or change the implementation to use a variable value such as `seed`

11.05.2016 / 16:28