Geek Answers Handbook

Permutations with additional restrictions

I have a set of elements, for example: {1,1,1,2,2,3,3,3} and a bounding 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 elements, but the first element should be 3, and the second should be 1 or 2, etc.

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

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

To illustrate, I know how to solve this problem for certain types of "bounding sets". Elementset: {1,1,2,2,3}, Constraints {{1,2}, {1,2,3}, {1,2,3}, {1,2}, {1,2} }. This is 2! / (2-1)! / 1! * 4! / 2! / 2 !. Effectively rearranging the first three, since they are the most restrictive, and then rearranging the rest of the objects where there is space.

Also ... polynomial time. Is it possible?

UPDATE: This is discussed further in the links below. The above problem is called "counting perfect matches", and each permutation restriction above is represented as {0,1} on the matrix of slots for residents.

+6
math algorithm permutation combinatorics
source share
4 answers

All other solutions here are exponential time - even for cases where they should not be. This problem has a similar substructure, so it should be solved using dynamic programming.

What you want to do is write a class that imagines solutions to subtasks:

class Counter { struct Problem { unordered_multiset<int> s; vector<unordered_set<int>> v; }; int Count(Problem const& p) { if (mvsize() == 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 = psbegin(); it != psend(); ++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 the choice of index i, which should be chosen in a place where v [i] .size () is small. Another option is to choose the number n, which should be one for which there are several places v in which it can be placed. I would say that at least two decisive factors must win.

In addition, you will need to define a hash function for the problem - it should not be too complicated if you use the boost hash file.

This solution can be improved by replacing the vector with the set <> and defining the <operator for unordered_set. This will lead to the breakdown of many identical subtasks into one element of the map and the subsequent decrease in the reduction of exponential inflation.

This solution can be further improved by the fact that the help instances are the same, except that the numbers rearrange the hash with the same value and are compared with the same.

+1
source share

You can consider a recursive solution that uses a pool of numbers (in the example that you provide, it will be initialized {1,1,1,2,2,3,3,3}} and decides, with the index given as a parameter, a figure for this index (using, of course, the restrictions that you provide).

If you like, I can put pseudo code.

+1
source share

You can build a tree. Level 0: Create the root node. Level 1: Add each element from the first “bounding box” as children of the root. Level 2: add each element from the second bounding set as children of each of the nodes of level 1. Level 3: add each element from the third bounding set as children of each of the nodes of level 2. ...

The number of permutations is the number of leaf nodes in the leaf tree.

Edit

It is unclear what is meant by a "set of objects" {1,1,1,2,2,3,3,3}. If this is intended to limit how many times each value can be used ("1" can be used 3 times, "2", etc.), we need one more step:

  • Before adding node to the tree, delete the values ​​used for the current path from the set of elements. If the value you want to add is still available (for example, you want to add “1” and “1” has only been used twice so far), then add it to the tree.
+1
source share

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

  • Create the root node.
  • Create a node for each element in the first set and a link from the root to the new nodes.
  • Create a node for each element in the second set and a link from each first set element for every second element specified.
  • ...

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

0
source share

More articles:


All Articles