Generator współrzędnych <C++>

[szymok]

Witam.

Wykonuje projekt w C++ rozwiązujący problem komiwojażer. Miasta (czyli ich punkty w układzie x,y), mają być generowane losowo. Pojawia się tutaj moje pytanie. Czy język C++ oferuje generator losowy (bądź pseudolosowy), który będzie w stanie wylosować określoną ilość unikatowych par liczbowych? Czy istnieją biblioteki, które jakoś mi z tym pomogą? A może któryś z Użytkowników posiada zoptymalizowany kod takiego generatora? Oczywiście biorę pod uwagę sprawdzanie wszelkich poprzednich par, jednak chciałbym lepiej rozwiązać ten problem. 

Pozdrawiam.

[webtom]

Kojarzy mi się taki wzór:

f(i) = A * i % B

Jeżeli A i B będą względnie pierwsze (brak wspólnych dzielników poza 1), to dla i z przedziału <0, B-1> uzyskasz unikalne wartości z tego właśnie przedziału. Jako że B będzie z góry znane, to wystarczy zapewnić, żeby A było odpowiednio dużą (żeby przypadkiem nie stało się dzielnikiem B) liczbą pierwszą. Przy okazji wypada się zatroszczyć, żeby iloczyn A*B mieścił się w zakresie wartości użytego typu danych.
(przy czym uczyłem się o tym ze ~3 lata temu, więc być może są do spełnienia jeszcze jakieś dodatkowe warunki, o których zdążyłem już zapomnieć)

Wracając do mapy - dla uproszczenia założę, że ma mieć identyczne wymiary - n. Przyjmujesz wtedy B=n*n, a kolejne punkty mają współrzędne x=f(i)/n oraz y=f(i)%n.

[[Ekspert] Hakken]

Generator liczb losowych

Generatora liczb losowych niestety w prawdziwym komputerze nie uświadczysz.

Generator liczb pseudolosowych

W bibliotece <random> masz sporo możliwości losowania, wyboru rozkładu itd. kilka słów o tym napisał Kerrek na StackOverflow: http://stackoverflow.com/a/7114482

Losowanie bez powtórzeń

Generatory liczb pseudolosowych losują liczby, zmiana ich tak, żeby nie generowały duplikatów byłaby dość ciężka i bezsensowna, tym się musisz zająć sam. Możesz to zrobić albo zapamiętując wszystkie wylosowane elementy i przy każdym kolejnym sprawdzać czy jest unikatowy, albo wygenerować "ręcznie" dużo możliwych wyników i tylko generować indeksy tych, które zostaną użyte. Tutaj można zrobić taką sztuczkę, że jeżeli masz N elementów w tablicy, to losujesz indeks `i` należący do [1, n], a następnie wykonujesz swap(i, n). Wtedy losujesz znowu już od 1 do n-1, potem swap (i, n-1) i tak dalej. Dzięki temu masz pewność, że nie będziesz miał pecha (nie będziesz ciągle losował tego samego elementu).
Jak łatwo sprawdzać czy dany element wcześniej wystąpił? Możesz użyć standardowej implementacji set albo unordered_set. 

"Lepiej rozwiązać ten problem"
Po co efektywnie losować dane do problemu komiwojażera? Problem i tak jest NP-trudny, więc to czy wylosujesz dane w czasie liniowym, kwadratowym czy sześciennym nie ma znaczenia.