Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.