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?

Answer 1

You might consider a recursive solution that uses a pool of digits (in the example you provide, it would be initialized to {1,1,1,2,2,3,3,3}), and decides, at the index given as a parameter, which digit to place at this index (using, of course, the restrictions that you supply).

If you like, I can supply pseudo-code.

Answer 2

You could build a tree. Level 0: Create a root node. Level 1: Append each item from the first "restricting set" as children of the root. Level 2: Append each item from the second restricting set as children of each of the Level 1 nodes. Level 3: Append each item from the third restricting set as children of each of the Level 2 nodes. ...

The permutation count is then the number of leaf nodes of the final tree.

Edit

It's unclear what is meant by the "set of items" {1,1,1,2,2,3,3,3}. If that is meant to constrain how many times each value can be used ("1" can be used 3 times, "2" twice, etc.) then we need one more step:

• Before appending a node to the tree, remove the values used on the current path from the set of items. If the value you want to append is still available (e.g. you want to append a "1", and "1" has only been used twice so far) then append it to the tree.

Answer 3

To save space, you could build a directed graph instead of a tree.

• Create a root node.
• Create a node for each item in the first set, and link from the root to the new nodes.
• Create a node for each item in the second set, and link from each first set item to each second set item.
• ...

The number of permutations is then the number of paths from the root node to the nodes of the final set.

Answer 4

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.