Very thanks Mr. Balaz.
The really situation is : I must to make a program that manage this
"exchange cards problem" and I did not have any idea how to attack
this problem. I need to know how put the card's numbers into a
structure that a search to a desired/recurring item at least run in
time no more than O(n) or O(n.m). And the people's Universe quantity
that will to use this program is big (more than 1.000), this structure
need be clean to use no much memory.
I'm thinking to make this structure like "maximum priority queue"
using pointer to array to store the collection's numbers, and use the
"backtracking algorithm" to do a search mechanism. What do You think
about this my solution ? Is It will do what I want ?
Regards.
2009/2/18 Miroslav Balaz <gpsla...@googlemail.com>:
> This is not algorithm problem, it is homework problem do it yourself.
>
> I see there one problem, and it is how large is N
>
> I suggest you to represent sets as pairs(cardID,repeat number )
> that means for each card you remember number of how much you have of that
> card, and when there is zero, it means you desire to have it.
> But this approach assumes that you will keep at least one card, and will not
> want ot have card twice.
>
> The interesting would be problem to exchange cards in way to maximize
> desired cards received by all players. But this would need one player to
> have card that he does not desire.
>
> 2009/2/17 Luciano Pinheiro <luciano....@gmail.com>
>>
>> I have several collections of cards (baseball league, championship
>> bascketball, etc..), Where each collection C (i) is numbered from 1 to N,
>> 1 <=
>> i <= |C|, where |C| = total number of collections that I have. I heve too
>> many
>> friends, F, that I can make exchange my recurring cards with their
>> derised cards.
>>
>> For each collection C (i) have a repeated set (R(i)) of cards to share
>> with my
>> friends. Repeated this set of cards, I have cards with the same number, or
>> only a single card repeated. And I also have relations of the cards I need
>> (desired items D(i)) to fill my collection C(i).
>>
>> For example:
>> I have follow card's collections:
>> 2000 Baseball Cards - numbers (1, 2, 3, 4, 5, 6, 10, 23, 45)
>> recurring items (1, 1, 2, 5, 5, 6, 23, 23)
>> items desired (7, 8, 9, 11, 12, 13, 14, 15, 16,
>> 17, 18, 19, 20, 21, 22, 23,
>> 24,
>> 25, .. , 44)
>>
>> 2000 Bascketball Cards - numbers (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 15,
>> 17,
>> 18, 20, 23, 30, 33,
>> 36, 47)
>> recurring items (1, 2, 2, 4, 4, 5, 10, 12, 23,
>> 23)
>> items desired (11, 13, 14, 16, 19, 21, 22,
>> 24,
>> 25, .. , 29, 31,
>> 32, 34, 35, 37, .. , 46)
>>
>> I have two friends (John and Mary) whom I exchange the cards I need. Each
>> of
>> these friends also have collections of cards and collection of cards for
>> each
>> of them, they repeated a set of cards and a list of cards you want.
>>
>> My friend Mary's card's collections is:
>> 1999 Baseball Cards - numbers (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16,
>> 18,
>> 20, 21, 22, 23, 24,
>> 25, 27, 29, 30, 33, 36,
>> 38, 39, 40, 41, 42, 43,
>> 44, 45)
>> recurring items (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14,
>> 16,
>> 18, 23, 42, 43)
>> items desired (9, 11, 13, 15, 17, 19, 26, 28, 31,
>> 32,
>> 34, 35, 37)
>>
>> 2000 Baseball Cards - numbers (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,
>> 13,
>> 14, 15, 16, 17, 18,
>> 19, 20, 21, 22, 23, 24,
>> 25, 27, 29, 30, 31, 32,
>> 33, 34, 35, 36, 37,
>> 38, 39, 40, 41, 42, 43,
>> 44, 45)
>> recurring items (1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 12, 13,
>> 14, 18, 19, 19, 19, 22, 22, 23,
>> 24,
>> 27, 27, 29, 30, 31, 32,
>> 35, 35, 36,
>> 39, 40, 44, 45)
>> items desired (26, 28)
>>
>> Mary's friend John's card's collections is:
>> 2000 Baseball Cards - numbers (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16,
>> 18,
>> 20, 21, 22, 23, 24,
>> 25, 27, 29, 30, 33, 36,
>> 38, 39, 40, 41, 42, 43, 44,
>> 45)
>> recurring items (1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14,
>> 16,
>> 18, 23, 42, 43)
>> items desired (9, 11, 13, 15, 17, 19, 26, 28, 31,
>> 32,
>> 34, 35, 37)
>>
>> 2000 Bascketball Cards - numbers (1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 14,
>> 15,
>> 16, 17, 18, 19,
>> 20, 21, 22, 23, 24, 25,
>> 27, 29, 30, 31,
>> 32, 33, 34, 38, 39, 40,
>> 41, 42, 43, 44, 45)
>> recurring items (1, 1, 1, 2, 3, 4, 5, 5, 6, 6, 12,
>> 13, 14, 18, 19, 19, 19,
>> 22, 24, 27, 27, 29,
>> 30, 31, 32, 35, 39, 40, 44,
>> 45)
>> items desired (7, 8, 9, 26, 28, 35, 36, 37)
>>
>> Let C collections set:
>> C = {2000 Baseball Cards, 2000 Bascketball Cards, 1999 Baseball Cards)
>>
>> Let F people set that will exchange cards is:
>> F = {Me, John, Mary}
>>
>> have this collections
>> Where : Me = P[1] = {2000 Baseball Cards, 2000 Bascketball Cards}
>> John = P[2] = {2000 Baseball Cards, 1999 Baseball Cards}
>> Mary = P[3] = {2000 Baseball Cards, 2000 Bascketball Cards}
>>
>> My "2000 Baseball Cards" collection have bellow sets:
>> numbers that I have N[1] = (1, 2, 3, 4, 5, 6, 10, 23, 45)
>> recurring items R[1] = (1, 1, 2, 5, 5, 6, 23, 23)
>> items desired D[1] = (7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18,
>> 19,
>> 20, 21, 22, 23, 24, 25, .. , 44)
>>
>> I need the follow John's recurring cards: (12, 13, 14, 18, 19, 22, 23, 24,
>> 27,
>> 29, 30, 31,
>> 32, 35, 36, 39, 40, 44)
>> And I need too the follow Mary's recurring cards: (15, 17, 26, 28, 34, 43)
>>
>> Then, after these exchanges, my new desired set is : (7, 8, 9, 11, 16, 20,
>> 21,
>>
>> 25, 33, 37, 38, 41, 42)
>>
>> Whereas this example we have only three people involved, and only three
>> collections of cards for each one, asking for that:
>>
>> 1. Create an abstract method to handle | F | people involved in
>> relationships
>> of exchange with | C | collections of cards for each one;
>>
>> 2. Develop a data structure that facilitates the search for desired items;
>>
>> 3. Make routines at run time at most O (n. m), where n = | C | and m = | F
>> |.
>>
>>
>
>
> >
>
--
----------------------------------------
Luciano Soares Pinheiro Jr.
Analista desenvolvedor Sr.
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
