Pseudolosowe przyporządkowanie wartości zmiennym

[Wojtek]

Potrzebuję w sposób losowy przyporządkować ośmiu określonym zmiennym (np. a,b,c,d,e,f,g,h) wartości z przedziału <1 - 8> z tym ,że wartości nie mogą się dublować (funkcja różnowartościowa).

Dość łatwo było opracować sposób przyporządkowywania w sposób pseudolosowy każdej zmiennej liczb z zakresu 1-8. Jednak sposób ,który opracowałem nie uwzględnia warunku różnowartościowości.

A więc na bazie mojego dotychczasowego algorytmu program "wylosował" następijące wartości dla zmiennych (przykładowo) :

a = 3

b = 3

c = 1

d = 2

e = 3

f = 5

g = 6

h = 5

Jak widać wartości się dublują. Wymyśliłem że jeśli ktoś ma nieograniczoną pamięć w uC to może sobie rozwiązać ten problem tak:

If a = b Then incr b
If a = c Then incr c
If a = d Then incr d
If a = e Then incr e
If a = f Then incr f
If a = g Then incr g
If a = h Then incr h

'Tutaj by trzeba było powtórzyć wszystko jeszcze 7 razy (żeby było spr. dla każdej zmiennej)

'a potem jeszcze sprawdzić trzeba czy żadna zmienna nie wyszła poza "granice":
If a = 9 Then a = 1
If b = 9 Then b = 1
If c = 9 Then c = 1
If d= 9 Then d = 1
If e = 9 Then e = 1
If f = 9 Then f = 1
If g = 9 Then g = 1
If h = 9 Then h = 1

W sumie uzyskałem 64 linii kodu!!! a to przecież tylko namiastka programu który chcę władować do swojego uC (niestety mój uC ma ograniczoną pamięć - a co gorsza mój kompilator mnie jeszcze ogranicza - wersja DEMO 😕 )

I tu pytanie do was - czy przychodzi wam do głowy jakiś prostszy sposób na elminacje tych powtórzeń wartości?

.

[marek1707]

Ja bym zaczął od zbioru uporządkowanego, tzn:

tablica[0]=1; tablica[1]=2; ... ; tablica[7]=8;

co już na wstępie załatwia sprawę powtórzeń a potem go permutował, mieszając np. przez losowe zamiany między sobą dwóch składników, np:

for(n=0; n

{

zamien(tablica, n%8, rnd()%8);

}

Liczbę permutacji możesz dobrać jak chcesz. Ta prosta pętla używa funkcji zamien, która dostaje wskaznik na tablicę oraz dwa indeksy jej elementów - nie napisałem tutaj ale wydaje się trywialna. Pierwszy indeks będzie zwiększał się w cyklu 0..7 a drugi będzie liczbą losową (no dobra, pseudolosową) z zakresu 0..7. No i to trochę tablicę wytarmosi. Zamiast operatorów modulo, w przypadku rozmiaru 8 możesz oczywiście użyć wybierania trzech najmłodszych bitów: "n & 7" i "rnd() & 7"

Oczywiście pozostaje problem losowości bądź pseudolosowości takiej operacji ale sprowadza się to do odpowiedniego "zasiania" funkcji rnd().

Algorytm nie wymaga pamięci za to zużyje każdy czas, jaki mu dasz 🙂

[rezolut]

T_odczyt(1) = Rnd(9)
Incr T_odczyt(1)
For I = 2 To 8
  A = 1
  While A = 1

  T_odczyt(i) = Rnd(9)
  Incr T_odczyt(i)
  K = I - 1
  A = 0
  For J = 1 To K
     If T_odczyt(j) = T_odczyt(i) Then A = 1
  Next J

  Wend

Next I

Ile to zajmuje pamięci?

[Wojtek]

Dzięki ,ale szczerzę mówiąc to nie rozumiem tego kodu co mi dałeś. Mógłbyś napisać komentarze do tego programu zebu ułatwić mi analizę?

1)To Tablica[0] itd to zmienne bajtowe czy tablicowe? Czy może zerowa komórka zmiennej tablicowej - ale o ile wiem w tablicach liczy się od 1?

2)Napisałeś

for(n=0; n

Co oznaczają średniki, n i n++?

3)Co oznacza to

"zamien(tablica, n%8, rnd()%8); "

"zamien" to przecież nie nazwa polecenia?Nie wydaje mi się że w BASCOMIE polecenie jest po Polsku 😮 ?

W miejscu gdzie napisałeś tablica wpisuje nazwę zmiennej tablicowej?

Kolejne miejsca po przecinkach to adresy do 2 bajtów w tej tablicy, które mają ulec permutacji?

Co oznacza to { i to } ? Jeśli jest to jakoś związane z pętlą For...next to wybacz ale nie znam tej pętli.

4) I ostatnie najważniejsze: Jak się w końcu nazywa procedura związana z permutacją w bascomie?

RND odpada - użyję czegoś innego ale z tym sobie już sam poradzę.

[ Dodano: 24-02-2012, 23:35 ]

No chyba żebym zrobił podprogram "zamien"

Coś takiego:

Chcę zamienić wartości zmiennych a i b ze sobą

a = pomoc
a = b
b = pomoc

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[rezolut]

Dzięki ,ale szczerzę mówiąc to nie rozumiem tego kodu co mi dałeś. Mógłbyś napisać komentarze do tego programu zebu ułatwić mi analizę?

Masz 2 pętle (pętle w pętli). Pętla I i pętla J

Pętla I przypisuje kolejnemu elementowi tablicy zmienną losową

Pętla J sprawdza wszystkie poprzenie elementy, czy któryś z nich nie jest równy właśnie wygenerowanej liczbie. Jeśli tak WEND jest przetwarzane ponownie. Jeśli nie, następuje kolejna iteracja pętli I

W wyniku otrzymujesz 8 różnych elementów pseudolosowych.

Errata: powinno być rnd(8) zamiast rnd(9)

[Wojcik98]

Wojtek

Kod użytkownika marek1707 nie jest napisany w Bascomie tylko w C

[marek1707]

Ech, zdanie "nie rozumiem tego kodu co mi dałeś" jest raczej do mnie. Kod jest napisany w C, zamien() to nazwa funkcji, indeksy tablic liczymy od zera i w ogóle...

Na BASCOM Ci tego nie przepiszę ale czuję, że chyba odgadłeś sens pomysłu:

- Robię tablicę 8-elementową.

- Wypełniam ją liczbami 1..8.

- Dowolną ilość razy powtarzam (w pętli for jest to LICZBA_PERMUTACJI) wykonanie funkcji "zamien" która zamienia miejscami wartości dwóch wskazanych elementów tablicy "tablica". Indeks pierwszego elementu zmienia się jak licznik w cyklu 0 → 7 a drugi jest liczbą losową z zakresu 0..7.

Taki algorytm nie wprowadza nowych liczb do tablicy więc nie ma niebezpieczeństwa, że pojawią się choćby dwie takie same. Nie oczekuje też na wylosowanie pewnej specjalnej liczby, pasującej do jakiegoś klucza - jak w pomyśle rezoluta. Przy np. 1000 pozycji w ten sposób moglibyśmy czekać na wypełnienie tablicy bardzo dlugo.. Tutaj każda liczba jest dobra.

Chcę jeszcze tylko zwrócić uwagę, że wbudowany generator rnd() jest dobry i spełnia testy statystyczne założone przez jego projektantów tylko pod warunkiem, że bierzemy w wyniku całą liczbę wyjściową. Poszczególne jej bity (jak w obu powyższych algorytmach) mogą mieć wręcz fatalne własności "losowe". Jeżeli więc robisz maszynę do losowania grubych pieniędzy, możesz mieć kłopoty ale jeśli jest to amatorski projekt, takie uproszczenie ujdzie Ci na sucho 🙂

[Wojtek]

A co sądzicie o zamianie wartości zmiennych w taki sposób?

If Pind < 255 OR Pina < 15 Then 'jeżeli zostanie naciśnięty któryś z przycisków. (Przyciski będą zwierłay
                               'do masy a stan spoczynkowy pinów będzie wynosił Portd = &B11111111 i 
                               'Porta = &Bxxxx1111 - tu gdzie x to i tak nie ważne)
Incr Pomoc                       ' tu z wielką częstotliwością będzie zmieniać się wartość zmiennej 
If Pomoc = 7 Then Pomoc = 0      ' pomoc w przedziale od 0 do 6
Else                             'gdy w końcu przycisk zostanie zwolniony
If Blok = 0 Then                 'tutaj taki bit pomocniczy( gdy już nie będe chciał aby się zmienne
                                'permutowały to ustawie go na 1 i w ten sposób to zablokuje)
Select case pomoc                'w zależności od wartości zmiennej "pomoc" zostają zamienione
case 0:                          ' wartości poszczególnych zmiennych
a = pomoc : a = b : b = pomoc    
Case 1:
a = pomoc : a = c : c = pomoc
Case 2:
a = pomoc : a = d : d = pomoc
Case 3:
a = pomoc : a = e : e = pomoc
Case 4:
a = pomoc : a = f : f = pomoc
Case 5:
a = pomoc : a = g : g = pomoc
Case 6:
a = pomoc : a = h : h = pomoc
End If
End Select                       'koniec
End If

Przyciski będą naciskane wiele razy gdyż użytkownik będzie musiał w urządzeniu wprowadzić pewne dane początkowe więc wszystko powinno się dobrze pomieszać 😉 . I "losowość" (sorry za te cudzysłowia ale jestem deterministom 😅 ) będzie wynikała z długości naciskania tych przycisków a nie z tego RND.

[marek1707]

