CODEWITHSUNDEEP
c++algorithmcountpermutation
Enigma
Enigma

Reputation: 189

Finding the permutation that satisfy given condition

I want to find out the number of all permutation of nnumber.Number will be from 1 to n.The given condition is that each ithposition can have number up to Si,where Si is given for each position of number.

1<=n<=10^6
1<=si<=n

For example:

n=5

then its all five element will be 

1,2,3,4,5

and given Si for each position is as:

2,3,4,5,5

It shows that at: 1st position can have 1 to 2that is 1,2 but can not be number among 3 to 5. Similarly, At 2nd position can have number 1 to 3 only. At 3rd position can have number 1 to 4 only. At 4th position can have number 1 to 5 only. At 5th position can have number 1 to 5 only. Some of its permutation are:

1,2,3,4,5
2,3,1,4,5
2,3,4,1,5 etc.

But these can not be:

3,1,4,2,5  As 3 is present at 1st position.
1,2,5,3,4  As 5 is present at 3rd position.

I am not getting any idea to count all possible number of permutations with given condition.

Upvotes: 0

Views: 731

Answers (4)

Treziac
Treziac

Reputation: 3264

To complete Yuriy Ivaskevych answer, if you don't know if the sis are in increasing order, you can sort the sis and it will also works. And the result will be null or negative if the permutations are impossible (ex: 1 1 1 1 1)

Upvotes: 0

Yuriy Ivaskevych
Yuriy Ivaskevych

Reputation: 966

Okay, if we have a guarantee that numbers si are given in not descending order then looks like it is possible to calculate the number of permutations in O(n).

The idea of straightforward algorithm is as follows:

  1. At step i multiply the result by current value of si[i];
  2. We chose some number for position i. As long as we need permutation, that number cannot be repeated, so decrement all the rest si[k] where k from i+1 to the end (e.g. n) by 1;
  3. Increase i by 1, go back to (1).

To illustrate on example for si: 2 3 3 4:

  1. result = 1;
  2. current si is "2 3 3 4", result *= si[0] (= 1*2 == 2), decrease 3, 3 and 4 by 1;
  3. current si is "..2 2 3", result *= si[1] (= 2*2 == 4), decrease last 2 and 3 by 1;
  4. current si is "....1 2", result *= si[2] (= 4*1 == 4), decrease last number by 1;
  5. current si is "..... 1", result *= si[3] (= 4*1 == 4), done.

Hovewer this straightforward approach would require O(n^2) due to decreasing steps. To optimize it we can easily observe that at the moment of result *= si[i] our si[i] was already decreased exactly i times (assuming we start from 0 of course).

Thus O(n) way:

unsigned int result = 1;
for (unsigned int i = 0; i < n; ++i)
{
    result *= (si[i] - i);
}

Upvotes: 2

Abdennacer Lachiheb
Abdennacer Lachiheb

Reputation: 4888

for each si count the number of element in your array such that a[i] <= si using binary search, and store the value to an array count[i], now the answer is the product of all count[i], however we have decrease the number of redundancy from the answer ( as same number could be count twice ), for that you can sort si and check how many number is <= s[i], then decrease that number from each count,the complexity is O(nlog(n)), hope at least I give you an idea.

Upvotes: 0

Alex Banu
Alex Banu

Reputation: 18

You can try backtracking, it's a little hardcore approach but will work. try: http://www.thegeekstuff.com/2014/12/backtracking-example/ or google backtracking tutorial C++

Upvotes: -1

Related Questions