[es] - Pomoc oko uparivanja

FOX028
Visoka tehnicka skola strukovnih studija
Kosovska Mitrovica

Član broj: 258986
Poruke: 850

Sajt: https://www.zile028.com

+49 Profil

Pomoc oko uparivanja

^{14.06.2014. u 16:18 - pre 120 meseci}

POtrebna mi je pomoc ili savet. Problem se satoji u tome sto mi je potrebno da uparujem po dva elementa skupa npr.

1,2,3,4,5,6

12 34 56
12 35 46
12 36 45

itd

trebao bi da dobijem sve ovakve kombinacije s tim sto je

21 34 56 isto sto i 12 34 56

po kom bi sistemu mogao ovo da resim, tj. da se napise program

[email protected]=

Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
..ppoe.dyn.broadband.blic.net.

+62 Profil

Re: Pomoc oko uparivanja

^{15.06.2014. u 20:46 - pre 120 meseci}

Pojasni malo taj kriterijum jednakosti, vrlo je cudan..? Navedi jos koji primer.

Pozz

Odgovor na temu

FOX028
Visoka tehnicka skola strukovnih studija
Kosovska Mitrovica

Član broj: 258986
Poruke: 850

Sajt: https://www.zile028.com

+49 Profil

Re: Pomoc oko uparivanja

^{16.06.2014. u 05:25 - pre 120 meseci}

rucno ispisano ovo bi bile sve moguce kombinacije koje zadovoljavaju kriterijum

12 34 56
12 35 46
12 36 45

13 24 56
13 25 46
13 26 45

14 23 56
14 25 36
14 26 35

15 23 46
15 24 36
15 26 34

16 23 45
16 24 35
16 25 34

Ovi elementi su ustvari cvorovi jedne transportne mreze i izmedju svakog od njih postoji odredjena udaljenost, ja bi trebao u ovom slucaju da saberem po tri grane ove mreze i da odaberem onu kombinaciju koja je najkraca.
nekad moze imati 6 cvorova nekad manje ili vise.

[email protected]=

Odgovor na temu

Rapaic Rajko
Bgd

Član broj: 4105
Poruke: 810
..ppoe.dyn.broadband.blic.net.

+62 Profil

Re: Pomoc oko uparivanja

^{17.06.2014. u 10:00 - pre 119 meseci}

Hm, a ako imas neparan broj elemenata pocetnog skupa, ovako nesto:

1 2 3 4 5 6 7

kako onda slazes parove elemenata (putanje)?

Pokusavam da skontam logiku uparivanja koju si prikazao, i nesto mi nije jasno. Ako se trazi najkraci put, onda bi zapravo prva putanja trebalo da bude

12 23 34 45 56

ili ja tu negde gresim? Na ovaj nacin, moze se uraditi nesto i sa neparnim brojem lokacija, npr. za 7 elemenata ide

12 23 34 45 56 67

i tako dalje.

Ako (verovatno) ipak gresim :), onda 'ajde poslozi elemente/parove za 7 elemenata, samo prvu kombinaciju (da, to su upravo kombinacije).

Pozz

Odgovor na temu

FOX028
Visoka tehnicka skola strukovnih studija
Kosovska Mitrovica

Član broj: 258986
Poruke: 850

Sajt: https://www.zile028.com

+49 Profil

Re: Pomoc oko uparivanja

^{17.06.2014. u 15:24 - pre 119 meseci}

ovo ne bi bilo ispravno, bar ne onako kako je meni potrebno

12 23 34 45 56

u ovom slucaju postoje 5 grane, a za sest cvorova treba da postoje 3 grane
sto se tice neparnog broja elemenata to bi morao jos malo da istrazim kako bi islo, ali recimo moglo bi ovako

12 34 56
12 34 57
12 37 56
12 37 54
12 37 64
itd.

ali o ovom slucaju bi razmisljao kasnje, za sad sam hteo da se ogranicim na paran broj elemenata

[email protected]=

Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541

+711 Profil

Re: Pomoc oko uparivanja

^{17.06.2014. u 15:42 - pre 119 meseci}

Jel ti treba najbrže rešenje, najkraće rešenje, šta tačno želiš...

Evo npr u Rubiju

Code:

require 'set'

a = [1, 2, 3, 4, 5, 6]

r = Set.new(
    a.permutation.map{|p|
        Set.new(
            p.each_slice(2).map{|s|
                Set.new(s)
            }
        )
    }
)

http://ideone.com/7j0sng

Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541

+711 Profil

Re: Pomoc oko uparivanja

^{17.06.2014. u 16:52 - pre 119 meseci}

Malo sam se igrao, evo jedna interesantna implementacija - rekurzivna, "lenja" (lazy) evaluacija:

Code:

