# Nested permutations

I would like to compute all "nested permutations" (not sure if it's the right term) of a list consisting of simple elements (numbers, strings) and simple sublists (level 1 lists of simple elements).

For example, with the list {1, {2, 3}}, I calculate the nested permutations like this:

list = {1, {2, 3}};
Flatten[# /. ({a___, b_List, c___} :> ({a, #, c} & /@ b)) & /@
Permutations[list], 1]

{1,2}
{1,3}
{2,1}
{3,1}


As you can see, I want all possible permutations where only one of the elements in the simple sublists is included. However, my method fails if the list contains more than one simple sublist:

list2 = {1, {2, 3}, {4}}
Flatten[# /. ({a___, b_List, c___} :> ({a, #, c} & /@ b)) & /@
Permutations[list2], 1]

{1,2,{4}}
{1,3,{4}}
{1,4,{2,3}}
{2,1,{4}}
{3,1,{4}}
{2,{4},1}
{3,{4},1}
{4,1,{2,3}}
{4,{2,3},1}


I tried replacing ReplaceAll (/.) with ReplaceRepeated (//.), this however caused an infinite recursion:

ReplaceRepeated::rrlim: Exiting after {1,{2,3},{4}} scanned 65536 times. >>


How can I compute all possible permutations where only one element from each of the simple sublists is included?

Edit: there can be any number of simple elements and simple lists in a list, but there will never be any duplicates.

• Can there be multiple simple elements? And if there are duplicate elements overall and selection/permutation results in a duplicate permutation, is it to remain or do you require distinctness? You need to better specify the question...
– ciao
Aug 19, 2015 at 11:04
• Yes, there can be any number of simple elements and simple lists. There can be no duplicate elements.
– shrx
Aug 19, 2015 at 11:14

perms[l_] := Flatten[Permutations /@ Tuples[Replace[l, (x_Integer | x_String) -> {x}, {1}]], 1]


outputs

{{1, 2, 4}, {1, 4, 2}, {2, 1, 4}, {2, 4, 1}, {4, 1, 2},
{4, 2, 1}, {1, 3, 4}, {1, 4, 3}, {3, 1, 4}, {3, 4, 1},
{4, 1, 3}, {4, 3, 1}}


when given input {1, {2, 3}, {4}}.

That is, if you just wrap each simple element in a List head, then use Tuples and find the permutations of each tuple thereby found, you get what I think you want.

• Done. charactercharacter Aug 19, 2015 at 12:32
• Why did you edit your answer? Now it's less general as it only works if simple elements are integers.
– shrx
Aug 19, 2015 at 13:58
• The fix is trivial. Someone said it would be better to write the function rather than just to demonstrate its application, so I did. I've made the obvious fix. Aug 19, 2015 at 15:08
• Doesn't work: Tuples::normal: Nonatomic expression expected at position {1,1} in Tuples[{1,{2,3},{4}}]. >>
– shrx
Aug 19, 2015 at 15:54
• @shrx I'd use a "skip rule" like {x_List :> x, x_ :> {x}}, or Except: x : Except[_List] :> {x} Aug 19, 2015 at 16:01

You could use Outer...

p[list_List] :=
Flatten[Permutations /@
Partition[
Flatten[Outer[List, Sequence @@ (list /. x_Integer -> {x})]],
Length[list]],
1]