Fórumok
Nem vágom az értelmes elnevezését a problémának, de:
- van 1 csomó szatyrom, amiben amúgy egyforma színes golyók vannak, változó számban, de 1 zacskóban bármely színből max. 1,
- Legyen mondjuk a 3,
- Melyik az a 3 (vagy valamennyi) szín, ami legtöbbször szerepel együtt a szatyrokban?
Olyasmi, mintha azt kérdezném, melyik az a 2-3-4 lottószám, melyeket legtöbbször sorsoltak ki együtt.
Illetve valami graphDB-vel lehet-e ilyesmi feladatot egyszerűen megoldani
Hozzászólások
Az optimális algoritmust keresed vagy megelégszel egy helyes megoldással? Kódolni akarsz vagy valami kész megoldást használni?
Egy kombinatorikai feladat is lehetne, ha tudnánk a színes golyók fajtáinak és a szatyroknak a konkrét számát.
Ez az egyik lepes egy kulso tombbe letarolni, hogy milyen szinek leteznek, majd minden egyes zsakot binarisan felirni, higy az adott szin letzik vagy sem a zsakban.
Ez utan legeneralni a lehetseges variaciokat, mondjuk egy tombbe ahol a kulcs a variacio binarisan az ertek meg az egyezesek szama.
Innen csak azt kell mar megkeresni melyik a legnagyobb.
Tudjuk. Ma 521 szatyor van és 698 különböző színű golyó. Holnap nem tudom, de egyik se lesz kevesebb.
Akkor a módszerem megbukott. :) (persze, ha van idő...)
Ha csak 3 féle golyót keresünk, akkor 56.434.696 féle lehetőség van amit 521x kell lefuttatni.
Azért nem ártana tudni a szatyor méretét. Minden szín előfordulhat egyszerre egy szatyorban?
Ha igen, akkor esetleg dinamikus programozással lehet valamit kezdeni, hogy az elő nem forduló - vagy kis számban szereplő - színeket, színkombinációkat elvessük, és csak a maradékkal számoljunk tovább.
Vagy be lehet vetni az adatbányászat nehézfegyvereit: 37_Szathmary.pdf (bme.hu)
AL
eleve nincs rendesen definiálva mi a feladat. Szatyor meg zacskó,meg legyen 3, meg más zagyvaságok. Szóval ebből még bármi is lehet :D
Meg a vesszők sem biztos, hogy ott vannak vagy nincsenek, ahol kellene. Bár lehet nem egyforma színes (egy színű), hanem különböző színű golyókra gondolta a szerző és a szatyor és a zacskó ugyanaz.
Ha statisztikailag / kombinatorikailag akarja az esélyeket megtalálni, akkor valsz az lesz a vége, hogy nyereménykategórián belül azonos az esélye bármelyik számsor kihúzásának a lottón. Konkrét esetben max időszakos kilengések lehetnek, de minél több a minta, annál egyenletesebb.
Építesz egy indexet, ami megmondja, melyik szín melyik szatyrokban szerepel. Pl. piros=>{0,1}, zöld=>{1,2,3}, kék=>{0,2,3}, sárga=>{1,4}. Aztán a színekből generálod az összes 3-elemű kombinációt: {piros,zöld,kék}, {piros,zöld,sárga}, {piros,kék,sárga}, {zöld,kék,sárga}. Az összes ilyenre megnézed az indexből a metszetet. Ugyanebben a sorrendben kijön, hogy {}, {1}, {}, {}. Tehát a {piros,zöld,sárga} a nyerő, mert azok egy szatyorban szerepelnek együtt, a többi egyben sem.
Dupla komment. Mikor az előző beküldtem, bejött az oldal a kommentem nélkül. Frissítettem, még mindig nem volt ott. Gondoltam, elveszett. Beküldtem megint. Akkor meg hirtelen megjelent mindkét beküldés.
egy anonimizalt pelda adatbazist nem tudsz idedobi, amivel szorakozhatunk? :)
“Any book worth banning is a book worth reading.”
Hát nem annyira, de asszem ez 1 elég általános probléma, nem a konkrét megoldás az érdekes
bar nincsen közöm a feladathoz, de szórakoztam vele én is:
https://drive.google.com/drive/folders/1wUZpd2fZnO_7tcQLzIM-NjHnOwrplmO…
a fájlok "szerkezete": első sor: színek száma dobozok száma (az a fájlnévben is benne van)
a további sorokban a dobozok tartalma szerepel (1 sor 1 doboz), a színek pozitív egészek
a fájl nevében az mx utáni szám a brute force módszerrel talált maximum. (k legyen mondjuk 3-ra :-))
Bár a Python-t divat itt utálni, de Python3-ban például így nézne ki.
AL
# képezzük az összes háromelemű kombinációt
56434696*3 byte = minimum 161 gigabyte-os tömb :)
Lehet, de itt most csak a szatyor tartalma számít a kombinációk generálásakor. Ha ezerszámra vannak benne elemek, akkor már kezd necces lenni.
A kiírásban még csak lottóhúzás szerepelt, nem pedig az, hogy Jókai regényeinek mondataiban mely három szó szerepelt együtt legtöbbször.
Az asszociatív tömb esetünkben csak azokat a kulcsokat (hármasokat) fogja letárolni, melyek valójában is szerepeltek.
AL
Nem kell eltárolni a kombinációkat, csak egyenként legenerálni.
És ha csak a maximumot keresi, akkor elég az aktuális maximumot eltárolni (a hozzá tartozó kombinációval).
ezdejo, itertools :)
:-)
AL
a lottoszamosra van megoldasom.
pascalos lesz, mert arra a nyelvre nagyjabol emlexem.
elso lepesben csinalsz egy x dimenzioju tombot, ( ha ket szam egyuttallasa erdekel, akkor x=2 , ha harom, akkor x=3 , ha 4, akkor x=4 )
tegyukfel a 3 egyuttsorsolt szam erdekel.
tehat
kisorsolt_kombo array[ 1..90, 1..90, 1..90 ];
kinullazod.
ezutan elkezded feldolgozni a sorsolasokat.
ez ugye sorsolasonkent egy egydimenzios tomb,
sorsolas array[1..5];
minden egyes sorsolas beolvasasa utan sorba kell rendezni a sorsolas tombot ( lehet anelkul is, de akkor kesobb tobb melo van. )
majd az ebben levo szamokat indexnek hasznalva noveled a kisorsolt_kombo megfelelo cellajat. vagyis :
inc( kisorsolt_kombo[ sorsolas[1], sorsolas[2], sorsolas[3] ] );
inc( kisorsolt_kombo[ sorsolas[1], sorsolas[2], sorsolas[4] ] );
inc( kisorsolt_kombo[ sorsolas[1], sorsolas[2], sorsolas[5] ] );
inc( kisorsolt_kombo[ sorsolas[1], sorsolas[3], sorsolas[4] ] );
inc( kisorsolt_kombo[ sorsolas[1], sorsolas[3], sorsolas[5] ] );
inc( kisorsolt_kombo[ sorsolas[1], sorsolas[4], sorsolas[5] ] );
inc( kisorsolt_kombo[ sorsolas[2], sorsolas[3], sorsolas[4] ] );
inc( kisorsolt_kombo[ sorsolas[2], sorsolas[3], sorsolas[5] ] );
inc( kisorsolt_kombo[ sorsolas[2], sorsolas[4], sorsolas[5] ] );
inc( kisorsolt_kombo[ sorsolas[3], sorsolas[4], sorsolas[5] ] );
ha vegigertel a sorsolasok feldolgozasan, akkor mar csak azt kell kinyomozni, a kisorsolt_kombo tombben hol van a legnagyobb szam, azt a kombit huztak a legtobbszor.
HUP te Zsiga !
+1. Ugyanaz az elv, mint az előbbi Python programban; csak ott nem kell szószátyárnak lenni.
Lássuk az ötöslottó leggyakoribb hármasait! Megint Python3, de ilyenkor már nem igazán illik megbízni a beépített véletlenszámgenerátorban, nagyon egyenletessé válik a valószínűség.
Az előbb elvárt 90x90x90=729.000 tárhely helyett csak 67.514-et használt fel az előbbi program. (igaz nem direkt elérés, hanem keresőfát épít a kulcsok alapján)
AL
evvan, sajnos 20+ eve nem tanultam uj programnyelvet, ezert ily modern dolgokhoz nemszakertek.
a memoriaigeny valos, de a mai pckkel már talan vallalhato. nyilvan a 600 szatyor 500 szin az ebben a formaban már szuperszámitógépet kiván :D , majd a kerdezo optimalizal, dolgozzon mar o is :D
HUP te Zsiga !
Minden szatyrot leképezel egy bináris számként (~bitarray):
Ezután fogod a lehetséges n-tagú kombinációkat (szintén bináris számként) és egy sima bitwise and-del összehasonlítod minden szatyorral. Megkeresed/eltárolod a maximumot, és kész :-)
Ez 698 szín, 521 szatyor és 3 tag esetén - ahogy feljebb már valaki írta - 56M x 521 összehasonlítás, ami nem kevés, de nem feltétlenül lassú, mivel alacsony szintű műveletekről van szó. Persze érdemes hozzá olyan programnyelvet választani, ami korlátlan méretű integereket kezel. Memóriaigénye elvileg minimális: 521 db 698 bites számot kell eltárolni, plusz az aktuális maximumot és a hozzá tartozó kombinációt.
@ant: bakker, nem publikáltam elég gyorsan az ötletet, de hasonlóan gondolkodtam ;)
Viszont megfejeltem kicsit és így az állapottér nagyrésze kidobásra kerül = sokkal kevesebb összehasonlításból megvan.
Minden színt leképezek egy bináris számként, az 1-esek azt jelölik melyik vödörben van az a szín.
És most jön a trükk: mivel két szám ÉS kapcsolata maximum annyi 1-est tartalmaz, mint amennyit a kevesebb 1-est tartalmazó szám, így berendeztem a színeket a Hamming súlyuk szerint (mennyi 1-es van bennük), és ha a következő választandó nem stimmel, már dobom is el az ágat.
(szín1 ÉS szín2 ÉS szín3) Hamming súlya megmondja hogy ez a színhármas hány vödörben van benne.
Kód:
Eredmény:
A kiírás első száma a szín azonosítója, a második, hogy az a szín hány vödörben van benne, utána a vödrök térképe
A Helper-ben lévő egyesek megmutatják melyik oszlopot nézd, hogy mely vödrökben volt benne
Szerintem ilyen méretek mellett közelítő algoritmusokban kellene gondolkozni. Bár ezek szerint általános esetben nem könnyen közelíthető: https://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf
Amit ideraktam az pontos eredményt ad O (n*m) komplexitás mellett ahol N a vödrök+színek száma, M pedig a keresett csoport mérete. A fenti számokra (521,698) 1s alatt végez a játszótér generálással együtt. A notimban 8GB mem és egy 4 éves i5 van.
Nem teljesen értem az algodat miért helyes, az hogy már kiválasztottál kettőt mondjuk és a következővel nulla közös részük van nem jelenti azt hogy az azutániakat nem kell vizsgálni.
Pl. 11000 11000 00110 10000
Erre nem ad jó megoldást, persze lehet félreértettem valamit.
de jó szemed van, igazad van. Az implementáció kicsit kócos lett, a koncepció még nem tűnik rossznak. Ha előbb nem, hétvégén igyekszem javítani, most már nagyon kíváncsi vagyok :)
Igen, gondolatban én is ilyesmi komplexitásra jutottam
Csinálok belőle egy feladatot a codewars-on, és ott majd kioptimalizálják ;-)
Hú de nem értik itt emberek szerintem a dolgot, de akkor lelepleznélek, egyetlen szó kicserélésével (na jó, legyen kettő):
És így már meg is van a megoldás, a neve apriori algoritmus: https://analyticslog.com/blog/2020/8/13/apriori-algorithm-items-frequently-bought-together-a-basic-explanation-of-how-it-works
Have fun.
Az apriori algoritmus nem erről szól. Hasonló, de nem ez.
"The apriori algorithm runs this at scale across all the product combinations to maximize the Lift metric based on your chosen level of minimum Support, Confidence."
Az apriori algoritmus azt mondja: ha van egy N küszöbértéked, akkor megmondja, hogy mik azok a lehetőségek, amik legalább ilyen gyakorisággal szerepelnek az adathalmazban. Azaz kell neki ez a küszöbérték. Nem mondja meg, hogy mi a leggyakoribb n-es, csak azt, hogy melyek az x gyakoriságnál gyakoribb n-esek.
Azaz ezt az algoritmust egyre nagyobb küszöbértékekkel kell futtatnod, azaz futásidőben ugyanott leszel - az algoritmus csak a belső ciklust valósítja meg, a külsőt nem.