I came out with the explanation.
Why permutation tests are biased in favor of those categorical variables with a large number of levels?
If the range of a variable is small, a permutation of the values will return a similar vector. Therefore, the permutation test concludes that this variable does not give enough information because the score is similar with or without permutation. For example, if the original binary vector is [0 1 0 1 1 1 0 0] and the permuted one is [1 1 0 0 1 0 0 1], 50% of the values are unchanged, which is harder to occur if the variable has more levels.
Can a partial permutation solve the bias problem?
In the partial permutation, only a fraction of the values are shuffled, this percentage is named as the permutation ratio. For each position within the vector, it is considered that a collision occurs when the value in the original and permuted vectors are the same. Thus, the higher the collision probability, the higher the similarity between original and permuted vector. If the permutation ratio is zero, the collision probability is 1 because original and permuted variables are the same. When the ratio is one, we are applying a regular permutation where all the values are permuted. The literature proposes a permutation ratio of 0.2 that leads a range of collision probability between 0.9 and 0.8.
For example, we have the 8-elements original vector [1 2 3 4 3 2 1 0] with a permutation ratio of 6/8=0.75; hence, for simplicity, the last two values are not shuffled. We create our statistics from three permuted vectors, namely [2 4 3 1 2 3 1 0], [1 3 4 3 2 2 1 0] and [2 3 2 3 2 1 1 0]. The permuted vectors have 3, 4 and 2 collisions, respectively. Hence, the collision probability is (3+4+2)/(3*7)=0.375.
In the plot, the collision probabilities have been obtained through simulations over 1000 permutations for each configuration. Each line corresponds to a different dimension, number of values that the variable can take, e.g. a dimension of 2 implies a binary variable.