Forum » Programiranje » Generiranje vseh kombinacij med vhodi in izhodi
Generiranje vseh kombinacij med vhodi in izhodi
i33a ::
Pozdravljeni,
imam sledeč problem:
V funkciji imam podane vhode in izhode podatne kot terke (indeks, vrednost).
Primer:
Vhodi se preslikajo v izhode (vrednosti vhodov in izhodov so enake), vhodi pa se ob preslikavi lahko "razdelijo" tudi na več vhodov.
Za posamezen izhod bi rad ugotovil vse možne kombinacije vhodov in dobil njihove indexe (prve elemente v terki) in to seveda počel kar se da hitro :)
Rešitev za zgornji primer:
Razlaga (output (0,5) )
[0,1,2] => ta output lahko tvori input0 + input1 + input2 (preostali del input2 pa tvori drugi output).
[0,2] => ta output tvorita input0 in input2
Tu ni ideja, da optimiziram kateri inputi najlepše pokrijejo outpute, ampak izračun vseh takih pokritij.
Ima kdo kakšno idejo kako se tega lotim, da bom časovno čimbolj učinkovito?
imam sledeč problem:
V funkciji imam podane vhode in izhode podatne kot terke (indeks, vrednost).
Primer:
inputs: [(0,1), (1,2), (2,4)] outputs: [(0, 5), (1,2)]
Vhodi se preslikajo v izhode (vrednosti vhodov in izhodov so enake), vhodi pa se ob preslikavi lahko "razdelijo" tudi na več vhodov.
Za posamezen izhod bi rad ugotovil vse možne kombinacije vhodov in dobil njihove indexe (prve elemente v terki) in to seveda počel kar se da hitro :)
Rešitev za zgornji primer:
output (0,5) => [0,1,2], [1,2], [0,2] output (1,2) => [0,1], [1], [2], [0,2]
Razlaga (output (0,5) )
[0,1,2] => ta output lahko tvori input0 + input1 + input2 (preostali del input2 pa tvori drugi output).
[0,2] => ta output tvorita input0 in input2
Tu ni ideja, da optimiziram kateri inputi najlepše pokrijejo outpute, ampak izračun vseh takih pokritij.
Ima kdo kakšno idejo kako se tega lotim, da bom časovno čimbolj učinkovito?
Randomness ::
Malenkost nerazumljivo si opisal problem. Zakaj pri outputu (1,2) rešitev [1,2] ni veljavna?
kljuka13 ::
Če prav razumem, je tvoja naloga sledeča: iz dane množice (pozitivnih?) števil najdi vse take podmnožice, katerih vsota znaša vsaj k.
V časovno najslabšem primeru so možna rešitev vse podmnožice, kar pomeni časovno zahtevnost O(2^n).
Trivialni način bi bil generiranje vseh možnih podmnožic (v Pythonu npr. z itertools.combinations) in nato filtriranje tistih z ustrezno vsoto. Ta način je primeren, če je število tvojih vhodov majhno in če ne iščeš teoretično najboljšega algoritma. V nasprotnem primeru boš verjetno moral poseči po bolj sofisticiranih algoritmih - problem se v splošnem imenuje SSP (https://en.m.wikipedia.org/wiki/Subset_....
V časovno najslabšem primeru so možna rešitev vse podmnožice, kar pomeni časovno zahtevnost O(2^n).
Trivialni način bi bil generiranje vseh možnih podmnožic (v Pythonu npr. z itertools.combinations) in nato filtriranje tistih z ustrezno vsoto. Ta način je primeren, če je število tvojih vhodov majhno in če ne iščeš teoretično najboljšega algoritma. V nasprotnem primeru boš verjetno moral poseči po bolj sofisticiranih algoritmih - problem se v splošnem imenuje SSP (https://en.m.wikipedia.org/wiki/Subset_....
Randomness ::
Se strinjam s kljuko. Ena taka preprosta a počasna rešitev je backtracking.
Če ti je to prepočasno (for zanki bi se načeloma dalo izogniti), si poglej, kako se subset sum problem reši z dinamičnim programiranjem.
def search(xs: list[int], total: int) -> set[tuple[int]]: found = set() def aux(pos, running, ys): if running == total: found.add(tuple(ys)) elif pos < len(xs): for x in range(xs[pos]+1): new_running = running + x if new_running <= total: if x > 0: ys.append(pos) aux(pos+1, new_running, ys) if x > 0: ys.pop() else: break aux(0, 0, []) return found def test(): assert search([1,2,4],5) == {(0,1,2),(0,2),(1,2)} assert search([2,1,4],5) == {(0,1,2),(0,2),(1,2)} assert search([4,2,1],5) == {(0,1,2),(0,1),(0,2)} assert search([1,2,4],2) == {(0,1),(1,2),(0,2),(1,),(2,)} test()
Če ti je to prepočasno (for zanki bi se načeloma dalo izogniti), si poglej, kako se subset sum problem reši z dinamičnim programiranjem.
Zgodovina sprememb…
- spremenilo: Randomness ()
i33a ::
Najlepša hvala za odgovore!
Ta rešitev ni veljavna, ker že sam input 1 (z vrednostjo 2) pokrije celotno izhodno vrednost (2). Tako bi outputu, ki je že "zapolnjen" dodajali še dodatno vrednost, ki je ne potrebujemo.
Se pa strinjam, da sem mogoče malo slabo definiral problem.
- Uporabljajo se samo pozitivne cela števila
In lahko bi temu rekel tako ja, da iščem vse podmnožice katerih vsota je večja ali enaka določenemu številu.
Pri problemu subset sum običajno rešujemo, če obstaja podmnožica, ki ima vsoto enako k. Tu pa potrebujem vse podmnočice, katerih vsota je vsaj k (+ še njihove indexe vhodov).
Randomness je izjavil:
Malenkost nerazumljivo si opisal problem. Zakaj pri outputu (1,2) rešitev [1,2] ni veljavna?
Ta rešitev ni veljavna, ker že sam input 1 (z vrednostjo 2) pokrije celotno izhodno vrednost (2). Tako bi outputu, ki je že "zapolnjen" dodajali še dodatno vrednost, ki je ne potrebujemo.
Se pa strinjam, da sem mogoče malo slabo definiral problem.
- Uporabljajo se samo pozitivne cela števila
In lahko bi temu rekel tako ja, da iščem vse podmnožice katerih vsota je večja ali enaka določenemu številu.
Pri problemu subset sum običajno rešujemo, če obstaja podmnožica, ki ima vsoto enako k. Tu pa potrebujem vse podmnočice, katerih vsota je vsaj k (+ še njihove indexe vhodov).
Randomness ::
Ta rešitev ni veljavna, ker že sam input 1 (z vrednostjo 2) pokrije celotno izhodno vrednost (2). Tako bi outputu, ki je že "zapolnjen" dodajali še dodatno vrednost, ki je ne potrebujemo.
Če prav razumem, moraš posamezen element vzeti v celoti ali pa ga izpustiti. To je potem še lažji problem in je praktično ekvivalenten subset sum problemu. Zgornja koda se v tem primeru poenostavi v sledečo:
def search(xs: list[int], total: int) -> set[tuple[int]]: found = set() def aux(pos, running, ys): if running >= total: found.add(tuple(ys)) elif pos < len(xs): # skip element aux(pos+1, running, ys) # add element ys.append(pos) aux(pos+1, running + xs[pos], ys) ys.pop() aux(0, 0, []) return found def test(): assert search([1,2,4],5) == {(0,1,2),(0,2),(1,2)} assert search([2,1,4],5) == {(0,1,2),(0,2),(1,2)} assert search([4,2,1],5) == {(0,1),(0,2)} assert search([1,2,4],2) == {(0,1),(1,),(2,),(0,2)} test()
i33a ::
Najlepša hvala vsem. Zgoraj opisani algoritem deluje super!
Rešitev me je privedla do naslednjega problema, kjer bi rad našel pokritja. V tem primeru so izhodi lahko manjši, kot vhodi. (To lahko rešim z dodajanjem novega izhoda, ki pokrije razliko in ga kasneje ignoriram).
Primer:
Ima kdo kakšno idejo kako se lotiti tega problema oz. kako ga prevesti na kak znan problem za katerega poznamo algoritem?
Rešitev me je privedla do naslednjega problema, kjer bi rad našel pokritja. V tem primeru so izhodi lahko manjši, kot vhodi. (To lahko rešim z dodajanjem novega izhoda, ki pokrije razliko in ga kasneje ignoriram).
Primer:
inputs: [1000, 138] outputs: [10, 985, 10, 127] Možne interpretacije pokritij: [(I1)=>(O1,O2), (I2)=>(O3,O4)] [(I1)=>(O3,O2), (I2)=>(O1,O4)] [(I1,I2)=>(O1,O2,O3,O4)]
Ima kdo kakšno idejo kako se lotiti tega problema oz. kako ga prevesti na kak znan problem za katerega poznamo algoritem?
Vredno ogleda ...
Tema | Ogledi | Zadnje sporočilo | |
---|---|---|---|
Tema | Ogledi | Zadnje sporočilo | |
» | [SQL] Ali je možno postavit UNIQUE index po grupah?Oddelek: Programiranje | 1592 (993) | Spura |
» | Kateri ponudnik ima najboljši ping v competitive gameih?Oddelek: Omrežja in internet | 1107 (895) | ranko123 |
» | [Java-matematika] Računanje relativnega horizontalnega in vertikalnega kota v 3DOddelek: Programiranje | 1064 (900) | zavtom |
» | Ubuntu 10.4 1,2GB poraba ramaOddelek: Operacijski sistemi | 1115 (841) | KaRkY |
» | Iskanje naslednje ponovitve - najboljši algoritem (strani: 1 2 )Oddelek: Programiranje | 4419 (3477) | Thomas |