Forma más eficiente de "ordenar" aleatoriamente (Reproducción aleatoria) una lista de enteros en C#

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

Un buen tiempo lineal algoritmo de barajar es el Fisher-Yates shuffle.

Un problema que encontrará con su algoritmo propuesto es que a medida que se acerca el final de la mezcla, 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 2

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 realice un intercambio, simplemente elimínelos de la agrupación.

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

Answer 3

No estoy seguro del factor de eficiencia, pero he utilizado algo similar a lo siguiente, si no se opone a la utilización 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; 
} 

uso de este, usted no tiene que preocuparse sobre el intercambio intermedio.

Answer 4

Como Greg señaló que el Fisher-Yates shuffle sería el mejor enfoque. Aquí es 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) proporcionar suficientemente al azar y sin resultados

Answer 5

¿No sería algo así como ¿este trabajo?

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 6

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 de aplicación IEnumerable

Answer 7

Podemos hacer un método de extensión de esto para conseguir un empadronador 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]; 
     } 
    } 
} 

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

Answer 8

Hice un método usando una Hashtable temporal, permitiendo que la 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 9

Supongo que las últimas dos líneas se deben intercambiar en la respuesta de Micah. Por lo tanto, el código podría ser como

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 10

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

Answer 11

respuesta de ICR es muy rápido, pero las matrices resultantes no se distribuyen normalmente. Si desea 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 lenta que la ICR condición, sin embargo esta es la única manera de que pudiera llegar a obtener una distribución resultado normal

Answer 12

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

listo!