1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\begingroup$ You might want to fix your permutation of 8 elements that has 7 elements. $\endgroup$
    – Dan Piponi
    Commented May 7, 2010 at 18:13
  • $\begingroup$ 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. $\endgroup$
    – Richard Stanley
    Commented May 7, 2010 at 19:45
  • $\begingroup$ 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. $\endgroup$
    – Ross Tang
    Commented May 10, 2010 at 4:48

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .