wybór losowy, z pominięciem jednej wartości
Wlodzimierz Holsztynski
(w C++).
Gdy chcemy wybrać losowo int x, spełniający;
0 \< x < d
to sprawa jest prosta:
x = random() % d;
To wszystko. Czasem jednak chcemy pominąć
pewną wartość b z tego przedziału (bo powiedzmy,
już mamy "obecną wartość" i chcemy "następną",
różną od obecnej). Można to yzyskać tak::
x = random() % (d-1);
x += (x >= b);
Można to napisać także w jednej linijce:
(x = random() % (d-1)) += (x >= b);
Kwestia gustu :-)
Pozdrawiam,
Wlodek
dK
ale sprawa się komplikuje
jeśli chcemy wyłączyć nie jedną a kilka wartosci
W skrajnym przypadku algorytm musi reagować, gdy
chcemy wyłaczyć wszystkie wartości z przedziału.
Ale jeśli tylko wyłączamy jeden element to
zaproponowany zapis jest jak najbardziej prawidłowy.
No może jeszcze tylko taki mały drobiazg, warunek nałożony na
dziedzinę d
d>1 co by nie było random() %0
Pozdrawiam
Darek
Wlodzimierz Holsztynski
> Tak, dla wyłączenia jednej wartości to zadziała,
> ale sprawa się komplikuje jeśli chcemy wyłączyć
> nie jedną a kilka wartosci
Nie chciałem się rozpisywać, więc nie podałem
dyskusji tła. Przy wybieraniu ruchów w zupełności
wystarczy omijanie natychmiastowych powtórek.
Inne wystąpią tak rzadko, że prościej i chyba
rachunkowo wydajniej jest nie martwić się o nie.
Szansa powtorzenia tej samej konfiguracji będzie
przy sporych bazach niewielka. Gdy to się zdarzy,
to strata czasu będzie mała, ścieżka prawie na
pewno powędruje w inną stronę już w pierwszym
kroku.
> W skrajnym przypadku algorytm musi reagować, gdy
> chcemy wyłaczyć wszystkie wartości z przedziału.
Można do tego podejść na jeden z 2 sposobów,
Jeżeli zabronionych wartości jest relatywnie
mało w porównaniu z dozwolonymi, to można
losować do skutku.
Można też ograniczyć się do pojedynczego
losowania, ale kosztem poważnych rachunków.
Chyba nie ma cud-rozwiązania. Dodatkowe
konstrukcje mogą dać złudzenie, ale trzeba je
wciąż uaktualniać.
> Ale jeśli tylko wyłączamy jeden element to
> zaproponowany zapis jest jak najbardziej prawidłowy.
>
> No może jeszcze tylko taki mały drobiazg, warunek
> nałożony na dziedzinę d, d>1 co by nie było
> random() %0
Tak, dziękuję, że zwróciłeś na to uwagę.
Myślałem o specyficznym zastosowaniu
do wyboru wykładnika liczby pierwszej
p \in Q, z bazy (z nośnika bazy). Wtedy
zawsze mamy d-1 = wkd[j] >/ 1 (gdzie
p = prime[j]), czyli d >/ 2. Podobnie
jest przy wyborze liczby pierwszej.
Wtedy d := pDim > 1 (bez sensu byłoby
mieć pDim=1; a w TWR nie jest to moźliwe,
zawsze pDim > 1; tak naprawdę, to chcemy,
żeby pDim b yło spore).
Pozdrawiam,
Włodek
PS. Czy takimi drobiazgami tylko
zawracam Wam głowę, zabieram czas?
dK
Nie, to tylko moje zboczenie zawodowe ;-)
dK
Wlodzimierz Holsztynski
> Tak, dla wyłączenia jednej wartości to zadziała,
> ale sprawa się komplikuje
> jeśli chcemy wyłączyć nie jedną a kilka wartosci
> W skrajnym przypadku algorytm musi reagować, gdy
> chcemy wyłaczyć wszystkie wartości z przedziału.
Powiedzmy, że chcemy wybrać losowo
wartość x : 0 \< x < d, porzy czym chcemy
ominąć wartości:
0 \< a[0] < a[1] < ... < a[r-1] < d
Oczywiście r \< d. Jeżeli r=d wyminięcie jest
niemożliwe, czyli kod może wyglądać tak:
if(r < d) findRnd();
else noMore();
Przedstawię kod, chyba prosty(?), dla funkcji findRnd().
Powiedzmy, że array a[] jest globalny:
int findRnd (int d, int r) // return the required random integer
{ int i, x;
x = random() % (d-r);
for (i=0; i < r; ++i) x += (x >= a[i]);
return x;
}
Prawdopodobnie powyższe dzieje się w pętli.
Wtedy należy jeszcze wtrynić x = findRnd()
w array a[] (jak po polsku iinformatycy mówią
"insert"m bo chyba nie wepchnąć, ani nie
wcisnąć, ani na pewno nie wtrynić :-) --
może włączyć?
Można skrócić pętle w funkcji findRnd().
Zakładam, że a[] ma wymiar na zapas.
int findRnd (int d, int r)
{ int i, x;
a[r] = d;
x = random() % (d-r);
for (i=0; x >= a[i]; ++i) ++x;
return x;
}
Pętlę przeciętnie skraca się o połowę,
przy czym rachunki nie są bardziej
złożone. Dla sporych parametrów
0 < r < d powinno się zyskać około
połowy czasu.
Przy naprawdę sporych parametrach 0 < r < d
opłaca się zrobić "binary search" czyli
dzielić na pół, na pół, na ... z grubsza tak:
należy porównać x = random() % (d-r)
z wyrazami ciągu a[] jak następuje:
porównaj y = x + r/2 oraz a[r/2];
następnie, w zależności od wyniku
porównania, porównaj albo y = x + r/4
oraz a[r/4], albo y + (3*r)/4 oraz a[3*r/4];
itd.
Pozdrawiam,
Włodek
Mirek
> Przy naprawdę sporych parametrach 0 < r < d
> opłaca się zrobić "binary search" czyli
> dzielić na pół, na pół,
Jeżeli tablica "a" byłaby przez jakiś(???) czas
statyczna, to najszybsze byłyby z góry policzone
tablice:
przyrostowa -> return x+b[x]
lub wręcz
translacyjna -> return c[x]