Permutations with extra restrictions

Question

I have a set of items, for example: {1,1,1,2,2,3,3,3}, and a restricting set of sets, for example {{3},{1,2},{1,2,3},{1,2,3},{1,2,3},{1,2,3},{2,3},{2,3}. I am looking for permutations of items, but the first element must be 3, and the second must be 1 or 2, etc.

One such permutation that fits is: {3,1,1,1,2,2,3}

Is there an algorithm to count all permutations for this problem in general? Is there a name for this type of problem?

For illustration, I know how to solve this problem for certain types of "restricting sets". Set of items: {1,1,2,2,3}, Restrictions {{1,2},{1,2,3},{1,2,3},{1,2},{1,2}}. This is equal to 2!/(2-1)!/1! * 4!/2!/2!. Effectively permuting the 3 first, since it is the most restrictive and then permuting the remaining items where there is room.

Also... polynomial time. Is that possible?

UPDATE: This is discussed further at below links. The problem above is called "counting perfect matchings" and each permutation restriction above is represented by a {0,1} on a matrix of slots to occupants.

• https://math.stackexchange.com/questions/519056/does-a-matrix-represent-a-bijection
• https://math.stackexchange.com/questions/509563/counting-permutations-with-additional-restrictions
• https://math.stackexchange.com/questions/800977/parking-cars-and-vans-into-car-van-and-car-van-parking-spots

Answer 1

All of the other solutions here are exponential time--even for cases that they don't need to be. This problem exhibits similar substructure, and so it should be solved with dynamic programming.

What you want to do is write a class that memoizes solutions to subproblems:

class Counter {
  struct Problem {
     unordered_multiset<int> s;
     vector<unordered_set<int>> v;
  };

  int Count(Problem const& p) {
    if (m.v.size() == 0)
      return 1;
    if (m.find(p) != m.end())
      return m[p];
    // otherwise, attack the problem choosing either choosing an index 'i' (notes below)
    // or a number 'n'.  This code only illustrates choosing an index 'i'.
    Problem smaller_p = p;
    smaller_p.v.erase(v.begin() + i);
    int retval = 0;
    for (auto it = p.s.begin(); it != p.s.end(); ++it) {
      if (smaller_p.s.find(*it) == smaller_p.s.end())
        continue;
      smaller_p.s.erase(*it);
      retval += Count(smaller_p);
      smaller_p.s.insert(*it);      
    }
    m[p] = retval;
    return retval;
  }

  unordered_map<Problem, int> m;
};

The code illustrates choosing an index i, which should be chosen at a place where there are v[i].size() is small. The other option is to choose a number n, which should be one for which there are few locations v that it can be placed in. I'd say the minimum of the two deciding factors should win.

Also, you'll have to define a hash function for Problem -- that shouldn't be too hard using boost's hash stuff.

This solution can be improved by replacing the vector with a set<>, and defining a < operator for unordered_set. This will collapse many more identical subproblems into a single map element, and further reduce mitigate exponential blow-up.

This solution can be further improved by making Problem instances that are the same except that the numbers are rearranged hash to the same value and compare to be the same.