Algorytm generowania losowej kolejności elementów

Jak dobrać losowo kolejność około 20 elementów o najniższej złożoności? (generowanie losowych permutacji)Algorytm generowania losowej kolejności elementów

Źródło

2009-11-07 Ante

Co masz na myśli przez cca? –

Analiza korelacji kanonicznej? –

Co masz na myśli przez około? : P –

jest dobrym wyborem.

Źródło

2009-11-07 02:33:48

Rozczarowujące, że ktoś powiedział coś innego, szczerze mówiąc. –

Cóż, jestem rozczarowany, że to jest odpowiedź. Ponieważ musisz najpierw przetestować listę, aby ją wypełnić, a następnie przetasować ją (z poprawnie dobranym algorytmem), pomyślałbym, że istnieje lepsze rozwiązanie. – SourceOverflow

Kilka miesięcy temu napisałem na blogu o uzyskaniu losowej permutacji listy liczb całkowitych. Możesz użyć tego jako permutacji indeksów zestawu zawierającego twoje elementy, a wtedy masz to, czego chcesz.

W pierwszym poście zbadać kilka możliwości i w końcu uzyskać "funkcja losowo permutate ogólny listę O (n) złożoność" , odpowiednio enkapsulowany do pracy na niezmiennych danych (tzn. jest wolny od efektów ubocznych).

W drugim poście udostępniam go jednolicie.

Kod jest w języku F #, mam nadzieję, że nie masz nic przeciwko!

Powodzenia.

EDIT: nie mam formalnego dowodu, ale intuicja mówi mi, że złożoność takiego algorytmu nie może być niższa niż O (n). Naprawdę byłbym wdzięczny za to, że zrobiłem to szybciej!

Źródło

2009-11-07 01:51:47

rekursja w drugim artykule jest prosta .. myślę, że mógłbym użyj go .. – Ante

Wszystkie permutacje muszą być możliwe, a ponowne ustawienie tablicy w derangement (czyli permutacja 'p' dla której' p (k)! = k' dla wszystkich 'k') wymaga, aby każdy element być odwiedzanym. Stąd O (n) najgorszy przypadek. Czy to wciąż nie jest wystarczająco formalne? –

Również O (n) przeciętny przypadek z tego samego dowodu, pomyśl o tym, ponieważ IIRC proporcja permutacji (1 ... n), które są derangencjami zbliża się do 1/e, gdy n zbliża się do nieskończoności. –

Prosty sposób losowania zamówienia polega na utworzeniu nowej listy prawidłowego rozmiaru (20 w twoim przypadku), iteracji na pierwszej liście i dodania każdego elementu w losowej pozycji do drugiej listy. Jeśli losowa pozycja jest już wypełniona, umieść ją w następnej wolnej pozycji.

myślę, że to pseudokod jest poprawna:

list newList 
foreach (element in firstList) 
    int position = Random.Int(0, firstList.Length - 1) 
    while (newList[position] != null) 
     position = (position + 1) % firstList.Length 
    newList[position] = element

EDIT: Okazuje się, że ta odpowiedź nie jest faktycznie tak dobry. Nie jest ani szczególnie szybki, ani szczególnie losowy. Dziękuję za twoje komentarze. Aby uzyskać dobrą odpowiedź, przewiń z powrotem na górę strony :-)

Źródło

2009-11-07 02:15:23

W najgorszym przypadku ten algorytm to O (n^2) (tzn. Jeśli generator liczb losowych mówi "1, 1, 1, 1, 1, 1, 1, ...", pozwalam ci obliczyć resztę) niezbyt zoptymalizowany. –

Umieszczenie przedmiotów w następnej wolnej pozycji powoduje, że jest mniej losowy. Przedmioty zachowają swoje pierwotne zamówienie bardziej niż w prawdziwie losowym tasowaniu. Aby to naprawić, musisz wybrać nową losową pozycję, gdy pozycja jest zajęta, co oczywiście sprawia, że jest znacznie wolniej. – Guffa

To dobry punkt Guffa. Nigdy tego nie zauważyłem. Dzięki. Przynajmniej coś się tutaj nauczyłem :-) –

Prawdopodobnie ktoś już zaimplementował tasowanie. Na przykład w Pythonie można użyć random.shuffle, w C++ random_shuffle oraz w PHP shuffle.

Źródło

2009-11-07 02:32:47

hmm .. php może? – Ante

Co zaskakujące, w PHP nazywa się 'shuffle' :). Zaktualizuję odpowiedź. –

Algorytm generowania losowej kolejności elementów

Odpowiedz

Powiązane problemy