4
$\begingroup$

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"}}]=

enter image description here

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

enter image description here

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:

enter image description here

$\endgroup$
  • $\begingroup$ Should it also include {{a},{a,b},{c}}, i.e. the length of rows not decreasing? $\endgroup$ – Marius Ladegård Meyer Dec 21 '15 at 20:37
  • $\begingroup$ @MariusLadegårdMeyer: No it should always be top aligned (no gaps, like an upside down game of connect-four) $\endgroup$ – JeffDror Dec 21 '15 at 20:52
4
$\begingroup$

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]
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JeffDror Dec 21 '15 at 19:02
  • $\begingroup$ 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. $\endgroup$ – JeffDror Dec 22 '15 at 13:37
  • $\begingroup$ Thanks for pointing out, you are right of course. Fixed. $\endgroup$ – Marius Ladegård Meyer Dec 22 '15 at 14:25
3
$\begingroup$
per = Permutations[{"a", "b", "c"}];

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

enter image description here

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

enter image description here

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

enter image description here

$\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.