I thing you the only choice, is binary search tree, but it is the most obvious one. It imposible to make it independent form cards universe,as far as i know but it can be made int time O(log(nmU)),where U is number of cards, it is much less than O(n). But you must think about what is the problem, if it is that you want to find for given card find someone who just have it repeated. jus make som new object and carefuly write comparator for it, I dont know what language you use, i am C++, it i have experience with that.
But if you want to just greedy exchange the cards, you cen put then as tupes in array, sort them by cardID. but you alsomust add "card request" to that array. where cardID is some unique identifier consisting of collection number, and number of collection. but again i must point out, that you said that m=number of collections, n=number of cards.so O(n.m) does not consider cards number. 2009/2/20 Luciano Pinheiro <[email protected]> > > 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 tak > 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 <[email protected]>: > > 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 <[email protected]> > >> > >> 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 [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
