[Aportación] C# Números aleatorios sin repetirse

[Totemalf]

Buenas,
he creado un script con C# que permite asignar valores a los indices de una lista, sin que se repitan. Estoy seguro que no será la manera más ortodoxa ni la de mejor rendimiento, pero si a alguien le sirve genial. Si alguien quiere aportar un modo que tenga un mejor rendimiento sería genial. Saludos!

   int [] elemento = new int[10];

   void Awake ()
   {
   
      for(int contador1 =0;contador1<elemento.Length;contador1++)
      {

         elemento[contador1]= Random.Range(0,10);
         int contador2 =0;

         while(contador2<contador1)
         {
            if(elemento[contador2]==elemento[contador1])
            {
               elemento[contador1]=Random.Range(0,10);
                contador2 = 0;
               continue;
            }
            contador2++;
         }
      }
}

[Totemalf]

Versión 2, que creo que es más eficiente, y remarco lo de creo.

Código [Seleccionar] Expand

//Array de enteros. Quiero asignar un valor del 0 al 9 en cada indice sin que se repitan
// O lo que es lo mismo, distribuir los numeros del 0 al 9 entre los indices
int [] elemento = new int[10];

void Awake ()
{
//Asigno un valor al primer elemento del array fuera del for
elemento [0] = Random.Range(0,10);

//El for guarda un numero aleatorio en la variable numeroAzar
for(int contador1 = 1;contador1<elemento.Length;contador1++)
{
int numeroAzar = Random.Range(0,10);
int contador2 = 0;

//El while guarda el valor del numeroAzar en cada indide del Array
//si no existe ya en un indice anterior

while(contador2<contador1)
{
if (elemento[contador2]==numeroAzar)
{
numeroAzar= Random.Range(0,10);
contador2 = 0;
continue;
}
else
{
elemento [contador1]= numeroAzar;
}
contador2++;
}

}
}

[[EX3]]

Buenas.

Una forma más sencilla y generica:

Código [Seleccionar] Expand

static void foo(ref int[] array, int from, int to)
{
    Random rnd = new Random((int)DateTime.Now.Ticks);

    // Asignamos primer valor:
    int randomValue = rnd.Next(from, to);
    array[0] = randomValue;

    // Buscamos y asignamos los restantes:
    for (int i = 1; i < array.Length; i++)
    {
        // Mientras el valor generado ya exista en el array, seguimos buscando:
        while (array.Contains(randomValue))
        {
            randomValue = rnd.Next(from, to);
        }

        // Asignamos valor:
        array[i] = randomValue;
    }
}

Ejemplo de uso:

Código [Seleccionar] Expand

int[] values = new int[10];
values = Enumerable.Repeat<int>(-1, values.Length).ToArray(); // Inicializamos los valores a -1 (el 0 esta dentro del rango de valores que queremos asignar).
foo(ref values, 0, 10); // Rellena el array con valores unicos desde 0 a 10.

Salu2...

[montaycabe]

Yo usé hace poco un sistema similar al de totemalf, un bucle para generar el numero aleatorio y otro bucle anidado dentro para comprobar si ya habia sido asignado y repetir con otro numero aleatorio o bien avanzar el bucle al siguiente valor.

Una pregunta, el sistema de [ex3] es mas eficiente en cuanto a la hora de claridad de programar, no de rendimiento en ciclos ¿no?
Quiero decir, a nivel interno, codigo maquina o como se quiera llamar, cuando se invoca un array.Contains(randomValue) realmente la maquina hace un bucle recorriendo los valores de forma similar al bucle de totemalf ¿o estoy equivocado?

[[EX3]]

Una pregunta, el sistema de [ex3] es mas eficiente en cuanto a la hora de claridad de programar, no de rendimiento en ciclos ¿no?
Quiero decir, a nivel interno, codigo maquina o como se quiera llamar, cuando se invoca un array.Contains(randomValue) realmente la maquina hace un bucle recorriendo los valores de forma similar al bucle de totemalf ¿o estoy equivocado?

Buen apunte :)

He corrido una prueba usando las dos formas, con array.Contains y con un bucle For a pelo, usando un array de 500000 elementos, y estos son los resultados:

Array.Contains:
Inicio: 22:21:36
Fin: 22:49:44
Total: 28 minutos (casi media hora)

For loop:
Inicio: 23:03:38
Fin: 0:06:26
Total: 1h aprox.

El proceso ha tardado algo más de el doble al usar el bucle For, ergo array.Constains parece más optimo, al menos con enteros. Con strings si es posible que sea más lento por como trabaja .NET las cadenas internamente. Ahi seguro que el bucle For ira más rapido con mayor volumen de elementos a evaluar.

