CODEWITHSUNDEEP
algorithmscalacollectionsmapping
arkonautom
arkonautom

Reputation: 958

Collection of variable-length Tuples AND map with multiple values TO weighted combinations

This problem is from "Functional Programming Principles in Scala" @ Coursera so I need to avoid having complete code in this question - it's past deadline already but there are always years to come. I was looking for general suggestions on methods to implement this transformation.

I have a set of variable-length Tuples, full subset of some String in lowercase

val indexes = Set('a', 'b', 'c')

and a set of tuples with max allowed occurence for each char

val occurences = Set(('a', 1), ('b', 5), ('c', 2))

I want to get combinations of weighted tuples:

val result = Seq(Set(), Set((a, 1)), Set((b, 1)), Set((b, 2)) ... Set((a, 1)(b, 2)(c, 2)) ...)

My assignment suggests easy way of building result via recursive iteration.

I'd like to do it in more "structural?" way. My idea was to get all possible char subsets and multiplex those with added weights (~pseudocode in last line of post).

I got subsets via handly subsets operator

val subsets = Seq(Set(), Set(a), Set(b), Set(c), Set(a, b), Set(a, c), Set(b, c), Set(a, b, c)

and also map of specific Int values for each char, either of

val weightsMax Map(a -> 1, b -> 5, c -> 2)

val weightsAll Map(a -> List(1), b -> List(5,4,3,2,1), c -> List(2,1))

I don't really know which language feature I should use for this operation. I know about for and collection operations but don't have experience to operate with those on this level as I'm new to functional paradigm (and collection operations too). I would have no problems with making some corporate-styled java / XML to solve this (yeah ...).

I'd like to have something similar defined:

FOREACH subset (MAP chars TO (COMBINATIONS OF weights FOR chars))

Upvotes: 1

Views: 124

Answers (1)

OlivierBlanvillain
OlivierBlanvillain

Reputation: 7768

You can express this problem recursively and implement it this exact way. We want to build a function called expend: Set[Char] => List[Set[(Char, Int)]] that returns all the possible combinations of weights for a set of chars (you wrote it chars TO (COMBINATIONS OF weights FOR chars)). The intuitive "by the definition" way is to assign each possible weights to the first char, and for each of these assign each possible weights to the second char and so on... 

def expend(set: Set[Char]): List[Set[(Char, Int)]] =
  if(set isEmpty) Nil else
  allPairsFromChar(set head) flatMap (x => expend(set tail) map (_ + x))

Where allPairsFromChar is trivial from your weightsAll and your FOREACH subset (...) is another flatMap ;)

Upvotes: 1

Related Questions