Created
January 4, 2019 13:54
-
-
Save fabrizioc1/0675d276dd80dc889ee63c8dc58664b0 to your computer and use it in GitHub Desktop.
Calculate permutations of a sequence
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Permutations are using all elements in the sequence | |
| import scala.collection.mutable.ArrayBuffer | |
| // Mutable version | |
| def permutationsM[T](s: Seq[T]): Seq[Seq[T]] = { | |
| if (s.length < 2) { | |
| Seq(s) | |
| } | |
| else if (s.length == 2) { | |
| Seq(s, s.reverse) | |
| } | |
| else { | |
| val output = ArrayBuffer[Seq[T]]() | |
| for (i <- (0 to s.length-1)) { | |
| val remainder = ArrayBuffer(s:_*) | |
| remainder.remove(i) | |
| val perms = permutationsM(remainder) | |
| perms.foreach { perm => | |
| val temp = s(i) +: perm | |
| output += temp | |
| } | |
| } | |
| output | |
| } | |
| } | |
| // Immutable version | |
| def permutationsI[T](s: Seq[T]): Seq[Seq[T]] = { | |
| if (s.length < 2) { | |
| Seq(s) | |
| } | |
| else if (s.length == 2) { | |
| Seq(s, s.reverse) | |
| } | |
| else { | |
| val indices = (0 to s.length-1) | |
| indices.flatMap { i => | |
| val remainder = indices.filter(_ != i).map(j => s(j)) | |
| val perms = permutationsI(remainder) | |
| perms.map(perm => s(i) +: perm) | |
| } | |
| } | |
| } | |
| // Using for comprehensions | |
| def permutationsF[T](s: Seq[T]): Seq[Seq[T]] = { | |
| if (s.length < 2) { | |
| Seq(s) | |
| } | |
| else if (s.length == 2) { | |
| Seq(s, s.reverse) | |
| } | |
| else { | |
| val indices = (0 to s.length-1) | |
| def removeIndex[T](k: Int) = indices.flatMap(j => if (j != k) Some(s(j)) else None) | |
| for { | |
| i <- indices | |
| perms <- permutationsF(removeIndex(i)) | |
| } | |
| yield s(i) +: perms | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment