Algorytm wariacji bez powtorzen.

[Atryo]

Witam wszystkich.

Mam do napisania niezbyt przyjemny projekt (tak, tak - uczelnia)
wykorzystujący rekurencyjny algorytm generujacy wariacje bez powtorzen. Mimo
poszukiwan na sieci nie wiem od ktorej strony to ugryzc. Jesli ktos bylby mi
w stanie pomoc, chocby tylko wskazowka gdzie szukac, to bede bardzo
wdzieczny.

Atryo.

P.S Jsli tafilem na zla grupe, to na jaka sie zglosic?

[Rymasz]

Post by Atryo
Jesli ktos bylby mi
w stanie pomoc, chocby tylko wskazowka gdzie szukac, to bede bardzo
wdzieczny.
Atryo.
P.S Jsli tafilem na zla grupe, to na jaka sie zglosic?

Moze na czyms typu pl.sci.matematyka pomoga :)
Samo przypomnienie sobie czym jest wariacja bez powtorzen i proba
implementacji nie wystarczy? To jakis bardzo wyszukany problem?

WBR Rymasz

[Atryo]

Post by Rymasz
Moze na czyms typu pl.sci.matematyka pomoga :)

Dzieki. Pomecze ich.

Post by Rymasz
Samo przypomnienie sobie czym jest wariacja bez powtorzen i proba
implementacji nie wystarczy? To jakis bardzo wyszukany problem?

Wstepnie zaznacze, że w Javie zbyt bystry jezscze nie jestem (pracuje nad
tym :-) ). Program do napisania to deszysfrator metoda 'brute force'.
Dostaje zdanie w posacie serii par cyfr (np. 42 25 31 12 25 19...). Kazdej
liczbie odpowiada jakas litera. Napisac program, ktor wypisze do pliku txt
wszystkie mozliwe kombinacje literowe.

- moj plan wyglada tak: sprawdzam ile roznych znakow jest w zdaniu.
- wybieram wariacje ze zbioru od a do z i wstawiam w odpowiednie miejsca (po
drodze planuje uzyc dwoch tablic, ale to chyba nieistotny dla sprawy detal).
- spisuje efekt do pliku

Pierwszy problem na jaki napotkalem to ten, ze ilosc wariacji
osmioelementowych w dwudziestodwuelementowym zbiorze jest ogromna (wynik
wykracza poza zmienna typu long). Wiem, ze ominac to da sie rekurencja, jak
na razie jednak stworzenie takiego algorytmu jest ponad moje zdolnosci, stad
pytanie.

Post by Rymasz
WBR Rymasz

Pozdrawiam
Atryo

[Rymasz]

Post by Atryo
Wstepnie zaznacze, że w Javie zbyt bystry jezscze nie jestem (pracuje nad
tym :-) ).

To chyba nie ma znaczenia tutaj :)

Post by Atryo
Dostaje zdanie w posacie serii par cyfr (np. 42 25 31 12 25 19...). Kazdej
liczbie odpowiada jakas litera. Napisac program, ktor wypisze do pliku txt
wszystkie mozliwe kombinacje literowe.

A czy pary np. 53 i 22 moga byc ta sama litera?

Post by Atryo
Pierwszy problem na jaki napotkalem to ten, ze ilosc wariacji
osmioelementowych w dwudziestodwuelementowym zbiorze jest ogromna (wynik
wykracza poza zmienna typu long). Wiem, ze ominac to da sie rekurencja, jak

Moze nie jest ona konieczna. Pozno dosc i spac juz ide. Mysli mi sie
niejasno, ale
moze tak?

Wektor takiej dlugosci ile jest roznych znakow w zdaniu. (kazde jego pole to
inna litera odpowiadajaca innej parze). Ustalamy na poczatku np. na
a,a,a,a,a,a,a,a albo a,b,c,d,e,f,g jak kazda para to inna litera.
Podstawiamy pod dana pare nasza aktualna jej wartosc i zwiekszamy skrajna
prawa litere o jedna w gore. Jak przekroczymy "zet" to na wartosc poczatkowa
dla danego miejsca i powiekszamy z lewej (+sytuacja "z" z lewej)
(+sprawdzanie czy nie ma jesli nie chcemy dwoch takich samych liter, na
razie przemilczymy ta sprawe)

Wlasnie zdalem sobie sprawe, ze moze to nie objac calej wariacji (bo bez
powtorzen
ma to szanse byc dla opcji, ze kazda para to inna litera) ale moze bedzie
choc troche
pomocne, pod warunkiem, ze nie pisze tu banalow :) Kwestia przemyslenia tej
wariacji
w tej wizji i rekurencja potrzebna moze nie bedzie :)

WBR Rymasz

[Rymasz]

Jeszcze mnie tak naszlo: wariancja chyba? :)

WBR Rymasz

[Atryo]

Post by Rymasz
Jeszcze mnie tak naszlo: wariancja chyba? :)

Nie, na pewno nie :-). Tak ogolnie, bez zbednych definicji: wariacja jest w
kombinatoryce, a wariancja wystepuje w statystyce, rachunku
prawdopodobieństwa i innych strasznych miejscach.

Post by Rymasz
WBR Rymasz

Atryo

P.S. Pomysl z drugiego posta wlasnie analizuje. I dokoncze, jak sie wyspie.
Dzieki serdeczne, bo chyba cos z tego bedzie :-).

[Wojtek]

Post by Atryo
Witam wszystkich.
Mam do napisania niezbyt przyjemny projekt (tak, tak - uczelnia)
wykorzystujący rekurencyjny algorytm generujacy wariacje bez powtorzen. Mimo
poszukiwan na sieci nie wiem od ktorej strony to ugryzc. Jesli ktos bylby mi
w stanie pomoc, chocby tylko wskazowka gdzie szukac, to bede bardzo
wdzieczny.

tu jest zrodelko... w C ;)

http://www.de.ioccc.org/1989/vanb.c

a tak powazniej (bo to raczej nie bedzie satysfakcjonujaca pomoca :D chociaz
dziala wysmienicie) to poszukaj w googlach o _subset_ problem (chyba ze nie
zrozumialem dokladnie o co chodzilo) - pisalem kiedys na zaliczenie cos
podobnego, w C - algorytm wzialem z jakiejs ksiazki polskiego autora - jest
niemal pelen kod w Pascalu, wystarczy przejzec i zrozumiec o co chodzi :) -
brakuje tylko funkcji wypisujacej elementy, ale jak juz sie zrozumie to jest
to 5 minut roboty, calosc zajmuje ok. 80 linii (z tego co pamietam jak
przepisalem to na C)

Pozdrawiam
Wojtek Chatkowski