Problema algoritmico: Picking Cards

Ecco una rapida implementazione in java. L'idea è di scoprire quante carte possono essere prese ogni passo contando il numero di carte con un numero sotto questo passo e sottraendo il numero di carte già pescate. Ovviamente un sacco di lavoro viene ripetuto inutilmente, ma questo dovrebbe dare una buona idea di come affrontare questo problema.

public class PickCards {
public static int countLessOrEqualThanMax(int[] cards, int max) {
    int count = 0;
    for (int number : cards) {
        if(number <= max) count++;
    }
    return count;
}

public static void main(String[] args) {
    int[] cards = {0, 1, 2, 4, 3};
    int numberOfWays = 1;
    for(int i = 0; i < cards.length; i++) {
        int ways = Math.max(0, countLessOrEqualThanMax(cards, i) - i);
        numberOfWays *= ways;
    }
    System.out.println(numberOfWays);
}

}

Come punto di partenza, nel caso in cui tutte le carte siano zero:

Output = N!

Ad esempio:

Input di esempio: 0 0 0

Output di esempio: 3 x 2 x 1 = 6.

Chiaramente, qualsiasi carta con un numero superiore a 0 ridurrà il numero di possibili modi di raccogliere le carte.

Qualsiasi carta con "N" su di essa renderà impossibile prendere le carte.

Modifica:

Considera N = 4 carte dove:

A = 0, B = 0, C = 1, D = 2

C non può apparire nella colonna 1. D non può apparire nella colonna 1 o 2.

1. A, B, C, D - Y
2. A, B, D, C - Y
3. A, C, B, D - Y
4. A, C, D, B - Y
5. A, D, B, C - N

6. A, D, C, B - N

7. B, A, C, D - Y

8. B, A, D, C - Y
9. B, C, A, D - Y
10. B, C, D, A - Y
11. B, D, A, C - N

12. B, D, C, A - N

13. C, A, B, D - N

14. C, A, D, B - N
15. C, B, A, D - N
16. C, B, D, A - N
17. C, D, A, B - N

18. C, D, B, A - N

19. D, A, B, C - N

20. D, A, C, B - N
21. D, B, A, C - N
22. D, B, C, A - N
23. D, C, A, B - N
24. D, C, B, A - N

L'algoritmo in pseudocodice non è efficiente, ma troverà TUTTI i casi

   //Create an array that stores card number, 
   //position, and a flag that denotes it is picked or not, 
   //initialize with not picked:
   (1, 10 , false) , ( 2, 9, false) .....

   // try to pick each item in array, 
   // and spawn a new sub-process tree for each possible move
   trypick(ARRAY)
   // try all cards one by one
   for i = 1 until N 
       if ARRAY[i].ispicked 
           // just skip it if its already picked
           do nothing 
       else
           // if its pickable hurray, but we are not 
           // generating a sub-process tree if it is not a valid case
           if ARRAY[i].number <= ARRAY[].Count(ispicked) 
               // pick it
               ARRAY[i].ispicked = true
               // spawn a new array tree for each possible 
               // move for the subtree generated
               trypick(ARRAY)  
   if ARRAY[].Count(ispicked) = N
       // we have picked all cards, lets ad plus one to our total
       totalways++