Skip to main content
3 of 4
edited tags
Mr.Wizard
  • 275.2k
  • 34
  • 606
  • 1.5k

How to generate all possible orderless partitions of a list according to another list?

This question is hard to describe in plain text. So I will post an example and a working code (stupid) to illustrate.

For example I have a list: {1, 2, 3, 4, 5} and a partition list {2, 2, 1}. I will first choose 2 elements (there are 10 ways to do so), and then choose another 2 elements from the rest of the list (of length 3 and there are 3 ways to do so). The output is

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

The current working code is very memory-inefficient because it generates unnecessary lists first and deletes them later. Here it is:

f[list_, partition_] := DeleteDuplicates[ Sort /@ Internal`PartitionRagged[#, partition] & /@ Permutations[list]] 

I am also working on using Subsets to generate directly, but I have got lost in Folding with brackets, and the code is very long. Any elegant or efficient solutions would be appreciated.

vapor
  • 8k
  • 2
  • 23
  • 59