No pewnie, przyciski + szybki licznik to całkiem dobry generator rnd. Przy pewnych założeniach - losowy bez cudzysłowów. Tylko dlaczego tak uparłeś się na te zmienne skalarne? Czy w BASCOMie nie ma tablic? Chyba byłoby dużo prościej operować na indeksach i napisać jedną funkcję zamiany niż sadzić takiego switch'a, przepraszam select'a.

No i trzeba by się zastanowić, jakie znaczenie statystyczne ma tak "niesymetryczne" używanie zmiennej "a". Przy dużej liczbie prób pewnie to się wyrównuje ale przy małej może to być poważne obciążenie.

[Wojtek]

Sorry ale wole rozumieć to co mam w programie bo potem jak będą jakieś problemy to nie będę wiedział za co się zabrać.

Ale reasumując ten ostatni program co wysłałem (mimo że jest bardziej prymitywny i pewnie nieco więcej miejsca zajmie) to będzie działać?

[Ksawery]

Ja napisałbym to tak:

Tab(1) = Rnd(8) + 1
For I = 2 To 8
 Do
   A = Rnd(8) + 1
 Loop Until A <> Tab(I - 1)
 Tab(i) = A
Next I

Wcześniej musisz zdefiniować tablicę ośmioelementową oraz zmienne pomocnicze.

[rezolut]

No i źle. Bo warunek until sprawdza tylko czy losowana liczba nie jest taka jak element poprzedni. Może się więc zdarzyć 1,2,1,2,1,2.....

[Ksawery]

Program przetestowałem w praktyce i nigdy liczby się nie powtórzyły. Program losujący liczby i wypisujący je na LCD:

$regfile = "m8def.dat"
$crystal = 1000000
Config Lcd = 16 * 2
Config Lcdpin = Pin , Db4 = Portc.3 , Db5 = Portc.2 , Db6 = Portc.1 , Db7 = Portc.0 , E = Portc.4 , Rs = Portc.5
Cursor Off
Cls

Dim Tab(8) As Byte
Dim A As Byte
Dim I As Byte
Dim ___rseed As Word
___rseed = 8956

Do
 Tab(1) = Rnd(8) + 1
 For I = 2 To 8
   Do
     A = Rnd(8) + 1
   Loop Until A <> Tab(i - 1)
   Tab(i) = A
 Next I
 Lcd Tab(1) ; ":" ; Tab(2) ; ":" ; Tab(3) ; ":" ; Tab(4) ; ":" ; Tab(5) ; ":" ; Tab(6) ; ":" ; Tab(7) ; ":" ; Tab(8)
 Wait 5
 Cls
 Tab(1) = 32 * Tab(2)
 Tab(2) = 13 * Tab(3)
   ___rseed = Tab(1) + Tab(2)
Loop
End

Tak z ciekawości wgraj go sobie i jeśli coś się powtórzy to napisz.

[BlackJack]

Tzn. TAK. Aby algorytm miał być losowy, to trzeba by użyć jakieś losowej zmiennej, np. z czujnika temperatury, światła, czy jakiegokolwiek źródła dającego losową wartość analogową, lub cyfrową.

Każdy inny algorytm będzie powtarzalny, ponieważ metodami matematycznymi nie da się generować tak naprawdę w pełni losowego przebiegu, ciągu liczb.

[marek1707]

Wojtek: tak, Twój program - o ile rozumiem BASCOM, będzie działał. Żeby losowość była "dobra" musisz wykonać dużo wciśnięć, np. 30 i więcej. Przy kilku, np. po 5 naciśnięciach klawiszka liczby będą słabo rozrzucone. Chyba sam rozumiesz dlaczego. Musi wykonać się dużo zamian. Jeżeli masz w systemie jakiś wyświetlacz, po prostu wypisuj sobie zawartość tych 8 zmiennych i sam zobaczysz, jak się mieszają. Zmienną "a" wykorzystujesz najczęściej ale pozostałe też powinny zostać w końcu "trafione".

K.G. i BlackJack: chyba mówicie o dwóch różnych rzeczach. Pierwszy z was twierdzi, że liczby na LCD nie powtarzają się. I to pewnie prawda - czyli algorytm działa OK. Ale czy po każdym włączeniu/wyzerowaniu procesora liczby ułożone są inaczej czy za każdym razem tak samo? O tym właśnie pisze BlackJack. To jest generator pseudolosowy, którego sekwencja jest zawsze taka sama, jeśli startuje od tego samego "ziarna". Skoro "zasiewasz" swój generator, czyli zmienną __rseed zawsze liczbą 8956, to sekwencja następnie wylosowanych liczb będzie zawsze taka sama. A tego Wojtek prawdopodobnie nie chce. I z tego chociażby powodu jego rozwiązanie z przyciskami jest najlepsze. Oczywiście mógłby np. użyć tylko jednego, pierwszego zmierzonego czasu przycisku do "zasiania" wbudowanego w BASCOM generatora a potem już jechać (którymkolwiek z zaprezentowanych algorytmów) na wywołaniach funkcji rnd ale to już jego wybór.