Forum » Znanost in tehnologija » Kombinatorčni problem.
Kombinatorčni problem.
ciki57 ::
Imamo n množic.
Množice imajo različno število elementov. Recimo množica i ima k(i) elementov.
Znotraj množice so vsi elementi različni.
Med množicami pa se lahko elementi ponavljajo (ali pa tudi ne). Recimo da z C(A,B) označimo skupne elemente množic A in B.
Sedaj naredimo vektor velikosti n tako da v izberemo en element iz vsake množice. Prvi element iz prve, drugi iz druge itd.
Elementi znotraj vektorja se ne smejo ponavljati!
Koliko takih vektorjev obstaja??
--------------------
Primer:
množica 1: { 3 5 7 8 }
množica 2: { 1 7 8 }
množica 3: { 5 8 9 }
množica 4: { 6 }
n = 4;
k(1) = 4; k(2) = 3; k(3) = 3; k(4) = 1;
C(1,2) = { 8,7}; C(1,3) = {5,8}; C(1,4) = {}; C(2,3) = { 8 }; C(2,4) = {}, C(3,4) = {}
pravilen vektor: [ 3, 1, 5, 6]
nepravilen vektor: [ 5, 8, 5, 6] - petka se ponovi -> narobe
število pravilnih vektorjev (rešitev problema) = 22
--------------------
Če imamo samo dve množici je rešitev preprosta: k(1)*k(2) - |C(1,2)|
Pri 3 in več pa se zaplete...
Ali je to kakšen standarden kombinatorični problem? Mal sem iskal po googlu pa nisem našel nič podobnega.
Rabil bi splošno formulo, ki mi takoj izračuna št. vektorjev, če imam recimo 10 množic in par sto elementov v vsaki.
Množice imajo različno število elementov. Recimo množica i ima k(i) elementov.
Znotraj množice so vsi elementi različni.
Med množicami pa se lahko elementi ponavljajo (ali pa tudi ne). Recimo da z C(A,B) označimo skupne elemente množic A in B.
Sedaj naredimo vektor velikosti n tako da v izberemo en element iz vsake množice. Prvi element iz prve, drugi iz druge itd.
Elementi znotraj vektorja se ne smejo ponavljati!
Koliko takih vektorjev obstaja??
--------------------
Primer:
množica 1: { 3 5 7 8 }
množica 2: { 1 7 8 }
množica 3: { 5 8 9 }
množica 4: { 6 }
n = 4;
k(1) = 4; k(2) = 3; k(3) = 3; k(4) = 1;
C(1,2) = { 8,7}; C(1,3) = {5,8}; C(1,4) = {}; C(2,3) = { 8 }; C(2,4) = {}, C(3,4) = {}
pravilen vektor: [ 3, 1, 5, 6]
nepravilen vektor: [ 5, 8, 5, 6] - petka se ponovi -> narobe
število pravilnih vektorjev (rešitev problema) = 22
--------------------
Če imamo samo dve množici je rešitev preprosta: k(1)*k(2) - |C(1,2)|
Pri 3 in več pa se zaplete...
Ali je to kakšen standarden kombinatorični problem? Mal sem iskal po googlu pa nisem našel nič podobnega.
Rabil bi splošno formulo, ki mi takoj izračuna št. vektorjev, če imam recimo 10 množic in par sto elementov v vsaki.
- spremenil: ciki57 ()
whatever ::
Za tale primer računaš takole:
Primer:
množica A: { 3 5 7 8 }
množica B: { 1 7 8 }
množica C: { 5 8 9 }
množica D: { 6 }
(a/b) POMENI BINOMSKI SIMBOL, TOREJ a NAD b!
1*(3/1)*(2/1)*1 + 1*(3/1)*(2/1)*1 + 1*(2/1)*(3/1)*1 + 1*(2/1)*(2/1)*1 =
1*3*2*1 + 1*3*2*1 + 1*2*3*1 + 1*2*2*1 = 6 + 6 + 6 + 4 = 18 + 4 = 22.
Torej: Začneš z vsakim elementom prve množice posebej in nato primerjaš če je kateri element naslednje množice enak kateremu koli elementu pred njim. Če začneš s 3: imaš 1*(3/1) možnosti, vendar se v množici C element 8 ponovi glede na množico B in zato *(2/1) - ker imaš naprej izbiraš en element med dvema elementoma množice C. Najbrž se bo dalo posplošit tudi za primere, ko je n=10.
Primer:
množica A: { 3 5 7 8 }
množica B: { 1 7 8 }
množica C: { 5 8 9 }
množica D: { 6 }
(a/b) POMENI BINOMSKI SIMBOL, TOREJ a NAD b!
1*(3/1)*(2/1)*1 + 1*(3/1)*(2/1)*1 + 1*(2/1)*(3/1)*1 + 1*(2/1)*(2/1)*1 =
1*3*2*1 + 1*3*2*1 + 1*2*3*1 + 1*2*2*1 = 6 + 6 + 6 + 4 = 18 + 4 = 22.
Torej: Začneš z vsakim elementom prve množice posebej in nato primerjaš če je kateri element naslednje množice enak kateremu koli elementu pred njim. Če začneš s 3: imaš 1*(3/1) možnosti, vendar se v množici C element 8 ponovi glede na množico B in zato *(2/1) - ker imaš naprej izbiraš en element med dvema elementoma množice C. Najbrž se bo dalo posplošit tudi za primere, ko je n=10.
Veliko jih je notri, še več jih je pa zunaj.
Bilijarde v šole! - Ivan Kramberger
Abnormal behaviour of abnormal brain makes me normal.
Bilijarde v šole! - Ivan Kramberger
Abnormal behaviour of abnormal brain makes me normal.
Zgodovina sprememb…
- spremenilo: whatever ()
whatever ::
Sicer pa tud mene zanima, če je možno skonstruirat splošno formulo za tole. Ajde mastermindi, da vas vidim!
Veliko jih je notri, še več jih je pa zunaj.
Bilijarde v šole! - Ivan Kramberger
Abnormal behaviour of abnormal brain makes me normal.
Bilijarde v šole! - Ivan Kramberger
Abnormal behaviour of abnormal brain makes me normal.
molotov ::
Hm mogoče ne sestaviš niti en vektor.
ciki57 >> ...Med množicami pa se lahko elementi ponavljajo (ali pa tudi ne)...
Za ta navodila se nada sestavit formule, kar pač lahko imaš npr. 2 enaki množici.
edit: ups sm spregledal, da imajo množice različno št. elementov, sry
ciki57 >> ...Med množicami pa se lahko elementi ponavljajo (ali pa tudi ne)...
Za ta navodila se nada sestavit formule, kar pač lahko imaš npr. 2 enaki množici.
edit: ups sm spregledal, da imajo množice različno št. elementov, sry
Zgodovina sprememb…
- spremenil: molotov ()
ciki57 ::
Ja če imaš recimo a = {1}, b = {1} se ne da sestavit vektorja, ampak v tem primeru bi formula pač morala vrniti 0. 
Vredno ogleda ...
| Tema | Ogledi | Zadnje sporočilo | |
|---|---|---|---|
| Tema | Ogledi | Zadnje sporočilo | |
| » | Baza v vektorskem prostoruOddelek: Šola | 2643 (1141) | BivšiUser2 |
| » | [c++] nalogeOddelek: Programiranje | 6248 (4788) | technolog |
| » | Računanje matrične enačbeOddelek: Šola | 6430 (5990) | soulfly |
| » | Surjektivno + Injektivno = Bijektivno ... huh!?Oddelek: Šola | 13264 (8015) | Math Freak |
| » | 1+1=3 ? (strani: 1 2 )Oddelek: Šola | 14486 (12003) | redo |