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

Improve this question
$\endgroup$
2
  • $\begingroup$ Should it also include {{a},{a,b},{c}}, i.e. the length of rows not decreasing? $\endgroup$
    – Marius Ladegård Meyer
    Dec 21, 2015 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, 2015 at 20:52

2 Answers 2

Reset to default
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]
Improve this answer
$\endgroup$
3
  • $\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, 2015 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, 2015 at 13:37
  • $\begingroup$ Thanks for pointing out, you are right of course. Fixed. $\endgroup$
    – Marius Ladegård Meyer
    Dec 22, 2015 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

Improve this answer
$\endgroup$

Your Answer

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

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