View previous topic :: View next topic |
Author |
Message |
Storm
Joined: 11 Apr 2006 Posts: 742
|
Posted: Tue Jun 10, 2008 2:28 pm Post subject: Ciparu grupeesana |
|
Ir taada probleeminja, ka ir noteikts skaits simbolu (ciparu) un ir grupas pa 4 kuraas ir no 1-4 simboli no dotajiem, piemeeram :
1, 2, 3, 4, 5, 6
1 2 5 X
2 5 X X
2 3 5 6
1 5 X X
2 4 6 X
1 2 3 X
2 4 5 6
2 3 4 5
Un vajag sagrupeet so te peec iespeejas lielaakaas grupaas. X noziimee undefined, ti simbols nav noteikts... Seciiba nav noteikta, galvenais ka grupinja satur simbolu.
Es gan pierakstiiju pilnu "new text document" ar visaadaam mahinaacijaam, tomeer pie reaala algoritma nenonaacu, varbuut kaads var paliidzeet ^^
Visas idejas more than welcome!
P.S Varu arii piedaavaat garaaku virkni, ja nepieciesams testeesanai
http://pastebin.org/42826 _________________ Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552 |
|
Back to top |
|
|
elvman Indago Uzvarētājs
Joined: 09 Apr 2003 Posts: 1278 Location: Kuldiga
|
Posted: Tue Jun 10, 2008 2:39 pm Post subject: |
|
Nu taa ir parastaa kombinatorika. Panjem kombinatorikas formulas un uzgjeneree visas iespeejamaas variaacijas (cik es saprotu, tad sheit ir bez atkaartojumiem un seciiba ir svariiga) _________________ long time; /* know C */ |
|
Back to top |
|
|
Storm
Joined: 11 Apr 2006 Posts: 742
|
Posted: Tue Jun 10, 2008 2:47 pm Post subject: |
|
Seciiba nav noteikta... Kombinatorika maibii, bet man vajag atrast minimaalo daudzumu 4 simbolu virkniites kuras speej atteelot visus dotos gadiijumus...
Apmeeram
piem virnkiite
1 2 5 7 speej atteelot jebko kas satur 1, 2, 5, 7 un nespeej atteelot neko kas satur kaadu citu simbolu...
piem speej:
1 5 X X
7 X X X
1 5 2 7
nespeej:
1 2 5 6
2 3 X X
7 5 4 3
Nu jaa, izdomaaju vienu variantu, vnk nemot visas kombinaacijas peec kaartas un skatoties kurai lielaaks "score" (vairaak deriigie gadiijumi), atrodam vislabaako kombinaaciju, iznemam visus deriigos gadiijumus sai kombinaacijai aaraa, un atkaarto atkal kameer vairs neviens nav palicis... bet ja man buus piemeeram 12 dazaadi simboli tas vareetu buut traki... cik tur tas permutaacijas sanaak veel viesiem jaaizbrauc cauri un jaakonstatee der neder (vismaz 4 cheki katram gadiijumam)... _________________ Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552 |
|
Back to top |
|
|
elvman Indago Uzvarētājs
Joined: 09 Apr 2003 Posts: 1278 Location: Kuldiga
|
Posted: Tue Jun 10, 2008 3:37 pm Post subject: |
|
Nu baac. Es varu atkaartoties: elementaara kombinatorika. Tev var buut 1 simbols, 2 simboli, 3 vai 4. Taatad njem kombinaaciju formulu (n!/k!(n-k)!). Pirmkaart ir iespeeja, ka stringaa buus 1 simbols. Taatad: 4!/1!(4-1)! = 4. Tat njem 2 simbolus: 4!/2!(4-2)! = 6. Tad njem 3: 4!/3!(4-3)! = 4. Un 4: 4!/4!(4-4)! = 1. Saskaiti visu kopaa: 4+6+4+1 = 15. Redzkur tavs magjiskais skaitlis. _________________ long time; /* know C */ |
|
Back to top |
|
|
Storm
Joined: 11 Apr 2006 Posts: 742
|
Posted: Tue Jun 10, 2008 3:40 pm Post subject: |
|
Lol ne jau parastas kombinatorikas formulas es prasu man jau nevajag saskaitiit cik buus kombinaacijas Izlasi ko man vajag... _________________ Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552 |
|
Back to top |
|
|
Vecais_Dumais_Laacis Guru
Joined: 29 Jan 2004 Posts: 800
|
Posted: Tue Jun 10, 2008 4:09 pm Post subject: |
|
ja tev grupeejamajaas grupaas max elementu skaits ir 4
tad njem visas pilnaas grupas kuras ir dazhaadas -> viena neietver otru.
1 2 3 4
1 3 5 6
2 3 5 7
un meklee taalaak no paareejaam grupaam kuraam ir tikai 3 elementi kuras iekljaujaas esoshajaas
ja kaada neiekljaujaas tad to noliekam atsevishkji
tad njemam visas divu simbolu grupas un meegjinam iemaaniit 3 un 4 simbolu grupaas (pirmajaas atlasiitajaas un otrajaas malaa noliktajaas)
ja nesanaak tad liekam malaa
viena simbola grupas kuraas ir jauns simbols kursh nav nevienaa jau esoshajaa grupaa liekam malaa
taatad mums ir kaukaadas 4 simbolu grupas (kuraas ir sapluudushas dalja 3 un 2u simbolu grupas) un malaa noliktaas 3, 2, 1 simbolu grupas kuras nesader nekur citur
integreejam 2u simbolu grupas 3 simbolu grupaas veidojot 4u simbolu grupu (kur kaads no 2u simbolu grupas elementiem ir kaadaa no 3 simbolu grupaa)
integreejam 1 simbolu grupas atlikushajaas 3 simbolu grupaas shaadi veidojot 4u simbolu grupas
paari paliek 2 un 1 vai 3 simbolu grupas (atkariibaa kas ir vairaak 3 vai 1 simbolu grupas peedeejaa iteraacijaa)
ja ir palikushas 2 un 1 simbolu grupas tad vienkaarshi apvienojam
ja ir palikushas 2 un 3 simbolu grupas kas nav apvienojamas tad 2u simbolu grupas var apvienot pa paariem un taa arii beidzaas
nu cerams ka sapratiisi domu _________________ ...un ja bites buutu laachi... |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
Posted: Tue Jun 10, 2008 4:24 pm Post subject: Re: Ciparu grupeesana |
|
Storm wrote: | Un vajag sagrupeet so te peec iespeejas lielaakaas grupaas. |
Ko nozīmē "pēc iespējas lielākās grupās"?
Kas ir grupa? Es biju sapratis, ka grupa vienmēr ir 4 simbolus liela. Kā tad panāk vēl lielāku grupu?
Edit: ah sapratu. Tavā otrajā postā ir atbilde:
Quote: | bet man vajag atrast minimaalo daudzumu 4 simbolu virkniites kuras speej atteelot visus dotos gadiijumus... |
vdl: varbūt drusku neiebraucu, bet vai gadījumā tavs algoritms uz šādām virknītēm:
Code: | 1 2 3 4
1 2 3 5
1 2 3 X
4 5 6 X |
neatlasīs sekojošās trīs:
Code: | 1 2 3 4
1 2 3 5
5 4 6 X |
kautgan vajadzētu tikai sekojošās divas:
? |
|
Back to top |
|
|
bubu Indago Uzvarētājs
Joined: 23 Mar 2004 Posts: 3223 Location: Riga
|
Posted: Tue Jun 10, 2008 5:03 pm Post subject: |
|
Storm: tava problēma ir aprakstīta rekur: http://en.wikipedia.org/wiki/Set_cover_problem
Ir pierādīts, ka tā ir NP pilna problēma. Tātad optimāls algoritms būs ļoti ķēpīgs un lēns (like pilnā pārlase). |
|
Back to top |
|
|
Storm
Joined: 11 Apr 2006 Posts: 742
|
Posted: Tue Jun 10, 2008 5:07 pm Post subject: |
|
Actualy es jau taisiiju pilno paarlasi... Itkaa jau buutu ideaali ja tas buutu realtime gadiijums, bet offline arii derees, tikai tad nebuus tik effektiivi... Un vdl gadiijums atlasa pareizi, jo virkniitei X netiek pienjemts (ja vien vienkaarsi visiem elementiem ir 3 cipari un X piemeeram) _________________ Izraadaas ka dazu dev.gamez.lv lietotaaju absurdaa ignorance meedz eksisteet arii augstaakas paakaapees : http://www.gamedev.net/community/forums/topic.asp?topic_id=411552 |
|
Back to top |
|
|
|