# A code that returns the partial permutations on {1,2,...,n}

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[#] &]


## 1 Answer

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


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


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


• 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. Commented Dec 21, 2021 at 16:11
• @geoffrey, thank you so much for the generous offer. If needed/feasible you can link to this answer as reference.
– kglr
Commented Dec 22, 2021 at 6:29