# Creating all permutations of list with "alignment"

I need to find all permutations of a list satisfying a condition but I'm lost about how to do so. Given a list I want a write a function to produce all permutations such that the list is "top aligned" and has all permutations of the elements. I think the second requirement of having all permutations of the elements is straightforward using replacements, but I'm not sure how to do the first. Here I give two examples of what I want the output to look like (I used Grid only to increase the clarity of the output)

MyPermute[{{"a","b"}}]=


MyPermute[{{"a","b","c"}}]=


EDIT:

I think the above two examples are insufficient to fully specify the output I want. If the permutation function was run on four elements I'd want to include output such as:

• Should it also include {{a},{a,b},{c}}, i.e. the length of rows not decreasing? Commented Dec 21, 2015 at 20:37
• @MariusLadegårdMeyer: No it should always be top aligned (no gaps, like an upside down game of connect-four) Commented Dec 21, 2015 at 20:52

This fills the blanks with 0s:

 myPerms[list_] :=
Flatten[Table[
ArrayReshape[#, {i, Length[list] + 1 - i}] & /@
Permutations[list],
{i, Length[list]}], 1]


Now doing

MatrixForm /@ myPerms[{"a", "b", "c"}]


reproduces what you want in the second case. I have assumed you only want rectangular arrays here. If you want to allow the lengths of different rows to be different, you can use IntegerPartitions[Length[list]] to calculate all possible lengths of rows.

UPDATE

As I suspected, OP also need tables with rows of different lengths. I'm sure there is a much better way to do this, but I couldn't think of one right now. First, the following function takes a permutation, and a list of lengths of rows, and returns the table:

pL[list_, rowlens_] :=
First@Last@
Reap[FoldList[(Sow[#1[[1 ;; #2]]]; #1[[#2 + 1 ;;]]) &, list,rowlens]]


E.g. pL[{"a", "b", "c", "d", "e"}, {3, 1, 1}] returns

{{"a", "b", "c"}, {"d"}, {"e"}}

Now we just apply this to all permutations of the original list, and let the row length specs be the integer partitions of the length of the original list:

myPerms2[list_] :=
Flatten[Table[
pL[perm, intpart], {intpart, IntegerPartitions[Length[list]]},
{perm, Permutations[list]}], 1]

• Thanks for your response. I think this is in the right direction, but its still missing a few elements I had in mind (see edit). This might be solved by using your suggested IntegerPartitions[Length[list]], but I'm not sure how to get this to work. Commented Dec 21, 2015 at 19:02
• Thanks it the update seems to work just as desired. Just a quick comment I don't think you need the Flatten in Flatten@intpart. Commented Dec 22, 2015 at 13:37
• Thanks for pointing out, you are right of course. Fixed. Commented Dec 22, 2015 at 14:25
per = Permutations[{"a", "b", "c"}];

Grid[{Row /@ per}, Dividers -> All]


Grid[{Column /@ per}, Dividers -> All]


Grid[{Grid /@ (per /. {a_, b_, c_} :> {{a, b}, {c, ""}})}, Dividers -> All]