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.



Permutations with extra restrictions
In the case where all the elements in your set are different, this problem is known as "rook theory" and there's a substantial literature on it.


What you're trying to do, then, is rook theory on multisets ("multiset" is the usual name for a set with repeated elements); I can't tell if this exists or not.


