Ottieni numeri casuali univoci entro limiti predefiniti

Dipende molto da quanto grande range <y,z> viene confrontato con x . Se range è enorme e x è piccolo, usa il primo algoritmo. Se sono approssimativamente uguali, usa il secondo.

C'è una terza opzione è semplicemente prendere tutti i numeri in range <y,z> , mischiarli e prendere x numeri dall'inizio. Ma questa è solo una versione diversa del secondo algoritmo. Sarà inefficace se range è grande e x è piccolo.

Una soluzione che non sembra essere stata trovata:

In pseudocode

def unique-random-in-range(count, bot, top):
    let B = new List[Integer](count)

    for i = 0 to n - 1:
        B[i] = random-in-range(bot, top - i)

    for gen = 0 to n - 1:
        for gen' = gen + 1 to n - 1:
            if B[gen'] >= B[gen]:
                B[gen']++

    return B

In inglese:

L'intuizione di base è questa, quando selezioniamo un numero che vogliamo essere in grado di saltarci sopra l'iterazione successiva. Quindi, se selezioniamo 5 su [1..10] , vogliamo che la prossima volta agisca come se selezionassimo da [1..10] \ {5} . Potremmo farlo con la tua proposta di verificare se abbiamo colpito 5 o un altro numero già selezionato e riprovare, ma un modo migliore è quello di fare quanto segue: la seconda volta selezioniamo da [1..9] e rappresentiamo il fatto che% il5 è stato eliminato incrementando tutti i futuri prelievi di >= 5 .

Come esempio, se vogliamo selezionare 4 valori da [1..10] , potremmo passare alla seguente sequenza:

Start:
    B = []

Pick values:
    i = 0:
          pick 5 from [1..10]:
              B = [5]
    i = 1:
          pick 2 from [1..9]:
              B = [5, 2]
    i = 2:
          pick 5 from [1..8]:
              B = [5, 2, 5]
    i = 3:
          pick 3 from [1..7]:
              B = [5, 2, 5, 3]

Normalize:
    i = 0 (B[0] = 5):
         B = [5, 2, 6, 3]
    i = 1 (B[1] = 2):
         B = [5, 2, 7, 4]
    i = 2 (B[2] = 7):
         B = [5, 2, 7, 4]
    i = 3 (B[3] = 4):
         B = [5, 2, 7, 4]

Speriamo che questo dia intuizione su come funziona e perché i valori sono garantiti per essere distinti e nella gamma. (Esercizio per il lettore: provalo.)

Se lasciamo che n sia il numero di valori desiderati e k sia la dimensione dell'intervallo, questo algoritmo avrà la complessità temporale O(n^2) e spazio O(n) . L'algoritmo shuffle suggerito da Euforic avrà la complessità del tempo e dello spazio O(k) . Pertanto, puoi provare questo metodo quando n è minore di sqrt(k) e shuffle altrimenti.

Non utilizzare l'elenco come ricerca O (n)

Usa hashset quando ottieni la ricerca O (1)

Aggiungi o Rimuovi a seconda della frazione dell'intervallo che stai cercando

public static HashSet<int> RandomFromXtoY(int x, int y, int k)
{
    if (x > y)
        return RandomFromXtoY(y, x, k);

    HashSet<int> hs = new HashSet<int>();
    if (k > (y - x + 1))
        return hs;

    Random rand = new Random();
    int next;

    if (k > (y - x) * 2 / 3)
    {
        hs = new HashSet<int>(Enumerable.Range(x, y - x + 1));
        while (hs.Count > k)
        {
            next = rand.Next(x, y + 1);  //net max is not inclusive
            hs.Remove(next); //duplicate just fails
            if (next == x)
                x++;
            else if (next == y)
                y--;
        }
    }
    else
    {
        while (hs.Count < k)
        {
            next = rand.Next(x, y + 1);  //net max is not inclusive
            hs.Add(next); //duplicate just fails
            if (next == x)
                x++;
            else if (next == y)
                y--;
        }
    }
    return hs;
}

Quanto sopra sarà più veloce ma sotto è garantito che sia O (n + k) dove n è il numero di elementi da selezionare e k è il numero da selezionare. Si basa su Shuffle di FisherYate, ma esce shuffle non appena ha k elementi. Il shuffle cambia posizione in modo tale che il numero non venga preso in considerazione in futuro.

public static IEnumerable<int> RandomFromXtoYshuffle(int x, int y, int k)
{
    int n = y - x + 1;
    if (k <= n && k > 0)
    {
        if (x > y)
        {
            int xTemp = x;
            x = y;
            y = xTemp;
        }
        List<int> range = new List<int>(Enumerable.Range(x, n));
        Random rand = new Random();
        for (int i = n - 1; i >= n - k; i--)
        {
            if (n == k)
                yield return range[i];
            else
            {
                int swapIndex = rand.Next(i + 1);  //.net rand max is not inclusive
                yield return range[swapIndex];
                if (swapIndex < i)
                    range[swapIndex] = range[i];
            }
        }
    }
}

Vorrei utilizzare una struttura dati impostata per archiviare gli interi. In un set, tutti gli oggetti sono unici (almeno in Python). Quindi diciamo che abbiamo una funzione

rand_int(y, z): #returns a random integer between y and z

Potresti farlo in questo modo:

x = 10 #number of integers we want to generate
randints = set()

while size(randints) < x:
    randints.add(rand_int(y, z))

Ovviamente, dovresti controllare se l'intervallo tra y e z è abbastanza grande da generare x di interi.

EDIT:

Diciamo che hai una funzione

rand_choice(list): #Returns a random integer from a list

È possibile generare un elenco di numeri tra y e z, quindi eseguire la funzione rand_choice () x volte e salvare le uscite in un altro elenco.

Questo metodo dovrebbe essere usato solo con un insieme relativamente piccolo di numeri interi.