desordenar - La forma más eficiente de "ordenar" aleatoriamente(aleatorio) una lista de enteros en C#

shuffle list c# unity

Question

Necesito ordenar aleatoriamente una lista de enteros (0-1999) de la manera más eficiente posible. ¿Algunas ideas?

Actualmente, estoy haciendo algo como esto:

bool[] bIndexSet = new bool[iItemCount];

for (int iCurIndex = 0; iCurIndex < iItemCount; iCurIndex++)
{
    int iSwapIndex = random.Next(iItemCount);
    if (!bIndexSet[iSwapIndex] && iSwapIndex != iCurIndex)
    {
        int iTemp = values[iSwapIndex];
        values[iSwapIndex] = values[iCurIndex];
        values[iCurIndex] = values[iSwapIndex];
        bIndexSet[iCurIndex] = true;
        bIndexSet[iSwapIndex] = true;
    }
}

Answer 1

¿No funcionaría algo como esto?

var list = new[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
var random = new Random();
list.Sort((a,b)=>random.Next(-1,1));

Answer 2

Como Greg señaló que la mezcla de Fisher-Yates sería el mejor enfoque. Aquí hay una implementación del algoritmo de Wikipedia:

public static void shuffle (int[] array)
{
   Random rng = new Random();   // i.e., java.util.Random.
   int n = array.length;        // The number of items left to shuffle (loop invariant).
   while (n > 1)
   {
      int k = rng.nextInt(n);  // 0 <= k < n.
      n--;                     // n is now the last pertinent index;
      int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
      array[n] = array[k];
      array[k] = temp;
   }
}

La implementación anterior se basa en Random.nextInt (int) proporcionando resultados suficientemente aleatorios e imparciales

Answer 3

Hice un método usando un Hashtable temporal, permitiendo que el tipo de clave natural del Hashtable se aleatorice. Simplemente agrega, lee y descarta.

int min = 1;
int max = 100;
Random random;
Hashtable hash = new Hashtable();
for (int x = min; x <= max; x++)
{
    random = new Random(DateTime.Now.Millisecond + x);
    hash.Add(random.Next(Int32.MinValue, Int32.MaxValue), x);
}
foreach (int key in hash.Keys)
{
    HttpContext.Current.Response.Write("<br/>" + hash[key] + "::" + key);
}
hash.Clear(); // cleanup

Answer 4

La respuesta de ICR es muy rápida, pero las matrices resultantes no se distribuyen normalmente. Si quieres una distribución normal, aquí está el código:

    public static IEnumerable<T> RandomPermutation<T>(this IEnumerable<T> sequence, int start,int end)
    {
        T[] array = sequence as T[] ?? sequence.ToArray();

        var result = new T[array.Length];

        for (int i = 0; i < start; i++)
        {
            result[i] = array[i];
        }
        for (int i = end; i < array.Length; i++)
        {
            result[i] = array[i];
        }

        var sortArray=new List<KeyValuePair<double,T>>(array.Length-start-(array.Length-end));
        lock (random)
        {
            for (int i = start; i < end; i++)
            {
                sortArray.Add(new KeyValuePair<double, T>(random.NextDouble(), array[i]));
            }
        }

        sortArray.Sort((i,j)=>i.Key.CompareTo(j.Key));

        for (int i = start; i < end; i++)
        {
            result[i] = sortArray[i - start].Value;
        }

        return result;
    }

Tenga en cuenta que en mis pruebas, este algoritmo fue 6 veces más lento que el ICR proporcionado, sin embargo, esta es la única forma en que podría llegar para obtener una distribución de resultados normal

Answer 5

No estoy seguro del factor de eficiencia, pero he utilizado algo similar a lo siguiente, si no se opone al uso de un ArrayList:

private ArrayList ShuffleArrayList(ArrayList source)
{
    ArrayList sortedList = new ArrayList();
    Random generator = new Random();

    while (source.Count > 0)
    {
        int position = generator.Next(source.Count);
        sortedList.Add(source[position]);
        source.RemoveAt(position);
    }

    return sortedList;
}

Al usar esto, no tiene que preocuparse por el intercambio intermedio.

Answer 6

Para mejorar su eficiencia, puede mantener un conjunto de valores / índices que se han intercambiado en lugar de un booleano para indicar que se intercambiaron. Elija su índice de intercambio aleatorizado del grupo restante. Cuando el grupo es 0, o cuando pasaste a través de la lista inicial, entonces has terminado. No tiene el potencial de intentar seleccionar un valor de índice de intercambio aleatorio.

Cuando hagas un intercambio, simplemente quítalos de la piscina.

Para el tamaño de los datos que está viendo, no es gran cosa.

Answer 7

Podemos hacer un método de extensión de esto para obtener un enumerador aleatorio para cualquier colección IList

class Program
{
    static void Main(string[] args)
    {
        IList<int> l = new List<int>();
        l.Add(7);
        l.Add(11);
        l.Add(13);
        l.Add(17);

        foreach (var i in l.AsRandom())
            Console.WriteLine(i);

        Console.ReadLine();
    }
}


public static class MyExtensions
{
    public static IEnumerable<T> AsRandom<T>(this IList<T> list)
    {
        int[] indexes = Enumerable.Range(0, list.Count).ToArray();
        Random generator = new Random();

        for (int i = 0; i < list.Count; ++i )
        {
            int position = generator.Next(i, list.Count);

            yield return list[indexes[position]];

            indexes[position] = indexes[i];
        }
    }
}   

Esto usa una mezcla aleatoria de Fisher-Yates en los índices de la lista que queremos enumerar al azar. Es un poco de un tamaño de cerdo (asignando 4 * list.Count bytes), pero se ejecuta en O (n).

Answer 8

Supongo que las últimas dos líneas deben intercambiarse en la respuesta de Micah. Entonces, el código puede parecerse

 public static void shuffle(int[] array) {
        Random rng = new Random();   // i.e., java.util.Random.
        int n = array.Length;        // The number of items left to shuffle (loop invariant).
        while (n > 1) {
            int k = rng.Next(n);  // 0 <= k < n.
            n--;                     // n is now the last pertinent index;
            int temp = array[n];     // swap array[n] with array[k] (does nothing if k == n).
            array[n] = array[k];
            array[k] = temp;

        }
    }

Answer 9

Un buen algoritmo de barajado en tiempo lineal es el barajado de Fisher-Yates .

Uno de los problemas que encontrará con su algoritmo propuesto es que a medida que se acerca el final de la reproducción aleatoria, su ciclo pasará mucho tiempo buscando elementos elegidos aleatoriamente que aún no se hayan intercambiado. Esto puede tomar una cantidad de tiempo indeterminada una vez que llega al último elemento para intercambiar.

Además, parece que su algoritmo nunca terminará si hay un número impar de elementos para ordenar.

Answer 10

qué pasa :

System.Array.Sort(arrayinstance, RandomizerMethod);
...
//any evoluated random class could do it !
private static readonly System.Random Randomizer = new System.Random();

private static int RandomizerMethod<T>(T x, T y)
    where T : IComparable<T>
{
    if (x.CompareTo(y) == 0)
        return 0;

    return Randomizer.Next().CompareTo(Randomizer.Next());
}

voila!

Answer 11

itemList.OrderBy(x=>Guid.NewGuid()).Take(amount).ToList()

Answer 12

static Random random = new Random();

public static IEnumerable<T> RandomPermutation<T>(IEnumerable<T> sequence)
{
    T[] retArray = sequence.ToArray();


    for (int i = 0; i < retArray.Length - 1; i += 1)
    {
        int swapIndex = random.Next(i, retArray.Length);
        if (swapIndex != i) {
            T temp = retArray[i];
            retArray[i] = retArray[swapIndex];
            retArray[swapIndex] = temp;
        }
    }

    return retArray;
}

modificado para manejar listas u otros objetos implementando IEnumerable