Statystyka multilotka - algorytm

Zadanie:
Program co sprawdz w ostatnich 5000 losowaniach ilosc wypadniecia kazdej mozliwej kombinacji 10.

Moj algorytm jest nastepujacy:
Wczytaj 5000 wynikow
Dla n-tego losowania stworz kombinacje
Sprawdz czy wystapila w innych losowaniach
I tak miliard razy :)

Pytanie moje jest czy da się to jakoś przyspieszyć gdyż czas wykonywania wynosi u mnie 3min*5000=10dni :/

Troche matmy:
-mozliwe losowanie to kombinacja bez powtorzen
-dla 20 wylosowanych kulek, kobinacji 10 jest (20 nad 10) czyli ok. 184000.
-wiec na czas wplywa ilosc obliczen dla kazdego z 184000 sprawdz w 5000 i tak 5000 razy czyli.. 464 miliardy operacji ;)

Jeżeli macie jakieś ciekawsze inne podejście do problemu to było by super.
Dzieki.

Oczywiście że można szybciej. Twoje rozwiazanie daje O(n^2) a da się to zrobić liniowo. Jak?
Tworzysz sobie mapę/tablicę hashującą która odwzorowuje
kombinacja->int
I robisz zwykłe zliczanie.

mapa[nastepnaKombinacja(wynikLosowania)]++;

na koniec w mapie masz ilość wypadnięć każdej kombinacji.

Mógłbyś trochę rozwinąć to co masz na myśli ?

Której części nie zrozumiałeś?

1. Nie wiesz co to jest mapa/tablica hashująca?
2. Nie wiesz co znaczy odwzorowywać?
3. Nie wiesz na czym polega zliczanie?
4. Nie wiesz co znaczy O(n) i O(n^2)?
5. Nie rozumiesz idei przedstawionego przeze mnie algorytmu?

Z tego co rozumiem Twój algorytm, to polega to na tym że w mapie dla każdej kombinacji, wpisujemy tam ile razy nastąpiło powtórzenie. Czyli zamiast 5000 razy przechodzić przez 5000 wyników - przejdziemy tylko raz przez 5000 tysięcy. Czy się mijam z prawdą :) ?

Nie mijasz się z prawdą, chodzi dokładnie o to.
Bo ty chciałeś przechodzić znacznie wiecej niż 5000 razy po 5000 razy. Ty przechodziłeś (20 po 10) kombinacji razy 5000 przez (20 po 10)*5000 (bo robiłeś porównanie każdy z każdym).
Mój algorytm wynika się więc (20 po 10)*5000 razy szybciej.

1. Czy mówiąc dla każdej kombinacji mówimy tu o (80 po 10) ?
2. Dla przykładu (6 kulek, losujemy 4, skreślamy 2)
   Wyniki 3 losowań:
   1,2,3,4
   1,3,4,5l
   2,3,5,6

To moj algorytm sprawdzal by wystapienie:
wkl=w każdym losowaniu
(1,2)wkl(1,3)wkl(1,4)wkl(2,3)wkl(2,4)wkl(3,4)wkl
(1,3)wkl,(1,4)wkl,(1,5)wkl,(3,4)wkl,(3,5)wk,(4,5)wkl
(2,3)wkl,(2,5)wkl,(2,6)wkl,(3,5)wkl,(3,6)wkl,(5,6)wkl

A Twoja wersja:
(1,2)(1,3),(1,4),(1,5),(1,6),(2,3),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6),(4,5),(4,6),(5,6) w pierwszym, drugim, trzecim ?

1. Nie. Tzn może i stablicowanie tych wszystkich kombinacji byłoby dobrym pomysłem, ale to by trzeba było policzyć a mnie się nie chce.
2. Mój algorytm zrobiłby tak:
   kombinacje[(1,2)]++;
   kombinacje[(1,3)]++;
   itd dla pierwszego losowanie
   i analogicznie dla drugiego i dla trzeciego.

W ten sposób jeśli mamy 1000 losowań to dla ciebie sprawdzenie ile razy (1,2) wystąpiło wymaga wyliczenia wszystkich (!) kombinacji z każdego losowania i sprawdzenia czy któraś z tych kombinacji == (1,2). To jest 1000ilość kombinacji. I to tylko dla sprawdzenia tego raz! Jeśli taka kombinacja wystąpiła tylko raz to wykonasz 1000ilośc kombinacji porównań. Mój algorytm wykona tylko jedną operację.
Jeśli taka kombinacja wystąpiła w każdym losowaniu to twój algorytm wykona 1000ilość kombinacji1000 porównań. Mój algorytm wykona tylko 1000 operacji.

A jaki to ma związek z inżynierią oprogramowania?

Taki że nie ma działu Algorytmy :P

To nadal nie jest związek. Idźcie sobie do nietuzinkowych albo na Berdyczów. :P

Bo w sumie w nietuzinkowych generalnie siedzą algorytmy. Więc to nie tyle nie ma działu, co już istniejący się źle nazywa.

http://4programmers.net/Forum/Coyote/167255-Brak_mi_tu_dzialu_ALGORYTMY
@somekind: ani ja ani autor nie jesteśmy moderatorami wiec nigdzie "iść" nie możemy :P