Count the number of possible permutations of numbers less than an integer N, given the N-1 constraints
We are given an integer N
, and we need to calculate the total number of substitutions for numbers less than N. We have also given constraints N-1
. eg:.
if N=4
, then count permutations 0,1,2,3
:
0>1
0>2
0>3
I thought about creating a graph, and then I would count the total number of permutations of numbers at one level and multiply it by the permutations at another level. For example:
In the above example:
0
/ | \
/ | \
1 2 3 ------> 3!=6 So total no of permutations are 6.
But I find it difficult to implement it in C++
. In addition, this question was asked in the Facebook hacker cup, the contest is over. I saw other people's code and found that they did it using DFS
. Any help?
source to share
The easiest way to do this is to use a standard permutation generator and filter out every permutation that violates the conditions. This is obviously very inefficient and is not computable for large N values. Doing this is the sort of "chatty" option these contests have that allows less intelligent contestants to solve the problem.
A skilled approach requires an understanding of how to count combinations and permutations. To illustrate the method, I'll use an example. Inputs:
N = 7
2 < 4
0 < 3
3 < 6
First, let's simplify this by combining the dependent conditions into one condition, as follows:
2 < 4
0 < 3 < 6
Start with the longest term and define a combination of whitespace counters (this is a key understanding). For example, some of the following combinations:
XXXX036
XXX0X36
XXX03X6
XXX036X
XX0XX36
etc.
Now you can see there are 4 spaces :? 0? 3? 6 & le ;. We need to calculate the possible partitions of X in these four spaces. The number of such sections is (7 choose 3) = 35 (can you see why?). Now, further, we multiply by the combination of the following condition, which is equal to 2 <4 over the remaining blank spots (Xs). We can multiply since this condition is completely independent of the condition 0 <3 <6. This is the number of combinations (4 choose 2) = 6. The final condition has 2 values in 2 spots = 2! = 2. So the answer is 35 x 6 x 2 = 420.
Now let's make it a little harder. Add a condition:
1 < 6
How this will change the calculation is what before 036 should have appeared in that order. But now we have three possible options:
1036
0136
0316
So the total number of samples is now (7 select 4) x 3 x (3 select 2) = 35 x 3 x 3 = 315.
So, to repeat, the procedure is that you isolate the problem in independent conditions. For each independent condition, you calculate the partition combinations, then you multiply them together.
I went through this example by hand, but you can program the same procedure.
source to share