Scegliere un numero intero casuale in un intervallo tale che non sia uguale a un numero particolare

Question

Scegliere un numero intero casuale in un intervallo tale che non sia uguale a un numero particolare

#1 da (15 voti)
#2 da (6 voti)
#3 da (0 voti)

3

Dato un intervallo intero e un numero all'interno di tale intervallo, qual è il modo ragionevolmente robusto ed efficace per selezionare casualmente un nuovo numero nell'intervallo in modo tale che non sia uguale al numero specificato?

Ogni volta che ho bisogno di farlo, di solito uso qualcosa come:

// Randomly choose an integer within an inclusive range with the condition
// that the result not equal the previous number chosen
// INPUT: lastNum is an int in the range [minVal, maxVal]
int ChooseNewNumber(lastNum){

    minVal = 0;
    maxVal = N; // This would usually be a value like someContainer.size - 1
    intervalLength = maxVal - minVal + 1;

    // Assume RandomInt...() is an existing function that lives up to its name
    int newNum = RandomIntWithinInclusiveRange(minVal, maxVal);

    if (newNum == lastNum){
        // Add a random offset to newNum and wrap around if necessary
        newNum = (newNum+RandomIntWithinInclusiveRange(1, intervalLength - 1)) % (maxVal+1);
    }

    return newNum;
}

Funziona e sembra evitare l'introduzione di qualsiasi bias nel caso newNum == lastNum , ma è un po 'goffo. C'è un modo più pulito per realizzare la stessa cosa?

EDIT: come sottolineato da coredump, il metodo sopra non funziona se minVal != 0 . Solo per riferimento, la linea:

newNum = (newNum+RandomIntWithinInclusiveRange(1, intervalLength - 1)) % (maxVal+1);

dovrebbe essere:

new = ((new + RandomIntWithinInclusiveRange(1, intervalLength - 1) - minVal) % intervalLength) + minVal;

Mi rendo conto che questo errore ha dato l'impressione che minVal potrebbe sempre essere 0; mi dispiace per questo.

refactoring random

posta Reign of Error 05.12.2014 - 17:21

fonte

3 risposte

6

Basta scegliere tra 1 e N e restituire 0 se il valore è lastNum .

int ChooseNewNumber(lastNum){ 
    random = RandomIntWithinInclusiveRange(1, N);
    if (random == lastNum) {
        return 0;
    }
    return random;
}

Oppure la versione più corta, se preferisci:

int ChooseNewNumber(lastNum){
    random = RandomIntWithinInclusiveRange(1, N);
    return (random == lastNum ? 0 : random);
}

La risposta generica (EDIT)

C'è stata una piccola confusione sul motivo per cui ho effettivamente scritto 0 e 1 invece di minVal e maxVal . Per la mia difesa, ho trovato la domanda originale ugualmente confusa ;-) (cfr. commento ). Ecco una versione modificata, con quelle variabili date come parametri e con tutte le ipotesi esplicitamente controllate:

int ChooseNewNumber(minVal, maxVal, lastNum){

    assert(minVal =< lastNum);
    assert(lastNum =< maxVal);
    assert(minVal < maxVal); /* there is at least one value */

    random = RandomIntWithinInclusiveRange(minVal, maxVal);
    return (random == lastNum ? (minVal + 1) : random);
}

Si noti tuttavia che poiché si suppone che lastNum sia l'ultimo numero selezionato, possiamo tranquillamente supporre che appartenga all'intervallo previsto.

Di seguito, presumo ancora che minVal sia 0 e maxVal sia N , il che ha senso nel mio esempio e semplifica la spiegazione.

Spiegazione

Immagina un mazzo di 4 carte:

ABXD

X è in posizione lastNum .

Quindi, scegli solo A, B o D.

Questo è equivalente al prelievo di una carta a caso in questo set,

XBAD

... dove scambieresti lastNum e 0 e scegli un elemento tra 1 e N .

In realtà, puoi farlo senza scambiare gli elementi.

risposta data 05.12.2014 - 21:25

fonte

0

Puoi anche scegliere il metodo scrabble:

Genera una lista di numeri da 1-N;
Seleziona un elemento casuale da questo elenco;
Rimuovi questo elemento dall'elenco;
Utilizza l'elenco modificato quando ti serve il tuo prossimo numero.

È semplicemente impossibile disegnare lo stesso numero due volte di fila, perché il numero non è più nella lista. È simile a ciò che accade nei giochi come Scrabble o Rummy.

nel codice C # (non testato):

//do this during the setup phase
List<int> numberRange = Enumerable.Range(0, N).ToList();
Random random = new Random(); //Or your random implementation of choice

//Do this when you need a number
int index = random.Next(numberRange.Count);
int chosenNumber = numberRange[index];
numberRange.Remove(chosenNumber);
return chosenNumber;

Si noti che questo scala in modo lineare in memoria con N e nel tempo con N durante la generazione dell'elenco. Deve essere utilizzato se è necessario assicurarsi di non avere lo stesso articolo due volte. Se non vuoi tirare lo stesso numero due volte di fila (ma vuoi comunque che il numero prima dell'ultimo numero sia un'opzione), devi mantenere l'elenco originale e rimuovere l'ultimo elemento usando Eccezione () PRIMA di te genera il tuo indice.

risposta data 06.12.2014 - 00:33

fonte

Leggi altre domande sui tag refactoring random

I puntatori esistono davvero in Java? [duplicare] Se la condizione non è vera: valore predefinito o altra clausola? [chiuso]

score 15 · Accepted Answer

Prendi un numero nell'intervallo [minVal, maxVal-1] e aggiungi 1 se è maggiore o uguale a lastNum

int ChooseNewNumber(lastNum){
    minVal = 0;
    maxVal = N;
    if(minVal > lastNum || lastNum > maxVal){ 
        //if lastNum is outside range then just take full range
        return RandomIntWithinInclusiveRange(minVal, maxVal);
    }
    random = RandomIntWithinInclusiveRange(minVal, maxVal-1);
    if(lastNum <= random) random++;
    return random;
}