// This function returns the number of hints required to
// determine the order of the cards.
// Parameter int c[n] specifies n cards which are provided
// in an unknown order. Each card is represented as a 10-bit field
// with two bits set, one representing the color of the card and the
// other r
Here is a fairly simple way to find a solution.
Make a list of each pair of the n cards which have been selected. This list
can include up to 300 pairs. Represent each card as a 10-bit value where
each bit represents one particular color or value. Thus, each card will
have two bits set. Each pa
There are a total of 10 hints which can be asked for.
If you ask for 4 colors and 4 values, you can deduce the remaining color or
value by a process of elimination, so the most hints you will ever need is
8.
You may not need all eight hints, if every card can be distinguished from
every other
As soon as you get one hint, the number of orders drops greatly. Your first
question should be to ask about the color or value which occurs closest to
n/2 times. When you ask about that, the number of possible orders will be
much smaller, and you can continue with just that list. The problem was
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
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
