dev.gamez.lv Forum Index dev.gamez.lv
Latvian Game Developers Community
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 

Ciparu grupeesana

 
dev.gamez.lv Forum Index -> Programmēšana
View previous topic :: View next topic  
Author Message
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: 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" Laughing 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
View user's profile
elvman
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga

PostPosted: 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
View user's profile Visit poster's website
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: 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
View user's profile
elvman
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 09 Apr 2003
Posts: 1278
Location: Kuldiga

PostPosted: 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
View user's profile Visit poster's website
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: Tue Jun 10, 2008 3:40 pm    Post subject:

Lol ne jau parastas kombinatorikas formulas es prasu man jau nevajag saskaitiit cik buus kombinaacijas Laughing 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
View user's profile
Vecais_Dumais_Laacis
Guru
Guru


Joined: 29 Jan 2004
Posts: 800

PostPosted: 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
View user's profile
bubu
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 23 Mar 2004
Posts: 3223
Location: Riga

PostPosted: 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:
Code:

1 2 3 X
4 5 6 X

?
Back to top
View user's profile Send e-mail
bubu
Indago Uzvarētājs
Indago Uzvarētājs


Joined: 23 Mar 2004
Posts: 3223
Location: Riga

PostPosted: 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
View user's profile Send e-mail
Storm



Joined: 11 Apr 2006
Posts: 742

PostPosted: 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
View user's profile
Display posts from previous:   
dev.gamez.lv Forum Index -> Programmēšana All times are GMT + 2 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group