3
$\begingroup$

A partial permutation is a bijective partial function. A partial function is a map from a subset of {1,2,...,n} into {1,2,...,n}.

I want a list of the matrix representations of all the partial permutations on {1,2,...,n}. For example the code below returns the desired matrices for n <=4. I would be happy to see the matrices for some larger values of n.

nn = 2;
ppQ[list_] := Apply[And, Table[Count[list[[i]], 1] <= 1 && Count[Transpose[list][[i]], 1] <= 1, {i, 1, Length[list]}]];
ppnn = Select[Tuples[Tuples[{0, 1}, nn], nn], ppQ[#] &]
$\endgroup$

1 Answer 1

2
$\begingroup$
ClearAll[partialPermMatrices1]

 partialPermMatrices1[n_] := Module[{im = PadRight[IdentityMatrix[n], {n + 1, n}], 
  p = Permutations[Join[ConstantArray[n + 1, n], Range@n], {n}]}, 
  Sort @ Map[Extract[im, List /@ #] &] @ p]

Examples:

MatrixForm /@ partialPermMatrices1[2] // Row

enter image description here

MatrixForm /@ partialPermMatrices1[3] // Multicolumn[#, 7] &

enter image description here

Length[partialPermMatrices1 @ #] & /@ Range[8]
{2, 7, 34, 209, 1546, 13327, 130922, 1441729}

An alternative (slower) method:

ClearAll[partialPermMatrices2]

partialPermMatrices2[n_] := Module[
  {f = Map[Through @* 
        (MapAt[ConstantArray[0, n] &, List /@ #] & /@ Subsets[Range @ n])], 
   im = Sort @ Permute[IdentityMatrix @ n, SymmetricGroup @ n]}, 
 Union @@ f @ im]

And a variation on OP's method using Tuples + Select:

ClearAll[partialPermMatrices3]
partialPermMatrices3[n_] := Select[Max[{Total @ #, Total[#, {2}]}] <= 1 &]@
 Tuples[{0, 1}, {n, n}]

(partialPermMatrices1[#] == 
   partialPermMatrices2[#] == 
     partialPermMatrices3[#]) & /@ Range[4]
{True, True, True, True}

Although partialPermMatrices3 faster than OP's method it is much slower than partialPermMatrices1.

An aside: If we want only the partial permutations, we can use a variant of partialPermMatrices as follows:

ClearAll[partialPerms]
partialPerms[n_] := Permutations[Join[ConstantArray[♢, n], Range @ n], {n}]

Examples:

Multicolumn[Row /@ #, Min[Length@#, 12], Appearance -> "Horizontal", 
    Dividers -> All] & /@ (partialPerms[#] & /@ Range[4]) // Column

enter image description here

$\endgroup$
2
  • $\begingroup$ This is great! Thank you. I wrote a code that counts the number of commuting pairs of partial permutations and submitted to OEIS. Is it OK to incorporate your code into mine. I can list you as co-author of the code if you wanted. $\endgroup$
    – geoffrey
    Commented Dec 21, 2021 at 16:11
  • $\begingroup$ @geoffrey, thank you so much for the generous offer. If needed/feasible you can link to this answer as reference. $\endgroup$
    – kglr
    Commented Dec 22, 2021 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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