CODEWITHSUNDEEP
javascalapermutationscala-collections
D. Ataro
D. Ataro

Reputation: 1821

Calculate all permutations for List(s) inside List

Request

As this question is dedicated to the Scala programming language, a solution in Java would do just as well. One minor thing to notice, however, is that in a Scala solution tail recursion (Scaladocs) is definitely favorable over any other, and in Java, a non-recursive solution is favorable. This is due to the fact that it needs work on quite large structures of data so that each item contained by the "preferably lazy Stream or similar" can be handled accordingly, without receiving a StackOverflowError (Javadocs) (how ironic).

The type of data that should be permuted is the Scala List (Scaladoc), but it’s completely alright to respond with a solution using Java arrays, and a somewhat intricate looping structure.

The Problem With Permutations of a Single List

In Scala, the following would be a completely valid way to retrieve all permutations of given collection type. This following approach returns an iterator containing all the permutations, in a lazy manner:

val permutations = List(1, 2, 3, 4, 5, 6, 7).permutations.take(5)

This would, as mentioned before, yield an iterator containing the permutations of that particular List. Since it’s lazy, we’re able to take only five from the sequence. This is fine, from my understanding, as long as we are not calling toString on the iterator, as that would result in the iterator computing all data available and returning it as a String.

Although lazy, this does not happen to solve my problem. What I’m after is with the following:

// List of lists
val lists = List(
        List(1, 2, 3), 
        List(3, 2), 
        List(4, 3, 2, 4))

Calculate all the possible permutations of the inner List(s), whilst maintaining the same ordering for the List(s) inside the outer List, with the same number of elements contained by each List inside the outer List. Meaning, the inner List(s) should be permuted, in all ways possible, together with the other inner List(s) as if though they had been flattened, whilst still maintaining the same ordering and containing the same number of elements as before.

One permutation might thus yield:

List(List(1, 3, 2), List(3, 2), List(3, 4, 4, 2))

Furthermore

It appears as though I’m not quite clever enough to conquer the concepts listed here on my own. Any pointers, if not complete code, would be highly appreciated! Should you have any questions, do write a comment and I’ll do my very best to clarify, either in a comment or by making minor edits to the already existing question.

If you have an answer to this question, but in a language not listed by this question, feel free to attempt to answer nonetheless, it’s mainly the concept of this type of permutations I’m after!

Upvotes: 3

Views: 813

Answers (2)

jwvh
jwvh

Reputation: 51271

If the size of the outer List is known and constant then it can be done as follows.

val ls = List(List(1, 3, 2), List(7, 8), List(9, 4, 4, 5))

val allPerms: Iterator[List[List[Int]]] = for {
  a <- ls(0).permutations
  b <- ls(1).permutations
  c <- ls(2).permutations
} yield List(a,b,c)

In this example the resulting Iterator has 144 elements, which is what we should expect: 6 X 2 X 12 = 144

If the outer List length is fluid then the task is a bit more complicated.

update

In this case "more complicated" means I had to work it over for a while before coming up with a possible solution.

def getAllPerms[A]( in: List[List[A]]
                  , acc: List[List[A]] = List()
                  ): Iterator[List[List[A]]] = in match {
  case end :: Nil => end.permutations.map(acc :+ _)
  case hd :: tl => hd.permutations.flatMap(x => getAllPerms(tl, acc :+ x))
  case Nil => Iterator()  // just to be complete
}

This is recursive but not tail recursive. It does pass my limited set of tests. Give it a try.

Upvotes: 1

Tzach Zohar
Tzach Zohar

Reputation: 37832

Tail-recursive, lazily evaluated solution:

@tailrec
def tailRecCombineWith(permutatedLists: Iterator[List[List[Int]]], remainingLists: List[List[Int]]): Iterator[List[List[Int]]] = remainingLists match {
  case Nil => permutatedLists
  case head :: tail => tailRecCombineWith(for {
    a: List[List[Int]] <- permutatedLists
    b: List[Int] <- head.permutations
  } yield a :+ b, tail)
}

val result: Iterator[List[List[Int]]] = 
  tailRecCombineWith(lists.head.permutations.map(List(_)), lists.tail)

Upvotes: 1

Related Questions