SPOJ PERMUT1

From Algorithmist
Jump to navigation Jump to search

64. Permutations[edit]

http://www.spoj.pl/problems/PERMUT1/

Summary[edit]

Calculate the total number of permutations containing the specified number of inversions.

Explanation[edit]

First, let us denote the number of n-element permutations with exactly k-inversions as . One way to compute this function would be to generate all n-element permutations, and then count the ones that contain inversions. While this approach will give the correct result, it is highly inefficient since there is a total of permutations. Fortunately, some analysis of the problem reveals a nice property, and that is if we can compute where , then we can insert the (largest) element somewhere in each permutation so that the resulting number of inversions is , thus if we sum all the values of that satisfy the condition, we would have computed . Having said that, we can come up with the following recurrence:

Notes:

  • If n = 0, then there are no permutations at all.
  • There is only one permutation with 0 inversions, and that is the permutation where the elements are sorted in increasing order.
  • The maximum number of inversions in a n-element permutation is , and that is the permutation where the elements are sorted in decreasing order.
  • The maximum number of inversions that can be obtained from some (n-1)-element permutation can be obtained by appending the nth element to the front of the permutation.
  • Only the large enough values of need to be included in the sum. For example if we wanted to compute , then we only need to compute , , and . will not be included, since is the permutation {1, 2}, and the maximum number of inversions that can be obtained after inserting the third element in the permutation is 2, thus it will be impossible to obtain the required number of inversions from that permutation.

    Implementation[edit]

    Some experimentation with the above recurrence will show that some of the subproblems will overlap, thus in order not to keep recomputing values, it is best to create a matrix of appropriate size to hold any already computed values, and look them up when needed.

    Here is C/C++ code:

    int count(int n, int k)
    {
    	if(n == 0)
    		return 0;
    	if(k == 0)
    		return 1;
    	if(dp[n][k] != -1)
    		return dp[n][k];
    	int val = 0;
    	for(int i = 0; i < n && k-i >= 0; i++)
    		val += count(n-1,k-i);
    	return (dp[n][k] = val);
    }
    

    Note:

    The array dp is a global variable and initialized with -1s.

    Input[edit]

    The number of test cases is specified on the first line. Each test case consists of two numbers. The first 1 <= n <= 12 is the number of elements and the second 0 <= k <= 98 is the number of inversions to find.

    1
    4 1
    

    Output[edit]

    3
    

    External Links[edit]

  • Dynamic Programming - Wiki Link
  • Dynamic Programming Tutorial - Topcoder.com
  • Cut The Knot - Listing permutations