def lkomb niz
  Enumerator.new do |y|
    if niz.length == 2
      y.yield([niz])
    else
      head, *tail = niz
      tail.each do |other|
        lkomb(tail - [other]).each { |rest|
          y.yield([[head, other]] + rest)
        }
      end
    end
  end
end

Ona omogućava da se i za velike ulazne nizove brzo dobije prvih n parova bez računanja kompletnog seta.

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Pomoc oko uparivanja

^{17.06.2014. u 19:28 - pre 119 meseci}

FOXe, nisi primetio da sam ti odgovorio na Excel temi: http://www.elitesecurity.org/t476927-0#3454632

Odgovor na temu

FOX028
Visoka tehnicka skola strukovnih studija
Kosovska Mitrovica

Član broj: 258986
Poruke: 850

Sajt: https://www.zile028.com

+49 Profil

Re: Pomoc oko uparivanja

^{17.06.2014. u 20:19 - pre 119 meseci}

primetio sam, ali ja kada sam postavljao pitanje postavio sam ga na oba foruma u isto vreme, u nadi da sto pre dobijem neki odgovor. A za tvoj primer koji si uradio (hvala na trudu u svakom slucaju) trebace mi malo vise vremena, jer mi je C++ nepoznat, vise radim u VB.

[email protected]=

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Pomoc oko uparivanja

^{18.06.2014. u 14:04 - pre 119 meseci}

@FOX

Nisam nikad napisao ni liniju koda u toj monstruoznoj tvorevini zvanoj VB. Jesam nešto malo pisao VBA, ali uglavnom tako što snimim makro, pa onda otvorim MSDN i gomilu stackoverflow linkova, na osnovu kojih modifikujem kod.

Evo ponovo algoritma:
1. Uzmi da je tekuća grupa ona koja je pretposlednja.
1. Zapamti desni element tekuće grupe.
2. uporedi ga sa svim ostalim elementima ostalih (desnih) grupa i nadji minimalan element koji je veći od tog zapamćenog
3. Ako je takav element pronađen, zameni ga sa elementom na poslednjem mestu tekuće grupe, a elemente ostalih grupa desno od tekuće sortiraj i ispiši kombinaciju.
4. Ako nije pronađen, pomeri se za jednu grupu u levo i ponovi postupak dok ne potrošiš sve grupe.

