Calculate all permutations for list (s) within a list
Request
Since this question is about the Scala programming language, a Java solution would work exactly the same. However, one minor thing is that in Scala's tail recursion solution (Scaladocs) is definitely advantageous over any other, and in Java, a non-recursive solution is beneficial. This is because it needs to work on rather large data structures so that every element held by a "preferably lazy stream" or the like can be handled appropriately without getting a StackOverflowError (Javadocs) (ironically).
The datatype that needs to be swapped is Scala List (Scaladoc), but its quite possible to answer with a solution using Java arrays and a somewhat complex loop structure.
One list permutation problem
In Scala, the following would be a completely correct way to get all permutations of a given collection type. This next approach returns an iterator containing all permutations in a lazy manner:
val permutations = List(1, 2, 3, 4, 5, 6, 7).permutations.take(5)
This, as previously mentioned, will give an iterator containing the permutations of that particular List. Since he was lazy, they were only able to take five of the sequence. This is fine in my opinion, as long as we don't call toString on the iterator, as this will cause the iterator to compute all available data and return it as a string.
Although lazy, this doesn't happen to fix my problem. What is Im after with the following:
// List of lists
val lists = List(
List(1, 2, 3),
List(3, 2),
List(4, 3, 2, 4))
Calculate all possible permutations of the inner list (s) while maintaining the same ordering for the list (s) inside the outer list with the same number of elements contained in each list inside the outer list. Meaning, the inner list should be reinstalled in every possible way along with the other inner list, as if they were flattened, while maintaining the same ordering and containing the same number of elements as before.
Thus, one permutation is possible:
List(List(1, 3, 2), List(3, 2), List(3, 4, 4, 2))
Furthermore
It looks like I'm not smart enough to beat the concepts listed here on their own. Any pointers if not complete code would be much appreciated! If you have any questions, post a comment and I'll do my best to clarify this either in the comment or by making minor changes to an existing question.
If you have an answer to this question, but in a language not listed in this question, feel free to try and answer, however, its mostly a concept of this type of permutation I'm after!
source to share
Tail-recursive , lazy-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)
source to share
If the size of the outside List
is known and constant, then this 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 resultant Iterator
has 144 items, which is what you would expect: 6 X 2 X 12 = 144
If the outer length List
is fluid, the task is a little more difficult.
Update
In this case, "more complex" means that I had to work through it 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
}
It is recursive, but not tail-recursive. It passes my limited set of tests. Try it.
source to share