We are given array-'a' and array-'b' consisting of positive integers. How can I count all the permutation of array 'a' which are strictly lexicographically smaller than array-'b' ?

Size of array can be as large as 10^5 and the integers it contains can also be large, but less than equal to 100000.

Thanks :)

Input : 3

1 2 3

2 1 3

Output : 2

Only permutations 1,2,3 and 1,3,2 are lexicographically smaller than 2 1 3

  • $\begingroup$ integers or digits? $\endgroup$ – gt6989b Jan 24 at 17:03
  • $\begingroup$ integers in the range : [1 to 100000] $\endgroup$ – Firex Firexo Jan 24 at 17:04
  • $\begingroup$ Can you give a small example of what you are trying to count? $\endgroup$ – Dubs Jan 24 at 17:29
  • $\begingroup$ I have added it in the question :-) $\endgroup$ – Firex Firexo Jan 24 at 17:32

I don't think you will find a formula for this, but if you want to use a computer to do the calculations this may help.

Suppose the integers are in the range $[1 - r]$ for some positive integer $r$ and suppose the $b$-array contains the integers $b_1, b_2,\ldots$ then let $c_i$ for $i=1,2,\dots$ be the number of $a$-arrays of length $n$. Clearly:

$$c_1 = b_1 - 1$$

Now suppose you have caculated $c_n$. We can calculate $c_{n+1}$ by considering the possible extensions of the $a$-array by one integer. One of the possible $a$-arrays, namely $[b_1-1, b_2-1,\ldots b_n-1]$, is critical in the sense that if it is extended with a value $a_{n+1} \ge b_{n+1}$ then the resulting $a$-array will no longer be below the $b$-array in the lexical order. So it has only $b_{n+1}-1$ possible extensions. All the other possible $a$-arrays have $r$ possible extensions. Thus we have the following formuls for $c_{n+1}$:

$$c_{n+1}=r(c_n-1) + b_{n+1}-1$$

Using these formulas iteratively you can calculate $c_n$ for any value of $n$.

  • $\begingroup$ Sorry I misread the question! I'll have another think about it. $\endgroup$ – Bernard Hurley Jan 25 at 4:54

If the first element of the permutation is strictly less than the first element of b, the rest of the elements can be in any order, so if $a$ has $k$ elements less than the first element of $b$ and $n$ elements total, this contributes $k(n-1)!$. If the first element of the permutation is the same as the first element of b, erase that element from each array and do the calculation for the reduced arrays.

As an example, let $a=\{1,2,3,4,5,6,7\}$ and $b=(3,4,0,8)$ There is no need for the two lists to have the same characters or the same number of characters. Since $a$ has two numbers less than $3$, there are $2\cdot 6!$ permutations of $a$ that come before $b$ because they start with $1$ or $2$. There are also some that start with $3$, which is when the permutation of $\{1,2,4,5,6,7\}$ comes before $(4,0,8)$. There are $2\cdot 5!$ that start with $1$ or $2$. We later find there are none that start with $4$ because of the zero.

  • $\begingroup$ @BernardHurley: I read $b$ to be a list of numbers, not just one. I want to erase the first number in $b$, not all of them. $\endgroup$ – Ross Millikan Jan 25 at 5:16
  • $\begingroup$ This is essentially correct. However it might be better to say "erase $b$ from the list of numbers to be processed". The point being that we are merely considering the numbers to be an ordered list so we end up with the formula: $$\sum_{i=1}^n(b_i^\ast - 1)(i - 1)!$$ where $$b_i^\ast=b_i-\sharp\{b_r : r<i\ \mbox{and}\ b_r<b_i\}$$ for each $i$. $\endgroup$ – Bernard Hurley Jan 25 at 5:39
  • $\begingroup$ That only works if all the integers in the both the arrays are distinct :( $\endgroup$ – Firex Firexo Jan 25 at 7:47

If there are $n$ numbers and the $b$-array is: $$[b_1,b_2,\ldots b_n]$$ Then the formula for the number of permutations is: $$\sum_{i=1}^n(b_i^\ast - 1)(n-i)!$$ where: $$b_i^\ast=b_i-\sharp\{b_r : r<i\ \mbox{and}\ b_r<b_i\}$$ for each $i$.

  • $\begingroup$ That only works if all the integers in the both the arrays are distinct :( $\endgroup$ – Firex Firexo Jan 25 at 7:47
  • $\begingroup$ Why do you say that? $\endgroup$ – Bernard Hurley Jan 25 at 8:13
  • $\begingroup$ Oh, I see what you are saying. I had read the question as permutations of numbers, but you actually want permutation of the elements of an array which could start out as, say: $$[12, 2, 3, 4, 2, 4,\ldots]$$ $\endgroup$ – Bernard Hurley Jan 25 at 10:03
  • $\begingroup$ yup :( :( :( :( :( $\endgroup$ – Firex Firexo Jan 25 at 12:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.