Algorithm

 Problem Statement for Deranged

 

problem link- https://community.topcoder.com/stat?c=problem_statement&pm=2013

Problem Statement
     A derangement of n numbers is a permutation of those numbers in which none of the numbers appears in its original place. For example, the numbers {1,2,3} can be deranged into {2,3,1} and {3,1,2}. We can modify this slightly for n numbers that are not necessarily distinct by saying that no number in the derangement can be in the place that a number of the same value was in in the original ordering. So the numbers {1,1,2,2,3} could be deranged into {2,2,1,3,1}, {2,2,3,1,1}, {2,3,1,1,2}, and {3,2,1,1,2}. Create a class Deranged with a function numDerangements that takes a int[] nums and return the number of derangements of nums.
 

Definition
    
Class: Deranged
Method: numDerangements
Parameters: int[]
Returns: long
Method signature: long numDerangements(int[] nums)
(be sure your method is public)
    
 
 

Notes
- The return value will fit in a 64-bit unsigned integer.
 

Constraints
- nums will contain between 1 and 15 elements, inclusive.
- nums will only contain values between 0 and the number of elements in nums - 1, inclusive.
 

Examples
0)  
     
{1,1,2,2,3}
 
Returns: 4
The example from above.
1)  
     
{0,0,0,1,1,1}
 
Returns: 1
The only derangement is {1,1,1,0,0,0}.
2)  
     
{0,0,0,1,1,1,1}
 
Returns: 0
There is no way to arrange the numbers such that no 1 is where a 1 was originally.
3)  
     
{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2}
 
Returns: 14
 
4)  
     
{0,5,4,2,3,6,6}

Returns: 640
 
5)  
     
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}
 
Returns: 481066515734

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

class Deranged {
public:
  static long long dp[(1 << 16)][16];

  long long numDerangements(vector <int> nums) {
    sort(nums.begin(), nums.end());
    memset(dp, -1, sizeof dp);
    long long ret = rec(0, 0, nums);

    int fr[16] = {0};
    for(int i = 0; i < nums.size(); ++i)
      ++fr[nums[i]];

    for(int i = 0; i < 16; ++i)
      ret /= fact(fr[i]);

    return ret;
  }
  
  long long rec(int idx, int msk, vector<int>&nums) {
    if(__builtin_popcount(msk) == int(nums.size()))
      return 1;

    long long &ret = dp[msk][idx];
    if(ret != -1)
      return ret;
    ret = 0;
    
    for(int i = 0; i < nums.size(); ++i)
      if(((msk >> i) & 1) == 0 && nums[idx] != nums[i])
        ret += rec(idx + 1, msk | (1 << i), nums);
    
    return ret;
  }

  long long fact(int x) {
    long long f = 1;
    for(int i = 2; i <= x; ++i)
      f *= i;
    return f;
  }
};

long long Deranged::dp[][16] = {0};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
{1,1,2,2,3}

Output

x
–
+
cmd
4
Advertisements

Demonstration

TopCoder Solution SRM176-D1-500  Problem Statement for Deranged C,C++, Java, Js and Python ,SRM176-D1-500