Salu2...

[Darago_malaga]

Que os parece una cosa como esta?
No la he probado. . . pero el concepto?


int [] elemento = new int[10];

   void Awake ()
   {
      int cont;
      int pos;
      int temp;

      //Primero rellenamos todo el array con valores ordenados
      for(cont =0;cont<elemento.Length;cont++)
      {
                 elemento[cont]=cont;
      }

      //Iremos recorriendo la lista del principio al fin intercambiando cada valor por uno al azar del resto de la lista
      for(cont =0;cont<elemento.Length;cont++)
      {
                 pos = Random.Range(cont,elemento.Length);
                 temp = elemento[pos];
                 elemento[pos]=elemento[cont];
                 elemento[cont]=temp;
      }

}

[[EX3]]

Acordandome ahora que en AS3 habia un metodo Shuffle en las colecciones, que es justamente para este proposito, y que en .NET no existe, he encontrado una implementacion de dicho metodo para C# en Stackoverflow como una opcion más a las propuestas:

http://stackoverflow.com/questions/273313/randomize-a-listt-in-c-sharp/1262619#1262619

Salu2...

[Totemalf]

Buenas,
gracias a todos por las respuestas y por vuestras ideas,
y gracias [EX3] por hacer la prueba, se ve claramente la falta de rendimiento en mi forma de hacerlo. Esta tarde haré más pruebas con lo que comentáis.
Por cierto, [EX3], como has hecho la prueba de rendimiento, ¿controlas cuando termina de ejecutarse de alguna forma? o tienes que estar pendiente a ver cuando acaba?

Un saludo!

[[EX3]]

Por cierto, [EX3], como has hecho la prueba de rendimiento, ¿controlas cuando termina de ejecutarse de alguna forma? o tienes que estar pendiente a ver cuando acaba?

Sencillamente tomo el tiempo inicial antes de la llamada y después de la llamada (dos variables DateTime). Con eso sacas la diferencia y tienes el tiempo que ha tardado la llamada. La información la sacas por consola.

Salu2...

[Totemalf]

Buenas,
creo que he encontrado un modo mejor de hacer esto, e imagino que será más eficiente, ya que no tengo la necesidad de hacer el for anidado de mis casos anteriores. ¿[EX3] serías tan amable de probar el rendimiento en tu computadora para poder comparar con los métodos anteriores?

Código [Seleccionar] Expand

List<int> listaEnteros = new List<int> ();
List<int> listaEnteros2 = new List<int> ();
public int numeroElementos = 10;
int numeroAleatorio;

void Awake ()
{

for (int contador = 0; contador < numeroElementos; contador++) {
listaEnteros.Add (contador);
print ("La posicion " + contador + " alberga el valor " + listaEnteros [contador]);
}
}

void Start ()
{

for (int contador2 = 0; contador2 <numeroElementos; contador2++)
{
numeroAleatorio = Random.Range (0, listaEnteros.Count);
listaEnteros2.Add(listaEnteros[numeroAleatorio]);
listaEnteros.RemoveAt (numeroAleatorio);
print (listaEnteros2[contador2]);
}
}

Me da la impresión de que es una forma de hacerlo más ingeniosa, espero no equivocarme y que me exploteis mi burbuja, ahora estoy de subidón. :P

Saludos y gracias

[[EX3]]

Muy buena idea la de usar dos listas en vez de un array y dos bucles. 23 segundos solo en desordenar 500000 elementos  :)

Tu implementacion lista para usar quedaria asi:

Código [Seleccionar] Expand

static void foo2(ref List<int> values)
{
    int itemCount = values.Count;
    int randIndex = 0;
    List<int> ret = new List<int>(itemCount);
    Random rnd = new Random((int)DateTime.Now.Ticks);
    for (int i = 0; i < itemCount; i++)
    {
        randIndex = rnd.Next(0, values.Count);
        ret.Add(values[randIndex]);
        values.RemoveAt(randIndex);
    }
    values.Clear();
    values.AddRange(ret);
}

Y ya picandome la curiosidad con este tema, he probado el algoritmo Shuffle que implementan en el articulo de stackoverflow que puse ayer, que lo hace con el mismo array de entrada y un solo bucle, y completa la operacion de desordenar los 500000 elementos en menos de un segundo. Es brutal la diferencia:

Código [Seleccionar] Expand

static void Shuffle<T>(ref IList<T> list)
{
    Random rng = new Random();
    int n = list.Count;
    while (n > 1)
    {
        n--;
        int k = rng.Next(n + 1);
        T value = list[k];
        list[k] = list[n];
        list[n] = value;
    }
}
Uso:

Código [Seleccionar] Expand

