6
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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... $\endgroup$
    – ciao
    Aug 19, 2015 at 11:04
  • $\begingroup$ Yes, there can be any number of simple elements and simple lists. There can be no duplicate elements. $\endgroup$
    – shrx
    Aug 19, 2015 at 11:14

2 Answers 2

Reset to default
7
$\begingroup$ 
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.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Done. charactercharacter $\endgroup$
    – Patrick Stevens
    Aug 19, 2015 at 12:32
  • $\begingroup$ Why did you edit your answer? Now it's less general as it only works if simple elements are integers. $\endgroup$
    – shrx
    Aug 19, 2015 at 13:58
  • $\begingroup$ 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. $\endgroup$
    – Patrick Stevens
    Aug 19, 2015 at 15:08
  • $\begingroup$ Doesn't work: Tuples::normal: Nonatomic expression expected at position {1,1} in Tuples[{1,{2,3},{4}}]. >> $\endgroup$
    – shrx
    Aug 19, 2015 at 15:54
  • 2
    $\begingroup$ @shrx I'd use a "skip rule" like {x_List :> x, x_ :> {x}}, or Except: x : Except[_List] :> {x} $\endgroup$
    – Mr.Wizard
    Aug 19, 2015 at 16:01
1
$\begingroup$

You could use Outer...

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