# Permutations with extra restrictions

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.

-
You might want to fix your permutation of 8 elements that has 7 elements. –  Dan Piponi May 7 '10 at 18:13
When all elements are different, the problem is equivalent to computing the permanent of a (0,1)-matrix. This is known to be #P-complete. See en.wikipedia.org/wiki/Computing_the_permanent. –  Richard Stanley May 7 '10 at 19:45
May I know why you would need permutations with extra restrictions? And are you doing with a large set? As Richard said, it is a #P-complete problem. I can write you a problem to solve this problem, but it may take forever for a large problem. –  Ross Tang May 10 '10 at 4:48

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.

-