Hello again Mr. Balaz,
I`m writting to thank You very, very so much about yours information,
that give "the path of stones" to solution my problem.
I think very well in this weekend and I came to this conclusion:
All collections have a number maximum limit MAX (C), where MAX (C) ≤
2000 for each collection c . And the recurring item set don`t have at
all collection number, and the same happen with desired item set. For
example:
Let T(R) = | R | , where R is recurring item set, and
Let T(D) = | D | , where D is derired item set.
Into a any collection c, T(R) + T(D) ≤ MAX (C), because someone that
have a desired item set, don`t have all collection numbers; and about
the recurring item`s set, if this guy have some recurring item`s set
that take all collection numbers, this situation make a conversion to
change this consideration : R = C.
Therefore, I can use two binary search trees: one to indicate a
desired item`s set B(D), and another to indicate the recurring item`s
set B(R), for each person. In each binary tree, the key will be a
compound by this formula:
To B(D): key = d + c, where d is d-th desired item and c is c-th collection;
To B(R): key = r + c, where r is r-th recurring item.
To sort these trees, I think I will use the radix sort, getting a
unsigned long data type to represent the key field into each tree,
where the first part of composite key get the two highest bytes, and
another composite key get the two another lowest bytes of the data
type .
Using this technique, I hope get some performance in my program. What
do You think Mr. Balaz ?
2009/2/20 Miroslav Balaz <gpsla...@googlemail.com>:
> 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 <luciano....@gmail.com>
>>
>> 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 <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.
>>
>>
>
>
> >
>
--
----------------------------------------
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
-~----------~----~----~----~------~----~------~--~---
