Quale di questi due algoritmi shuffle è più casuale?

Naviga le tue risposte
3

Quale dei seguenti due algoritmi shuffle ( shuffle1 e shuffle2 ) è più casuale? 

public final class Shuffle {
    private static Random random;

    public static void shuffle1(final Object[] array) {
        if (random == null) {
            random = new Random();
        }

        for (int i = array.length - 1; i > 0; i--) {
            swap(array, i, random.nextInt(i + 1));
        }
    }

    public static void shuffle2(final Object[] array) {
        if (random == null) {
            random = new Random();
        }

        for (int i = 0; i < array.length; i++) {
            swap(array, i, i + random.nextInt(array.length - i));
        }
    }

    protected static void swap(final Object[] array, final int i, final int j) {
        final Object tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}

L'algoritmo shuffle2 garantisce che tutti gli elementi siano direttamente toccati, ma, in shuffle1 algoritmo, l'elemento con indice = 0 non viene mai direttamente toccato a causa della condizione i > 0 .

    
posta robosoul 19.09.2013 - 10:57
fonte

2 risposte

8

Se vuoi solo un shuffle usa Collections.shuffle(Arrays.asList(array)); che è stato scritto da persone più intelligenti di te e me.

Per quanto riguarda la garanzia che il primo elemento venga toccato, considera che nel secondo algoritmo l'ultimo passo (quando i==array.length-1 ) che stai chiamando random.nextInt(1) che restituisce sempre 0 che rende questo passo senza significato

Oltre a ciò gli algoritmi sono equivalenti.

    
risposta data 19.09.2013 - 11:16
fonte
11

Supponendo che il generatore di numeri casuali sia sufficientemente robusto, l'algoritmo ottimale è Fisher-Yates shuffle

L'algoritmo può essere riassunto come segue: - 

Given a list of items numbered from 1 to N
Pick a random item between 1 and N and swap with item N
Pick a random item between 1 and N-1 and swap with item N-1
...
Pick a random item between 1 and 2 and swap with item 2.

Ovviamente se l'elemento selezionato è già in posizione, non è necessario effettuare lo scambio.

Il punto chiave è evitare di scambiare di nuovo un oggetto, una volta che è stato collocato in posizione. Vedi qui per una discussione sul pregiudizio che può essere introdotto se fare.

    
risposta data 19.09.2013 - 11:24
fonte

Leggi altre domande sui tag

Specifiche delle dichiarazioni Switch e If Posiziona le variabili usate frequentemente dalla stessa funzione sull'heap?