☰

» »

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: 
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_....

Randomness ::

Se strinjam s kljuko. Ena taka preprosta a počasna rešitev je backtracking.
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…

i33a ::

Najlepša hvala za odgovore!

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

Zimonem ::

Permutacija brez ponavljanja.

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

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[SQL] Ali je možno postavit UNIQUE index po grupah?

Oddelek: Programiranje		211592 (993) Spura
»

Kateri ponudnik ima najboljši ping v competitive gameih?

Oddelek: Omrežja in internet		61106 (894) ranko123
»

[Java-matematika] Računanje relativnega horizontalnega in vertikalnega kota v 3D

Oddelek: Programiranje		51064 (900) zavtom
»

Ubuntu 10.4 1,2GB poraba rama

Oddelek: Operacijski sistemi		201114 (840) KaRkY
»

Iskanje naslednje ponovitve - najboljši algoritem (strani: 1 2 )

Oddelek: Programiranje		724419 (3477) Thomas

Več podobnih tem