Ako ovo nije jasno, evo primera.
Recimo da treba da napravimo kombinacije od 8 elemenata.
Napravimo niz koji ima sledeći sadržaj: 1 2 3 4 5 6 7 8
Ovaj niz predstavlja prvu kombinaciju, tj. : (1,2) (3,4) (5,6) (7,8)
Koja je sledeća kombinacija?
Uzmemo desni član (to je 6) pretposlednje grupe (to je grupa (5,6), odnosno par čvorova grafa).
Uporedimo ga sa svim članovima niza DESNO od njega (to su 7 i 8).
Nađemo minimalan član koji je veći od njega (znači min(7,8) tako da je min > 6), što je u ovom slučaju element 7)
Zamenimo im mesta (sada je originalan niz ovakav: 1 2 3 4 5 7 6 8 - 6 i 7 su zamenili mesta).
Zatim sortiramo niz desno od mesta gde je prethodno bio broj 6 (tj. sortiramo 6 i 8, a oni su već sortirani kako treba)
Vratimo niz koji smo tako formirali (tj. 1 2 3 4 5 7 6 8, odnosno, ako to prikažemo kao niz uređenih parova to je (1,2), (3,4), (5,7), (6,8)

I tako smo dobili kombinaciju 2 od kombinacije 1.

Primer 2.

Kako od kombinacije 15: (1,2) (3,8) (4,7) (5,6) dobijemo kombinaciju 16: (1,3) (2,4) (5,6) (7,8)
Desni član treće grupe je broj 7.
Desno od njega su brojeve 5 i 6 i oba su manja, tako da ne postoji minimalan broj desno od 7 da je veći od 7.
Zato uzmemo DESNI član DRUGE grupe, a to je 8.
Opet se pojavljuje ista situacija, svi elementi niza desno od 8 su manji od njega.
Zato uzimamo DESNI član PRVE grupe, a to je 2.
Desno od 2 se nalazi 3 koji je najmanji broj veći od 2, a koji je desno od 2 u nizu.
Zamenimo mesta 2 i 3 i dobijemo privremeni niz 1 3 2 8 4 7 5 6.
1 i 3 ostaju na svojim mestima, a sortiramo DESNO od 3 podniz 2 8 4 7 5 6, pa dobijemo 2 4 5 6 7 8.
Rezultujući niz je 1 3 2 4 5 6 7 8, tj. (1,3) (2,4) (5,6) (7,8) što je i trebalo da se dobije.

Da li je sada jasno?

Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541

+711 Profil

Re: Pomoc oko uparivanja

^{18.06.2014. u 21:41 - pre 119 meseci}

@djoka:

Nemam baš vremena da analiziram tvoj algoritam, reci mi samo jel to "zvaničan" algoritam za rešavanje ovog problema i koja mu je složenost?

BTW implementirao sam rešenje i u Haskell-u, dosta interesantan jezik:

http://ideone.com/J8afCH

Code:
upari :: [Int] -> [[(Int, Int)]]
upari [] = []
upari [a, b] = [[(a, b)]]
upari (a:xa) = foldl ff [] [0..length(xa) - 1]
  where
    ff :: [[(Int, Int)]] -> Int -> [[(Int, Int)]]
    ff acc i = acc ++ map (\res -> (a, b):res) (upari(left ++ right))
      where
        (left, b:right) = splitAt i xa


main = mapM_ print (upari [1..6])

Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3453

Jabber: djoka_l

+1462 Profil

Re: Pomoc oko uparivanja

^{18.06.2014. u 22:05 - pre 119 meseci}

Moj algoritam, nisam proveravao složenost ali mislim da je veća od n^2logn, a manje od n!, mada se ne bih zakleo u drugu tvrdnju.

Odgovor na temu

FOX028
Visoka tehnicka skola strukovnih studija
Kosovska Mitrovica

Član broj: 258986
Poruke: 850

Sajt: https://www.zile028.com

+49 Profil

Re: Pomoc oko uparivanja

^{19.06.2014. u 19:41 - pre 119 meseci}

Jasno i primenjeno

Code:
Dim Niz As Variant
Dim n As Integer
Dim k As Integer

Public Sub Main()

Dim TG As Variant
Dim elem As Single
Dim i As Integer

Dim MinElem As Integer
Dim komb As String

k = 1
n = 6

komb = ""

Niz = Array(1, 4, 6, 7, 8, 9)
Stampaj Niz

TG = Niz

Do While NextGroup(Niz, TG(n - 1)) And k < 20
    k = k + 1
    Stampaj Niz
Loop

End Sub

Public Function NextGroup(arr As Variant, ByVal elem As Integer) As Boolean
Dim i As Integer
Dim Gropu As Integer
Dim m As Integer

NextGroup = False
Group = n / 2 - 1

i = 2

Do
    If arr(i) < elem Then
        m = FindMin(arr, n - i, n, arr(n - i - 1))
        If m = 0 Then

        Else
            Swap n - i - 1, m
            SortArr arr, n - i
            NextGroup = True
        End If
    End If

    i = i + 2
Loop While i < n And Not NextGroup

End Function

Public Function FindMin(arr As Variant, ByVal start As Integer, ByVal kraj As Integer, ByVal element As Single)

Dim i As Integer
Dim min As Integer
Dim p As Integer
p = 0

For i = start To kraj - 1
    If arr(i) > element Then
        If p = 0 Then
            p = i
            min = arr(i)
        Else
            If arr(i) < min Then
                min = arr(i)
                p = i
            End If
        End If
    End If
Next i

FindMin = p
End Function

Public Function Swap(ByVal l As Integer, ByVal r As Integer)
Dim t As Single
t = Niz(l)
Niz(l) = Niz(r)
Niz(r) = t
End Function

Public Sub SortArr(arr As Variant, ByVal start As Integer)
Dim strTemp As Single
Dim i As Long
Dim j As Long
Dim lngMin As Long
Dim lngMax As Long

lngMin = start
lngMax = UBound(arr)

For i = lngMin To lngMax - 1
    For j = i + 1 To lngMax
        If arr(i) > arr(j) Then
            strTemp = arr(i)
            arr(i) = arr(j)
            arr(j) = strTemp
        End If
    Next j
Next i
Niz = arr
End Sub

Public Sub Stampaj(arr As Variant)

Dim komb As String
Dim i As Integer

komb = ""

For i = 1 To n
    If i = 1 Then
        komb = Val(Niz(i - 1))
    ElseIf i Mod 2 = 0 Then
        komb = komb & Val(Niz(i - 1))
    Else
        komb = komb & ", " & Val(Niz(i - 1))
    End If
Next

Debug.Print k & ":", komb

End Sub

a evo ga i izlazni rezultat, bas onako kako mi je potrebno

Code:
1:            14, 67, 89
2:            14, 68, 79
3:            14, 69, 78
4:            16, 47, 89
5:            16, 48, 79
6:            16, 49, 78
7:            17, 46, 89
8:            17, 48, 69
9:            17, 49, 68
10:           18, 46, 79
11:           18, 47, 69
12:           18, 49, 67
13:           19, 46, 78
14:           19, 47, 68
15:           19, 48, 67

[email protected]=

Odgovor na temu