2
$\begingroup$

We are given a set of distinct objects, e.g. $\{a,b,c\}$, and each object can be assigned to a mix of different positions, e.g.

$a$ can be in position $1,2$

$b$ can be in position $1,2,3$

$c$ can be in position $2,3$

Is their a formulaic way to determine total number of permutations without repetition? E.g.

$a-b-c$

$b-a-c$

I know a brute force way of doing this but would love to know an efficient way to count the total number of permutations.

$\endgroup$
  • $\begingroup$ It seems crucial to note that two distinct objects cannot have the same position. While a formula could be presented for your specific example, presumably you have in mind that one can try to solve a very general counting problem, where any number of objects are restricted by a subset of positions allowed for that object. Without imposing some regularity on how those subsets are determined, there is only a very general observation on this counting: it is equivalent to computing the permanent of a binary matrix. $\endgroup$ – hardmath Apr 25 '17 at 12:32
  • $\begingroup$ This actually helped answer my question as looking up permanents completely satisfied what I was after, just need to figure out a way now of quickly determining what the actual orders are. $\endgroup$ –  Bodmas12 Apr 26 '17 at 9:50
  • $\begingroup$ Sadly the computation of permanents is not easy. Unlike the computation of determinants (which can be found in polynomial time), the fastest methods known to compute permanents have an exponential complexity. If you are interested, I'll clarify the Question and try to get it reopened, so an Answer can be posted. $\endgroup$ – hardmath Apr 26 '17 at 10:57
  • 1
    $\begingroup$ Well i managed to make a computer code that answers my question posted here and figures out the number of total possible orders in near negligible time, currently my code for determining what the possible orders are takes way too long so i'm working on that. Don't worry about this question because as far as I'm aware it is answered, thanks heaps for the tip $\endgroup$ –  Bodmas12 Apr 26 '17 at 11:01
  • $\begingroup$ Reopen request on meta: math.meta.stackexchange.com/questions/19042/… (I have added the link mainly because the user who suggested reopening explains there why they consider this question to be interesting and worth keeping on the site.) $\endgroup$ – Martin Sleziak May 7 '17 at 5:27
2
$\begingroup$

One can succinctly express the count of possible matchings of items to allowed positions (assuming it is required to position each item and distinct items are assigned distinct positions) by taking the permanent of the biadjacency matrix relating items to allowed positions.

In the example above we would express the count, taking items $a,b,c$ as columns and $1,2,3$ as rows:

$$ \operatorname{perm} \begin{pmatrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \end{pmatrix} = 3 $$

Sadly the computation of a matrix permanent, even in the restricted setting of "binary" matrices (having entries $0,1$), was shown by Valiant (1979) to be $\#P-$complete. The topic was discussed in this previous Math.SE Answer. See also this slightly more recent Math.SE Question.

A naive approach to computing a permanent exploits the expansion by (unsigned) cofactors in $O(n!\; n)$ operations (similar to the high school method for determinants). A clever algorithm by H.J. Ryser (1963) allows the exact evaluation of an $n\times n$ permanent in $O(2^n n)$ operations (based on inclusion-exclusion).

A deterministic polynomial time algorithm for exact evaluation of permanents would imply $FP=\#P$, which is an even stronger complexity theory statement than $NP=P$. So the prospects for this appear extremely dim at present. Interest in boson sampling as a model for quantum computing draws upon a connection with evaluation of permanents.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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