Mireczki, mam problem. Potrzebuje funkcji (w javascript ale w sumie bardziej o algorytm niż konkretną implementacje się rozchodzi, więc może być inny język/pseudokod) która wygeneruje mi losową liczbę z zakresu od MIN do MAX ale nie jako trzeci parametrz przekazuję tablice numberów EXCLUDE i żaden z numerów z EXCLUDE nie może wystąpić w wyniku.
tzn. np:
randomExclude( 1 , 10 , [ 3,5] );
powinno wygenerować losową liczbę z zakresu od 1 do 10 ale nie może to być 3 i 5.
I teraz myk polega na tym, te tablice będą bardzo pojemne (setki tysięcy rekordów), więc bawimy się bez while itp. Tzn. te dwie koncepcje odrzucam:
a) wygenerowanie arraya dopuszczalnych wyników i potem pobrach randomowy losowego elementu b) losowanie while( wynik jest w odrzuconych ) { powtorz probe; }
Tzn. jak potrzebuje liczby od 1 do 10 ale wyłączając [3,5] to generuje liczbę od 1 do 8 i w przypadku wylosowania liczby większej niż 3 dodaje +1 ("przekręcam" na kolejną) a w przypadku 5 dodaje +2. Ale funkcja działa poprawnie tylko gdy jest jedna wartość w exlude, przy 2+ nie działa. Czuje że idę dobrą drogą ale brakuje mi jakiegoś małeog kawałka w tym, dlatego zwracam się do Was o pomoc :)
@matowoszary: no napisałem że taką koncepcje odrzucam bo będę potrzebował wygenerować losowo kilka liczb z zakresu np. od 1 do 500000 z wyłączem [23,171,99121,23125] itp. Aplikacja jest w Node.JS więc ja nie moge blokować event loopa generując sobie raz za razem tabliczki które mają po 500,000 elementów żeby potem usunąć z nich 5 elementów i wylosować. wiem że jest inny sposób na to :)
@larvaexotech: Koncepcyjnie to losujesz z tablicy min - max z usuniętymi liczbami z exclude. Wydajnie będzie to tak: losujesz liczbę od min do max-len(exclude) sprawdzasz, ile jest liczb w exclude mniejszych lub równych od wylosowanej (złożoność lg n, tablica exclude musi być wcześniej posortowana). dodajesz do wylosowanej liczby tę
@wczoraj: wywołanie funkcji ma wylosować jedną wartość od MIN do MAX ale nie wolno wylosować żadnej wartości z exclude. sama funkcja będzie w pewnych sytuacjach wywoływana kilkakrotnie.
co do >= to chodzi o to że chciałem zrobić tak że w przypadku parametrów MIN=1 MAX=10 i EXCLUDE=[3] żeby wylosować liczbę od 1 do 9 i gdy jest większa lub równa 3 to podbić ją o 1 co spowoduje że zestaw wyników
@MrGreeneye: ok faktycznie działa jak należy chociaż wbrew mojej intuicji. mi się wydaje że powinno być n<value a nie n<=value ale ten wariant @MrGreeneye działa jak należy.
Mireczki, mam problem. Potrzebuje funkcji (w javascript ale w sumie bardziej o algorytm niż konkretną implementacje się rozchodzi, więc może być inny język/pseudokod) która wygeneruje mi losową liczbę z zakresu od MIN do MAX ale nie jako trzeci parametrz przekazuję tablice numberów EXCLUDE i żaden z numerów z EXCLUDE nie może wystąpić w wyniku.
tzn. np:
randomExclude( 1 , 10 , [ 3,5] );
powinno wygenerować losową liczbę z zakresu od 1 do 10 ale nie może to być 3 i 5.
I teraz myk polega na tym, te tablice będą bardzo pojemne (setki tysięcy rekordów), więc bawimy się bez while itp. Tzn. te dwie koncepcje odrzucam:
a) wygenerowanie arraya dopuszczalnych wyników i potem pobrach randomowy losowego elementu
b) losowanie while( wynik jest w odrzuconych ) { powtorz probe; }
Mam obecnie taką funkcję:
http://pastebin.com/YfpsmTyU
Tzn. jak potrzebuje liczby od 1 do 10 ale wyłączając [3,5] to generuje liczbę od 1 do 8 i w przypadku wylosowania liczby większej niż 3 dodaje +1 ("przekręcam" na kolejną) a w przypadku 5 dodaje +2. Ale funkcja działa poprawnie tylko gdy jest jedna wartość w exlude, przy 2+ nie działa. Czuje że idę dobrą drogą ale brakuje mi jakiegoś małeog kawałka w tym, dlatego zwracam się do Was o pomoc :)
Komentarz usunięty przez autora
Koncepcyjnie to losujesz z tablicy min - max z usuniętymi liczbami z exclude. Wydajnie będzie to tak:
losujesz liczbę od min do max-len(exclude)
sprawdzasz, ile jest liczb w exclude mniejszych lub równych od wylosowanej (złożoność lg n, tablica exclude musi być wcześniej posortowana).
dodajesz do wylosowanej liczby tę
co do >= to chodzi o to że chciałem zrobić tak że w przypadku parametrów MIN=1 MAX=10 i EXCLUDE=[3] żeby wylosować liczbę od 1 do 9 i gdy jest większa lub równa 3 to podbić ją o 1 co spowoduje że zestaw wyników
faktycznie, kod ma identyczną logikę no i faktycznie tak samo nie działa :D
@larvaexotech: mniejsza równa od value, nie mniejsza?
dla potomnych pełna działająca funkcja:
http://pastebin.com/xtCzWzhb