Alla ricerca di un buon algoritmo per la distribuzione equa

Question

Sto lavorando a un'applicazione in cui molti ritagli di giornale devono essere "lanciati" casualmente su un tavolo. tuttavia, se si utilizza il vero casuale, c'è sempre la possibilità che tutti i clip vengano visualizzati in un unico punto. il cliente preferirebbe una distribuzione casuale più "uguale".

una delle mie soluzioni era: se ho 20 clippings, calcoli una griglia con 20 campi e poi metti ogni ritaglio in un campo con posizioni x/y casuali all'interno di quel campo.

qualcuno ha una soluzione migliore/più intelligente?

grazie mille!

Answer 1

Quello che stai cercando è noto come una sequenza quasi casuale (o una sequenza di discrepanze basse). Ci sono diverse sequenze ben note come questa, ecco lo Wikipedia entry. A seconda della lingua prescelta, potrebbero essere disponibili librerie pronte all'uso (un paio di esempi sono menzionati in questa domanda: Recommendations for Low Discrepancy (e.g. Sobol) quasi-random sequences in Python/SciPy?).

Answer 2

Ecco quello che vorrei fare ....

come si tratta di ritagli suppongo che la parte visiva è importante anche ...

Vorrei dividere il tavolo in 4 parti uguali (in superficie) e una ulteriore parte (sovrapposta) che rappresenta il centro del tavolo. puoi sempre giocare con il numero di 4 e renderlo 6 o 8 ma non andare fino a 20.

Ora dividi i ritagli a posizioni x/y casuali sulle 5 parti.

In questo modo si avrà sempre un centro "forte" del proprio tavolo, ma si garantisce che non tutti i ritagli si trovano su una pila.

Answer 3

Forse il modo più semplice per risolvere questo problema è appiattirlo su un oggetto lineare. Una griglia di 4 x 5 può diventare una lista di 20. Basta assegnare a ciascun 'slot' un numero (da 0 a 19) e utilizzare il seguente algoritmo. Spero non ti dispiaccia Java.

private void randomSlotFiller(int numberOfSlots) { 
    List<Integer> list = new ArrayList<Integer>(); 
    Random random = new Random(); 
    for (int i = 0; i < numberOfSlots; i++) { 
     list.add(i); 
    } 
    while(!list.isEmpty()) { 
     System.out.print(list.remove(random.nextInt(list.size())) + " "); 
    } 
} 

L'algoritmo funziona nel seguente modo:

1. Creare una lista vuota
2. Riempire la lista con i nostri numeri di slot
3. casualmente selezionare e rimuovere uno slot fino a quando nessuno rimangono.

Ovviamente la stampa dei numeri non sta andando molto bene, quindi modificare il codice secondo necessità.

Un'uscita esempio potrebbe essere:

15 9 17 13 8 10 6 11 3 7 2 19 4 0 12 18 16 5 1 14 

Nota: Questo algoritmo fornisce una distribuzione uniforme in tutti gli slot '' nel corso di molti iterazioni.

Answer 4

Ecco un semplice approccio a forza bruta:

• tenere un elenco dei punti che avete già scelto.
• raccogliere punti n casuali
• Selezionare tra di loro al punto che ha la maggiore distanza minima a tutti i punti sulla vostra lista, buttare via gli altri
• aggiungere che punto l'elenco dei punti che avete scelto
• ripetizione finché non si hanno abbastanza punti

Fondamentalmente, si provano sempre più punti e si sceglie solo quello più lontano da tutti i punti precedentemente scelti.

Il tempo di esecuzione è O (n²)