Jak wybrać losowo posortowaną listę?

Question

Oto dziwne pytanie dla was,

Mam ładnie posortowaną listę, którą chcę wybrać losowo. Jak miałbym to zrobić?

W mojej aplikacji mam funkcję, która zwraca listę punktów opisujących kontur dyskretnego obiektu. Ze względu na sposób rozwiązania problemu funkcja zwraca ładnie uporządkowaną listę. Mam drugą granicę opisaną w matematyce i chcę określić, czy te dwa obiekty przecinają się wzajemnie. Po prostu iteruję po punktach i ustalam, czy jakikolwiek punkt znajduje się w granicach matematycznych.

Metoda działa dobrze, ale chcę zwiększyć prędkość poprzez losowanie danych punktów. Ponieważ jest prawdopodobne, że moja granica matematyczna pokryje się szeregiem punktów, które są obok siebie, myślę, że sensownym byłoby sprawdzenie losowej listy zamiast iterowania nad ładnym posortowanym (ponieważ zajmuje tylko jeden naciśnij, aby zadeklarować skrzyżowanie).

Więc, jakieś pomysły na temat losowania zamówionej listy?

Answer 1

Użyj std::random_shuffle. Jeśli chcesz zaimplementować metodę samodzielnie, powinieneś spojrzeć na Fisher-Yates shuffle.

Answer 2

Możesz wypróbować random_shuffle algorithm, ale pamiętaj, że nie będzie działał pod list, ponieważ wymaga iteratorów z dostępem swobodnym. Możesz go użyć na vector lub deque.

Answer 3

std::random_shuffle(thelist.begin(), thelist.end()); 

Answer 4

Zakładając, że "list" nie znaczy, połączonej listy, ale zamiast coś znaczy, że obsługuje losowego dostępu (np tablicę, std :: vector lub std :: deque), std :: random_shuffle może być przydatne.

Answer 5

Ale kluczowe pytanie brzmi, czy środowisko wykonawcze wymagane do zrobienia losowo listy nie może być czymś więcej niż środowisko wykonawcze do sekwencyjnego przechodzenia przez nią.

Być może to, co naprawdę musisz zrobić, to nie jest to randomizacja, ale raczej czytanie w innej kolejności niż od początku do końca. Na przykład, jeśli lista ma n członków, być może powinieneś przetworzyć 1, n, 2, n-1, 3, n-2, itd. Lub 1, n/2, 2, n/2 + 1, 3, n/2 + 2, itd.

Jeśli zawsze masz taką samą liczbę punktów lub liczba punktów przypada na mały, skończony zestaw, możesz złożyć zamówienie na ocenę punktową dla każdej możliwej liczby punktów z wyprzedzeniem albo prawdziwie losowe, albo może starannie obliczone w jakiś sposób.

Answer 6

 
int array[N]; 

for(int i = N - 1; i > 0; i--) { 
    int j = rand() % i; 
    int tmp = array[i]; array[i] = array[j]; array[j] = i; 
}