Forum » Programiranje » Algoritem za razbitje seznama in kasnejše združevanje nazaj
Algoritem za razbitje seznama in kasnejše združevanje nazaj
i77a ::
Pozdravljeni,
imam sledeč problem. Seznam števil moram razbiti na vse možne podmnožice, pri čemer pa vrstni red ni pomemben (ne želimo si podvajanj).
Algoritem moram napisati v C++, tako da uporaba nekih Python knjižnic žal ne pride v poštev.
Primer vhoda:
Izhodi:
Iz teh množic nato izračunam določene vrednosti. Kasneje pa si želim te množice nazaj združiti oz. izračunati kako pašejo skupaj.
Imamo npr. 3 skupine (osnovna množica, ki jo želimo sestaviti brez podvajanja elementov je [1,2,3,4]):
Možni izhodi v tem primeru so:
Ima kdo kakšno idejo kateri algoritem bi rešil moj problem (čimbolj učinkovito). Zavedam se, da bo za daljše sezname ogromno število možnih podmnožic.
Najlepša hvala za pomoč!
imam sledeč problem. Seznam števil moram razbiti na vse možne podmnožice, pri čemer pa vrstni red ni pomemben (ne želimo si podvajanj).
Algoritem moram napisati v C++, tako da uporaba nekih Python knjižnic žal ne pride v poštev.
Primer vhoda:
[0,1,2]
Izhodi:
[[0,1,2], []], [[0],[1,2]], [[1],[0,2]], [[2],[0,1]], [[0],[1],[2]]
Iz teh množic nato izračunam določene vrednosti. Kasneje pa si želim te množice nazaj združiti oz. izračunati kako pašejo skupaj.
Imamo npr. 3 skupine (osnovna množica, ki jo želimo sestaviti brez podvajanja elementov je [1,2,3,4]):
[[1,2], [3,4]] [[1], [2], [3,4]] [[1,2,3,4]]
Možni izhodi v tem primeru so:
[1,2,3,4] (iz 3. skupine) [1,2] (iz 1. skupine), [3,4] (iz 1. ali 2. skupine) [1], [2] (iz 2. skupine), [3,4] (iz 1. ali 2. skupine)
Ima kdo kakšno idejo kateri algoritem bi rešil moj problem (čimbolj učinkovito). Zavedam se, da bo za daljše sezname ogromno število možnih podmnožic.
Najlepša hvala za pomoč!
6bt9hmDwY ::
Najprej posortiraj, iteriraj element po element rekurzivno do zadnjega in vstavljaj podmnožice v vector (ali pa map) in potem uporabi indekse (ali keye).
Če bo kakšna dobričina, ti bo napisal.
Če bo kakšna dobričina, ti bo napisal.
i77a ::
Ok, sortiranje ni problem.
Ne razumem pa točno kako naj rekurzivno vstavljam? Rekurzijo načeloma razumem in najbrž je ideja, da kličem isto funkcijo na manjšem seznamu, dokler ta ni dolžine 1 oz. 0.
Vendar ne razumem kaj naj vsak korak rekurzije naredi?
Kaj naj naredim z indexi/keyi?
Ne razumem pa točno kako naj rekurzivno vstavljam? Rekurzijo načeloma razumem in najbrž je ideja, da kličem isto funkcijo na manjšem seznamu, dokler ta ni dolžine 1 oz. 0.
Vendar ne razumem kaj naj vsak korak rekurzije naredi?
Kaj naj naredim z indexi/keyi?
Jarno ::
Na internetu je kar precej osnovnih algoritmov za iskanje vseh podmnožic neke množice.
Tukaj ti brez podrobnih navodil verjetno nihče ne bo natančno reševal problema...
Tukaj ti brez podrobnih navodil verjetno nihče ne bo natančno reševal problema...
#65W!
6bt9hmDwY ::
Glede na podane vhode in izhode (kot je napisano), moraš N elementov 'razrezati' in dodati v rezultirajočo zbirko podmnožice vseh velikosti, če razumem naveden izhod.
Najprej dodaš 0 elementov in vse elemente v output vector, da rešiš skrajnosti (1 sestavljen element v izhodu).
Rekurzivno do podmnožice velikosti 1, manjše vsakič za en element; in vsakič uporabiš na istem nivoju drug element v podmnožici in dodaš v zbirko s preostankom elementov (vedno pa, izgleda, imaš množico en {{element}, {N-1 elementov}}. Jaz bi pričakoval še {{O elementov}, {N-O elementov}} ampak ok, morda ni potrebno.
Funkcija to dela, da ti ostane en sam (rekurzija), več ni potrebno, ker prazno množico že imaš. Tvoj primer je poenostavljen s tremi elementi, razmišljaj pa v N, verjetno je to namen vaje, da je univerzalno.
Bi pa predlagal, da še kdo preveri, če sem kaj preveč poenostavil ali zakompliciral. Je pa to čisto 'akademska' zadeva.
Najprej dodaš 0 elementov in vse elemente v output vector, da rešiš skrajnosti (1 sestavljen element v izhodu).
Rekurzivno do podmnožice velikosti 1, manjše vsakič za en element; in vsakič uporabiš na istem nivoju drug element v podmnožici in dodaš v zbirko s preostankom elementov (vedno pa, izgleda, imaš množico en {{element}, {N-1 elementov}}. Jaz bi pričakoval še {{O elementov}, {N-O elementov}} ampak ok, morda ni potrebno.
Funkcija to dela, da ti ostane en sam (rekurzija), več ni potrebno, ker prazno množico že imaš. Tvoj primer je poenostavljen s tremi elementi, razmišljaj pa v N, verjetno je to namen vaje, da je univerzalno.
Bi pa predlagal, da še kdo preveri, če sem kaj preveč poenostavil ali zakompliciral. Je pa to čisto 'akademska' zadeva.
Spura ::
To je preprosto. Rekurzivno se gres skoz seznam elementov i -> [0..n), signature fn(prefixSeznam, i).
Najprej preveris ustavitveni pogoj, ce je i = n, potem vrnes prefixSeznam, sicer klices rekurzivno z i+1 dvakrat, enkrat z i-tim elementom dodanim v seznam, drugic brez. Vrnes konkatenacijo resultatov teh rekurzivnih klicev.
Najprej preveris ustavitveni pogoj, ce je i = n, potem vrnes prefixSeznam, sicer klices rekurzivno z i+1 dvakrat, enkrat z i-tim elementom dodanim v seznam, drugic brez. Vrnes konkatenacijo resultatov teh rekurzivnih klicev.
(defn superset [elements]
(letfn [(inner [prefix i]
(if (= i (count elements))
[prefix]
(concat (inner prefix (inc i))
(inner (conj prefix (elements i)) (inc i)))))]
(inner [] 0)))
=> #'development/superset
(superset [1 2 3 4])
=> ([] [4] [3] [3 4] [2] [2 4] [2 3] [2 3 4] [1] [1 4] [1 3] [1 3 4] [1 2] [1 2 4] [1 2 3] [1 2 3 4])
kuall ::
problem razdeliš na 2 dela.
A. dobi vse možne podsezname iz nekega seznama (vrstni red ni važen)
B. dodaj podsezname iz točke 1 v vse možne pare. s tem, da se osnovni element ne sme ponoviti.
toranj:
vhod: [0,1,2]
Točko A se da zlahka takole rešit:
narediš bitarray velikosti vhoda.
ta bitarray "vrtiš" (narediš vse možne kombinacije ničel in enk v njej)
kjer je ničla to pomeni, da tisti element izbrišeš
toranj:
1. [0,0,0] = []
2. [0,0,1] = [2]
3. [0,1,0] = [1]
4. [0,1,1] = [1,2]
5. [1,0,0] = [0]
6. [1,0,1] = [0,2]
7. [1,1,0] = [0, 1]
8. [1,1,1] = [0, 1, 2]
kako vrtiš bitarray?
število kombinacij bo:
power (2, len (input))
torej narediš for (int i = 0 to power (2, len (input)))
vsakič ta int pretvoriš v bitarray pa imaš, v c# takole:
Točko B se da rešit z bitwise XOR. Shraniš pri vsaki podmnožici njen i in potem narediš i xor i2
če to vrne power (2, len (input) (v našem primeru 8) potem veš, da lahko ta 2 para daš skupaj.
pač prej še vse podmnožice primerjaš, ali jih lahko vržeš skupaj v par, takole:
for (int x = 0 to štPodmnožic)
{
for (int y = x + 1 to štPodmnožic)
{
par = {podmnožice [x], podmnožice[y]}
aliJeParOk = (i1 XOR i2) == štPodmnožic
if (aliJeParOk)
okPari = append (okPari, par)
}
}
pač takole na pamet, lahko da je kaka napaka kje.
A. dobi vse možne podsezname iz nekega seznama (vrstni red ni važen)
B. dodaj podsezname iz točke 1 v vse možne pare. s tem, da se osnovni element ne sme ponoviti.
toranj:
vhod: [0,1,2]
Točko A se da zlahka takole rešit:
narediš bitarray velikosti vhoda.
ta bitarray "vrtiš" (narediš vse možne kombinacije ničel in enk v njej)
kjer je ničla to pomeni, da tisti element izbrišeš
toranj:
1. [0,0,0] = []
2. [0,0,1] = [2]
3. [0,1,0] = [1]
4. [0,1,1] = [1,2]
5. [1,0,0] = [0]
6. [1,0,1] = [0,2]
7. [1,1,0] = [0, 1]
8. [1,1,1] = [0, 1, 2]
kako vrtiš bitarray?
število kombinacij bo:
power (2, len (input))
torej narediš for (int i = 0 to power (2, len (input)))
vsakič ta int pretvoriš v bitarray pa imaš, v c# takole:
BitArray b = new BitArray(new byte[] { x });
int[] bits = b.Cast<bool>().Select(bit => bit ? 1 : 0).ToArray();
Točko B se da rešit z bitwise XOR. Shraniš pri vsaki podmnožici njen i in potem narediš i xor i2
če to vrne power (2, len (input) (v našem primeru 8) potem veš, da lahko ta 2 para daš skupaj.
pač prej še vse podmnožice primerjaš, ali jih lahko vržeš skupaj v par, takole:
for (int x = 0 to štPodmnožic)
{
for (int y = x + 1 to štPodmnožic)
{
par = {podmnožice [x], podmnožice[y]}
aliJeParOk = (i1 XOR i2) == štPodmnožic
if (aliJeParOk)
okPari = append (okPari, par)
}
}
pač takole na pamet, lahko da je kaka napaka kje.
SloKin ::
Koncno sem docakal dan, da kual postavi svojo kodo na ST. Res sem ponosen na tebe. Cist iskreno.
Dvojni loop v B delu... Kolk je casovna zahtevnost tega v odvisnosti od dolzine podanega seznama? A tega se ne da hitreje naredit?
Op jaz drugega dela ne razumem dobro ampak se mi zdi, da je vprasanje v smislu: za podano mnozico in elemente mi povej razbitje, ki bo imel to podmnozico.
Npr, ce imam [1,2,3,4] in me zanima [1] bi bil odgovor [[1], [2,3,4]], [[1], [2,3], [4]], [[1], [2,4], [3]], [[1], [2], [3,4]] in [[1], [2], [3], [4]].
Jah pac vzami iz osnovne mnozice kar te zanima in naredi razcep tega. Potem pa vsakemu seznamu nazaj pripopaj kar te zanima.
Ce pa ne razumem prav potem pa itak ni prava resitev...
Dvojni loop v B delu... Kolk je casovna zahtevnost tega v odvisnosti od dolzine podanega seznama? A tega se ne da hitreje naredit?
Op jaz drugega dela ne razumem dobro ampak se mi zdi, da je vprasanje v smislu: za podano mnozico in elemente mi povej razbitje, ki bo imel to podmnozico.
Npr, ce imam [1,2,3,4] in me zanima [1] bi bil odgovor [[1], [2,3,4]], [[1], [2,3], [4]], [[1], [2,4], [3]], [[1], [2], [3,4]] in [[1], [2], [3], [4]].
Jah pac vzami iz osnovne mnozice kar te zanima in naredi razcep tega. Potem pa vsakemu seznamu nazaj pripopaj kar te zanima.
Ce pa ne razumem prav potem pa itak ni prava resitev...
kuall ::
Dvojni loop v B delu... Kolk je casovna zahtevnost tega v odvisnosti od dolzine podanega seznama? A tega se ne da hitreje naredit?
Op nima naloge naredit hitro kodo ampak naredit kodo, ki vrne pravilni rezultat. Tak da ne pametuj ampak raje napiši kaj uporabnega, tako kot sem jaz, npr celo rešitev naloge.
kuall ::
Op jaz drugega dela ne razumem dobro
Saj sem jaz čisto dobro interpretiral nalogo, še enkrat si preberi moj post pa ti bo mogoče kapnilo. Ni nobenga drugega dela. Sta samo A in B tako kot sem jaz opisal nalogo. Ti ne razumeš dela B.
Sem se pa zdajle spomnil še ene bolj enostavne rešitve. Ampak ker se op ni zahvalil niti za prvo rešitev jo bom zadržal zase. Pa ker je težak SloKin prišel srat v temo.
Oziroma tam sem mau falil, da se gre samo za pare, to se da popravit.
Zgodovina sprememb…
- spremenilo: kuall ()
IgorCardanof ::
Koncno sem docakal dan, da kual postavi svojo kodo na ST. Res sem ponosen na tebe. Cist iskreno.
Dvojni loop v B delu... Kolk je casovna zahtevnost tega v odvisnosti od dolzine podanega seznama? A tega se ne da hitreje naredit?
Op jaz drugega dela ne razumem dobro ampak se mi zdi, da je vprasanje v smislu: za podano mnozico in elemente mi povej razbitje, ki bo imel to podmnozico.
Npr, ce imam [1,2,3,4] in me zanima [1] bi bil odgovor [[1], [2,3,4]], [[1], [2,3], [4]], [[1], [2,4], [3]], [[1], [2], [3,4]] in [[1], [2], [3], [4]].
Jah pac vzami iz osnovne mnozice kar te zanima in naredi razcep tega. Potem pa vsakemu seznamu nazaj pripopaj kar te zanima.
Ce pa ne razumem prav potem pa itak ni prava resitev...
Pretty sure, da je način z bitmaskami najlažji za napisat. Po časovni zahtevnosti pa pomoje v enakem razredu kot najhitrejsi algoritem. Če hočeš generirat vse podmnožice množice z N elementi, boš moral čez 2^N kombinacij. Implementacija z bitmaski ima O(N * 2^N).
Zgodovina sprememb…
- spremenilo: IgorCardanof ()
SloKin ::
@kual aaaa si ugotovil, da neki ne stima ze v samem razumevanju naloge. Kako pa? Saj si ti to pravilno intepretiral?
Ej a ti se neki povem? Pa ne komu povedat... Vsak i, ki ga uporabljas je manjsi od stevila podmnozic. Kako bos iz tega z xor kadarkoli dobil stevilko, ki je enaka stevilu podmnozic ves verjetno samo ti.
@Jeff Tezos kot lahko vidis iz dela B nasega kolega kuala, v algoritmu uporablja dve for zanki, ki gresta do stevila podmnozic. Kar pomeni, da je nas kolega naredil algoritem O(2^2n). Torej seznam s 50 elementi ne rabi vec samo 2^50 operacij pac pa 2^100.
@kual komentar na algoritem dela... Dela dela. Samo nikoli se ne zakljuci ?
Prijatelj... Res je bila pohvala misljena iskreno. Napredujes... Ampak dej... Popravi tisto, kar pravis, da se da popravit. Mene osebno zelo zanima.
Ej a ti se neki povem? Pa ne komu povedat... Vsak i, ki ga uporabljas je manjsi od stevila podmnozic. Kako bos iz tega z xor kadarkoli dobil stevilko, ki je enaka stevilu podmnozic ves verjetno samo ti.
@Jeff Tezos kot lahko vidis iz dela B nasega kolega kuala, v algoritmu uporablja dve for zanki, ki gresta do stevila podmnozic. Kar pomeni, da je nas kolega naredil algoritem O(2^2n). Torej seznam s 50 elementi ne rabi vec samo 2^50 operacij pac pa 2^100.
@kual komentar na algoritem dela... Dela dela. Samo nikoli se ne zakljuci ?
Prijatelj... Res je bila pohvala misljena iskreno. Napredujes... Ampak dej... Popravi tisto, kar pravis, da se da popravit. Mene osebno zelo zanima.
kuall ::
mišljeno je bilo, da je
i1 npr [1,0,0]
i2 npr [0,1,1]
in z i1 xor i2 dobiš [1,1,1] = 8
ker se ne gre za pare je zanko v B točki treba spremnit, da dodaja podmnožice tako dolgo, da i xor i3 postane [1,1,1].
dodamo lahko samo tiste podmnožice, kjer i xor iKandidat vrne številko, ki je večja in od i in od iKandidat.
primer:
[0,0,1] xor [0,0,1] = [0,0,0] -> ni ok, ne smemo dodati skupaj
[0,0,1] xor [0,1,0] = [0,1,1] -> ok ampak nadaljujmo z dodajanjem naslednje podmnožice, ker še niso vsi členi 1
[0,1,1] xor [1,0,0] = [1,1,1] -> končano
i1 npr [1,0,0]
i2 npr [0,1,1]
in z i1 xor i2 dobiš [1,1,1] = 8
ker se ne gre za pare je zanko v B točki treba spremnit, da dodaja podmnožice tako dolgo, da i xor i3 postane [1,1,1].
dodamo lahko samo tiste podmnožice, kjer i xor iKandidat vrne številko, ki je večja in od i in od iKandidat.
primer:
[0,0,1] xor [0,0,1] = [0,0,0] -> ni ok, ne smemo dodati skupaj
[0,0,1] xor [0,1,0] = [0,1,1] -> ok ampak nadaljujmo z dodajanjem naslednje podmnožice, ker še niso vsi členi 1
[0,1,1] xor [1,0,0] = [1,1,1] -> končano
Spura ::
Ta drugi del je exact cover problem. Algoritem za uporabit je Dancing Links od Knutha.
Zgodovina sprememb…
- spremenil: Spura ()
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Generiranje vseh kombinacij med vhodi in izhodiOddelek: Programiranje | 829 (509) | i33a |
| » | Matematična analiza naloga (strani: 1 2 )Oddelek: Šola | 6445 (4795) | lebdim |
| » | Python - pomoč!Oddelek: Programiranje | 1201 (1037) | lknix |
| » | urejanje - pythonOddelek: Programiranje | 1357 (1134) | ktka |
| » | Python iskanje podvojenih vrednostiOddelek: Programiranje | 1488 (1201) | BlueRunner |