CODEWITHSUNDEEP
algorithmscala
Avi Kaminetzky
Avi Kaminetzky

Reputation: 1538

Combinations of Unique Subsets of List

Given this list List(1, 1, 2, 2, 3, 3, 4, 5), how can I produce all combinations of subsets of the list, with the following constraints:

  1. Each subset can only contain unique elements.
  2. Each combination of subsets must contain all elements in the initial list (including duplicates). Flattening a combination should equal my initial list.

Here are some of the possible combinations:

List(List(1), List(1), List(2), List(2), List(3), List(3), 
List(4),List(5)) // 1*8
List(List(1,2), List(1,2), List(3,4), List(3,5)) // 2 *4
List(List(1,2,3), List(1,2,3), List(4,5)) // 3,3 and 2
List(List(1,2,3,4), List(1,2,3,5)) // 4 and 4
List(List(1,2,3,4,5), List(1,2,3)) // 5 and 3

I have tried something like this:

val myList = List(1, 1, 2, 2, 3, 3, 4, 5)

val combs = (1 to 5).map(n => myList.combinations(n).toList.filter(x => x.distinct sameElements x)).toList.flatten

val step2 = (1 to combs.length).flatMap(n => combs.combinations(n)).toList

But the computation is too expensive:

java.lang.OutOfMemoryError: Java heap space

Upvotes: 0

Views: 108

Answers (1)

pramesh
pramesh

Reputation: 1964

Try this:

val listLen = l.toSet.size
(1 to listLen).flatMap(x => l.combinations(x).map(x => x.distinct))

Please reply if it runs faster, otherwise need to go with other approaches

Upvotes: 1

Related Questions