Świąteczne prezenty – kto komu?

Nadchodzą Święta Bożego Narodzenia, a więc temat świąteczny. Wyobraźmy sobie kilka rodzin, które zasiadają przy stole. Chcemy dla uporządkowania wylosować obdarowywanych w taki sposób, aby każda osoba dawała prezent innej osobie. Jak to zrobimy?

Oczywiście – powiecie, możemy łatwo zorganizować to za pomocą kartek papieru. Każdy napisze swoje imię na kartce, wrzucimy je do pojemnika, i każdy wyciągnie jedną kartkę. Proste 😉 Lecz nie do końca. Co będzie, jeśli wyciągniemy kartkę z własnym imieniem? Musielibyśmy wiedzieć, która kartka jest nasza. Jak zrobić, abyśmy my wiedzieli, ale inni nie? Pomyslcie, może wpadniecie na rozwiązanie, czekam na komentarze.

Ja chciałbym zaproponować, abyśmy zabawili się w losowanie komputerowe – oczywiście z Pythonem w tle.

Napiszmy program, który będzie działał wg schematu:

• na początku mamy listę osób, które są unikatowe – to ważne! Jeśli lista nie będzie unikatowa, program nie zadziała, gdyż nie będzie mógł jednoznacznie rozróżnić osób do losowania.
• w pętli będziemy wykonywać wyszukiwanie dla każdej osoby z listy
• utworzymy zbiór osób, który będzie zawierał wszystkie osoby poza tą jedną, dla której będziemy szukać osoby do obdarowywania
• wylosujemy liczbę spośród liczby osób możliwych do obdarowywania
• sprawdzimy, czy wylosowana osoba nie jest już przez przypadek obdarowywana przez kogoś innego
• jeśli nie, to od razu przypisujemy ją do osoby, dla której wyszukujemy i przechodzimy do kolejnej osoby na liście (tworzymy element słownika)
• jeśli osoba znajduje się już jako obdarowywana przez kogoś innego, wówczas wyświetlamy znak kropki „.” (tak dla wizualizacji) i wyszukujemy inną liczbę – oczywiście może się zdarzyć, że wylosujemy kilkanaście razy tę samą liczbę, ale to możemy rozwiązać modyfikując algorytm wyszukiwania; jestem ciekaw Waszych propozycji w komentarzach
• kiedy już znajdziemy osobę, która może być obdarowywana, wpisujemy informację na ekranie, dodajemy parę osób do słownika i przechodzimy dalej

Kiedy już wykonamy te działania dla wszystkich osób na liście, zakończymy działanie programu.

Oto kod funkcji w serwisie Pastebin oraz zrzut ekranu środowiska Mu-Editor oraz IDLE, w których wykonywany jest ten program.

Możemy zauważyć, że dla ostatniej osoby na liście wyszukiwanie trwało najdłużej (10 znaków kropki).

Czy można to zoptymalizować? Zapraszam Was do analizy 😉