CODEWITHSUNDEEP
algorithmscalacombinations
JoeDortman
JoeDortman

Reputation: 185

Scala all possible combinations

I'm having hard time doing this task. Let's say I have this data:

0| PRECIOUS LETS
1| GANDALF
2| AYYY

Now I want to print all combinations - take a single word from every line and make a sentence out of it. It's kind of hard to explain, so I'll give an example solution to this problem above(there are two solutions to this) :

1) PRECIOUS GANDALF AYY  //first words from all 3 lines
2) LETS GANDALF AYY      //now another solution is to take 'LETS' instead of 'PRECIOUS' from first line

Now it's clear if I added one more word in 1-3 sentence i would have even more possible solutions. I have been struggling for quite some time now with this and any help would be sooo much appreciated!

Thank you soo much!! ^^

Upvotes: 0

Views: 355

Answers (2)

Tzach Zohar
Tzach Zohar

Reputation: 37822

You can also try:

// For input in the form of List[List[String]]:
val input: List[List[String]] = List(
  List("PRECIOUS", "LETS"),
  List("GANDALF"),
  List("AYYY")
)

val result: List[List[String]] = input.tail.foldLeft(input.head.map(List(_))) {
  (res, nextList) => res.flatMap(sentence => nextList.map(word => sentence :+ word))
}

Note that if any of the input lists is empty, the result would be empty (not sure what your requirement is in that case, can be easily changed to skip empty "lines")

Upvotes: 3

juvian
juvian

Reputation: 16068

I don´t know scala, but here is the pseudocode:

function solve (int listIndex, String current):
    if (listIndex == lists.size()):
        print(current)
        return
    for int i = 0 to lists[listIndex].size():
        solve(listIndex + 1, current + lists[listIndex][i])

solve(0, "")

Upvotes: 1

Related Questions