Hányszor szerepel(nek) a listában

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.

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.

Szerkesztve: 2021. 04. 10., szo – 22:53

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.”

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. 

import itertools as it
c = {}  # dict, azaz asszociatív tömb
s = {'PZKSFN','FRKS','PRK','PZK','ZKP','FSNK','PZ','PKNF'}
for k in s:  # vegyük az egyes szatyrokat
    for i in it.combinations(k,3):  # képezzük az összes háromelemű kombinációt
        c[i]=c.get(i,0)+1           # növeljük a számlálót
m = max(c.values())                 # a legtöbb előfordulás értéke
print([''.join(i) for i in c if c[i]==m])    # hátha valaki az összes megoldásra kíváncsi

AL

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

Szerkesztve: 2021. 04. 11., v – 17:17

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.

import itertools as it
import random as r
c={}
for _ in range(10000):
    k = r.sample(range(1,91),5)
    for i in it.combinations(k,3):
        si=tuple(sorted(i))
        c[si]=c.get(si,0)+1
m = max(c.values())
print(m,[i for i in c if c[i]==m])
# eredmény pl. : 8 [(45, 46, 67)]

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):

    A B C D E F G H ...
1:  1 0 0 0 1 1 0 1 ...
2:  0 1 1 1 0 0 0 1 ...
3:  1 0 0 1 0 1 1 0 ...
4:  ...

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:

    from random import randint

    def allOnes(size):
        return int(pow(2, size + 1)) - 1

    def makerandombits(length):
        res = ""
        for _ in range(length):
            res += str(randint(0, 1))
        return int(res, 2)


    def makefield(nbuckets, ncolors):
        field = []
        for colorindex in range(ncolors):
            bucketmap = makerandombits(nbuckets)
            hammingweight = bin(bucketmap).count('1')
            field.append( (colorindex, bucketmap, hammingweight) )
        return sorted(field, key=lambda x: x[2], reverse=True)


    def finder(groupsize, colors, remainingField, allones):
        if len(colors) == groupsize:
            return colors
        if groupsize == len(colors) + len(remainingField):
            common = allOnes() 
            for color in (colors + remainingField):
                common = common & color[1]
            if common == 0:
                return []
            else:
                return colors + remainingField
        common = allones 
        for color in ( colors + [remainingField[0]] ) :
            common = common & color[1]
        if common == 0:
            return []
        else:
            return finder(groupsize, colors + [ remainingField[0] ], remainingField[1:], allones)
        

    if __name__ == "__main__":
        groupsize = 3 #színcsoport mérete
        ncolors = 5 #hány szín van összesen
        nbuckets = 20 #hány vödör van

        formatter = "0" + str(nbuckets) + "b"
        
        field = makefield(nbuckets, ncolors)
        firstResult = { "colors": [] * groupsize, "nbuckets": 0 }

        for f in field:
            print(format(str(f[0]),'5') + 
                format(str(f[2]),'5') + 
                format(int(f[1]), formatter))
    
        common = allOnes(nbuckets)     
        firstbest = finder(groupsize, [], field, common)
        colorgroup = []
        for color in firstbest:
            common = common & color[1]
            colorgroup.append(color[0])
        if len(colorgroup):
            print("Helper:   " + format(common, formatter))
        else:
            print("No bonus")
        print("First best color group: ")
        print(colorgroup)
        if len(colorgroup): print("Found in " + str( bin(common).count('1')) + " buckets" )

Eredmény:

3    13   10011111010111001101
1    11   01001110000110011111
2    11   11110111000110010010
0    8    11011100000001000011
4    8    00001110101101001000
Helper:   00000110000110000000
First best color group: 
[3, 1, 2]
Found in 4 buckets

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 

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.

Szerkesztve: 2021. 04. 12., h – 11:43

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ő):

 

Nem vágom az értelmes elnevezését a problémának, de:

- van 1 csomó szatyromkosaram, amiben amúgy egyforma színes golyóktermékek vannak, változó számban, de 1 zacskóbankosárban bármely színbőltermékből max. 1,

- Legyen mondjuk a 3,

- Melyik az a 3 (vagy valamennyi) színtermék, ami legtöbbször szerepel együtt a szatyrokban?kosarakban?

Olyasmi, mintha azt kérdezném, melyik az a 2-3-4 lottószám, melyeket legtöbbször sorsoltak ki együtt.

É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.