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.

$\endgroup$
  • 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 '15 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 '15 at 11:14
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.

$\endgroup$
  • 1
    $\begingroup$ Done. charactercharacter $\endgroup$ – Patrick Stevens Aug 19 '15 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 '15 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 '15 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 '15 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 '15 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]
$\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.