Shuffle<int>(ref listaEnteros);


Desde luego yo me quedaba con esta solucion sin duda ;)

Salu2...

P.D.: Acabo de darme cuenta que la implementacion de Darago_malaga es similar a esta ultima (por no decir practicamente lo mismo).

[Hechelion]

A mi hace poco me toco hacer algo parecido, necesitaban generar 200.000 códigos para etiquetas únicas y por esas manías de mi jefe quería que fueran aleatorias. Eso si, yo estaba usando Python no C#.

El problema que tenía, es que debido al formato de la etiqueta, no podía (o mejor dicho, no habría quedado "presentable") usar valores correlativos y luego "barajarlos". (idea que por cierto, encuentro genial como solución), ya que las etiquetas están compuestas por 10 caracteres hexacedimales que debí tratar como un string.

La solución real que le dí fue la misma que propuso exe en su primer post y simplemente dejé el script corriendo durante la noche y listo, ya que esto era un pedido puntual.


Sin embargo, esa noche me quedó dando vueltas la idea de como mejorar el algoritmo y lo que se me ocurrió fue usar 2 listas. La primera tendría los valores generados al azar y la segunda sería una pila binaria ordenada. ordenada mediante DYV.
En cada ciclo, el valor generado de forma aleatoria sería comparado contra la pila ordenada, lo cual significaba (en teoría) reducir el número de comparaciones de 200.000! a 200.000*18*2.

Reitero que esto solo fue una idea teórica que se me ocurrió. Aprovecho de comentarla, ya que en casos como el mio, donde no es posible contar con valores consecutivos podría servir para reducir considerablemente el tiempo de comparación.
Al final nunca lo probé, ya que como comentaba, era un pedido puntual, simplemente use la solución más simple y aproveche la fuerza bruta de la CPU.

[Totemalf]

Bueno,
pues al final  parece que entre todos se ha llegado a la forma más optima, que es la del articulo de stackoverflow = Darago_malaga. Así que me lo apunto.
De cualquier modo iré probando las diferentes formas para entenderlas, ya que estoy aprendiendo y aún me cuesta un poco entender algunas cosas de los códigos.

Lo dicho, muchas gracias!

[Gallo]

En realidad la mejor forma es esta:

[DiegoMGar]

Buenas! Veo que EX3 te ha sugerido el suffle, algo así venía yo a aportar. Pero más que venir a decirte por decirte, me gustaría ayudarte a entender porqué dos blucles anidados completos en función de la longitud de tu array es una terrible solución de búsqueda.
Para un vector con menos de cientos de miles de elementos puede ser una solución decente, pues requiere poca complejidad algorítmica, lo programas en un pispás y funciona bien.
Ahora bien, cuando se te dispara la longitud debes ser consciente de la eficacia y la carga temporal de tu solución, tras cada elemento, recorrer el vector entero en una búsqueda puede ser desastroso, o puede ser magnífico; no siempre van a salirte esas cargas temporales de media o una hora, pues será en función de la semilla de los elementos random.

Por qué? Piensa que cuando vas a añadir un elemento primero lo buscas, en el mejor de los casos nunca está, esto quiere decir que por cada nuevo elemento, recorrerás tu vector una vez.
Complejidad temporal de n*log(n), muy buena.

En el peor de los casos, puede repetirse indefinidas veces el recorrido en el vector, pues no solamente sí esté el elemento si no que además está a la cola. Esto podría darte incluso un abrazo mortal en el proceso, por no llegar al final, precisamente por ser random puede que siempre estén contenidos en el vector los nuevos números.

Ahora bien, como recomendación, sin entrar en la tremenda carga que tiene la creación de números aleatorios y que no es algo que se deba usar a la ligera y menos con rangos altos de números, siempre que quieras hacer búsquedas y puedas ordenar, ordena; en este caso con números enteros, puedes ordenas y deberías, los algoritmos de ordenación y de búsqueda ordenada están más que optimizados y estudiados dándote una capacidad enorme de desarrollo sin preocuparte de la carga temporal.

Te recomiendo mirar, en búsqueda la Búsqueda Dicotómica. Que lo que hace es dividirte el vector en mitades hasta encontrar el elemento, en un vector ordenado claro.

Y te recomiendo mirar, en ordenación, QuickSort, no es difícil de implementar pero sí laborioso, ahora bien, funciona brutalmente bien.

Te voy a dejar un gif sobre carga temporal de algoritmos de ordenación:


Y por último, si no te has cansado aún de leerme, experiencia personal en una prueba que hice el año pasado:
- BubbleSort 100k elements: 38 min
- QuickSort 100k elements: 0.002 secs

Un saludo!