Don, if you are talking about cards ordering then it will be n! which looks pretty high to compute ( consider even for n=10). and then for every count , you will need to compute every single color and values , i.e. worst case will be 25 n! ~ O(n!) . Can we do better ?
On Wednesday, 2 July 2014 01:20:07 UTC+5:30, Don wrote: > > Initially there are 5! = 120 possible orders for the cards. You should ask > for the hint which will reduce that number by the largest amount. So in > your example above, asking which cards have value 1 would not reduce the > number at all. Asking which card is Green would reduce the possible orders > to 24. The algorithm is to make a list of the possible orders. Then for > each question, count the number of orders in the list would give each > possible answer. The largest count is the score for that question. Ask the > question with the smallest score. Then based on the answer, remove any > orders from the list which are not consistent with that answer. Repeat the > process until you have only one order remaining. > Don > > On Tuesday, July 1, 2014 12:15:14 PM UTC-4, vikas wrote: >> >> One of my friend posted this question to me and I am unable to get >> anywhere. Could you guys please help >> >> A game of cards has 5 colors and 5 values. Thus a total of 25 cards are >> possible. Player 1 will choose n cards and tell you exactly , what all >> cards he has. Then he will spread cards in front of you with face downwards >> in random fashion. >> So you know the card values but not the ordering. Player 1 will provide >> you 2 types of hints , he can tell you what all cards have some color or he >> can tell you what all cards have some value. you need to tell the ordering >> of cards with the help of these hints. >> challenge is to find out minimum number of hints to be provided by player >> 1 so that you are able to make it for all cards. >> >> e.g. say player chosen n=5 cards >> and tells you the values >> >> B1 Y1 W1 G1 R1 >> >> he can either tell you that what all cards are 1 (in this case all cards) >> or can tell you different color like leftmost is color 'B" and next after >> 'Y' and so on. So minimun hints in this case is 4 >> >> >> another example >> if n=4 >> G4 R3 R4 B3 >> >> Here he can tell you the card 1st and 3rd are of values 4 and cards 2 >> and 3 are of color 'R'. This will be sufficient to infer the card values. >> so answer is 2 >> >> >> I am not interested in code , please suggest plain simple algorithms, if >> possible with arguments that why it is correct ? >> >> -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
