Szukam dobrego algorytmu dla równej dystrybucji

Question

Pracuję nad aplikacją, w której wiele wycinków z gazet należy "rzucać" losowo na stół. Jednak w przypadku korzystania z prawdziwych losowych zawsze istnieje możliwość, że wszystkie klipy pojawią się w jednym miejscu. klient wolałby bardziej "równy" losowy rozkład.

Jednym z moich rozwiązań było: jeśli mam 20 wycinków, obliczyć siatkę z 20 polami, a następnie umieścić każdy wycinek w polu z losowymi pozycjami x/y w obrębie tego pola.

Ktoś ma lepsze/mądrzejsze rozwiązanie?

wielkie dzięki!

Answer 1

To, czego szukasz, jest znane jako quasi-losowa sekwencja (lub sekwencja o małej rozbieżności). Istnieje kilka dobrze znanych takich sekwencji, oto Wikipedia entry. W zależności od wybranego języka mogą być dostępne gotowe biblioteki (w tym pytaniu wymieniono kilka przykładów: Recommendations for Low Discrepancy (e.g. Sobol) quasi-random sequences in Python/SciPy?).

Answer 2

Oto co chciałbym zrobić ....

Jak to jest o wycinki przypuszczam, że część wizualna jest również ważne ...

chciałbym podzielić tabelę na 4 części (w równych powierzchni) i jeszcze jedna (nakładająca się) część, która reprezentuje środek tabeli. zawsze możesz grać z liczbą 4 i zrobić 6 lub 8, ale nie osiągnę 20 punktów.

Teraz dzielisz losowo pozycje x/y na 5 części.

W ten sposób zawsze będziesz mieć "mocne" centrum stołu, ale gwarantujesz, że nie wszystkie ścinki są na jednym stosie.

Answer 3

Być może najprostszym sposobem rozwiązania tego problemu jest spłaszczyć go do obiektu liniowego. Siatka 4 x 5 może stać się listą 20. Po prostu podaj każdemu 'szczelinie' numer (0 - 19) i użyj następującego algorytmu. Mam nadzieję, że nie masz nic przeciwko Javie.

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())) + " "); 
    } 
} 

Algorytm działa w następujący sposób:

1. Utwórz pustą listę
2. Wypełnij listę numerów z naszych gier
3. losowo wybrać i usunąć gniazda, aż żaden pozostają.

Oczywiście tylko drukowanie numery nie zrobi wiele dobrego, więc zmodyfikować kod, ile potrzeba.

Przykładem może być produkcja:

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

Uwaga: Ten algorytm zapewnia równomierne we wszystkich „gniazd” w ciągu wielu iteracji.

Answer 4

Tutaj jest bardzo proste podejście brute-force:

• przechowywać listę punktów, które zostały już pobrane.
• pick n losowo punktów
• wybrać spośród nich ten punkt, który ma największy minimalny dystans do wszystkich punktów na liście, wyrzucić inni
• dodać ten punkt do listy punktów wybrali
• powtarzania do momentu uzyskania wystarczającej liczby punktów:

Zasadniczo zawsze wypróbowujesz wiele punktów i wybierasz tylko ten, który jest najdalej od wszystkich wcześniej wybranych punktów.

Czas pracy to O (n²)