Losowanie zbioru par wartości

pytanie zadane 25 kwietnia 2016 w Algorytmy przez Surykat Stary wyjadacz (14,780 p.)

Cześć!

Mam taki ciekawy problem do rozwiązania- wylosować zestaw par koordynatów x oraz y w taki sposób, aby żadna para się nie powtarzała (może jednak w tym zbiorze istnieć punkty takie jak (1,2) i (2,1)).

Do zrobienia, ale odrzucam wszystkie rozwiązania, które zawierają w sobie następujący mechanizm:

"Jeśli zbiór zawiera już taką parę, powtórz losowanie."

Chwilowo stanęło na tym:

1. Generuje sobie 2 listy, X oraz Y, takie że X[i] = i oraz Y[i] = i dla 1>=i<=n

2. Zamieniam w losowy sposób kolejność elementów w obu listach

3. Biorę pierwsze m rozwiązań, gdzie m to liczba par, którą potrzebuje

Wszystko fajnie, tylko mnie dziś prowadzący uświadomił, że w tym algorytmie, odpadają mi możliwości par, jak (2,1), (2,2) itd, a takie też mi są potrzebne. Macie jakiś pomysł?

komentarz 26 kwietnia 2016 przez Surykat Stary wyjadacz (14,780 p.)

Ok, znalazłem rozwiązanie (chociaż zapewne nieoptymalne, ale spełniające założenia :) ).

Otóż rozszerzyłem moją koncepcję- generuję wszystkie możliwe pary x, y i to je mieszam, wybierając m par.

Znacie jakiś ciekawszy pomysł?

1 odpowiedź

odpowiedź 27 kwietnia 2016 przez Magicone Nałogowiec (45,100 p.)

Em, jeśli masz określoną szerokość układu współrzędnych, to możesz zdobyć "unikalny" indeks do nich ze wzoru Y*szerokość+X, można powiedzieć, że działa on tak, że każdy punkt jest numerowany od lewej do prawej strony, po zakończeniu jednego wiersza przechodzi do następnego.

http://i.imgur.com/MJJiPjg.jpg → tu masz przykład