Code to enumerate permutations in Scala

by

Given a Seq, one can already have permutations by invoking the permutations method.

scala> List(1,2,3).permutations.mkString("\n")
res3: String = 
List(1, 2, 3)
List(1, 3, 2)
List(2, 1, 3)
List(2, 3, 1)
List(3, 1, 2)
List(3, 2, 1)

Furthermore there is also a method for combinations:

scala> List(1,2,3).combinations(2).mkString("\n")
res4: String = 
List(1, 2)
List(1, 3)
List(2, 3)

Regarding your implementation I would say three things:

(1) Its good looking

(2) Provide an iterator (which is the std collections approach that allows to discard elements). Otherwise, you can get lists with 1000! elements which may not fit in memory.

scala> val longList = List((1 to 1000):_*)
longList: List[Int] = List(1, 2, 3,...


scala> permutations(longList)
java.lang.OutOfMemoryError: Java heap space
    at scala.collection.immutable.List.$colon$colon(List.scala:67)
    at .interleave(<console>:11)
    at .interleave(<console>:11)
    at .interleave(<console>:11)

(3) You should remove duplicated permutations (as observed by Luigi), since :

scala> permutations(List(1,1,3))
res4: List[List[Int]] = List(List(1, 1, 3), List(1, 1, 3), List(1, 3, 1), List(1, 3, 1), List(3, 1, 1), List(3, 1, 1))

scala> List(1,1,3).permutations.toList
res5: List[List[Int]] = List(List(1, 1, 3), List(1, 3, 1), List(3, 1, 1))

More Related Contents:

  1. error in if return in Scala
  2. What are Scala context and view bounds?
  3. Call by name vs call by value in Scala, clarification needed
  4. (Why) do we need to call cache or persist on a RDD
  5. Automatically and Elegantly flatten DataFrame in Spark SQL
  6. Spark extracting values from a Row
  7. How to pass -D parameter or environment variable to Spark job?
  8. Why is “Unable to find encoder for type stored in a Dataset” when creating a dataset of custom case class?
  9. Scala: Merge map
  10. Finding type parameters via reflection in Scala 2.10?
  11. MatchError while accessing vector column in Spark 2.0
  12. Spark / Scala: forward fill with last observation
  13. how do I get sbt to use a local maven proxy repository (Nexus)?
  14. How do you do dependency injection with the Cake pattern without hardcoding?
  15. Scala multiple type pattern matching
  16. Pattern matching on generic type in Scala
  17. What are the rules to govern underscore to define anonymous function?
  18. Use case of scala.concurrent.blocking
  19. Apache Spark: Get number of records per partition
  20. Escape a dollar sign in string interpolation
  21. Why is it possible to declare variable with same name in the REPL?
  22. Explicit self-references with no type / difference with ”this”
  23. How to sort a list in Scala by two fields?
  24. Addition of two RDD[mllib.linalg.Vector]’s
  25. How can I connect to a postgreSQL database into Apache Spark using scala?
  26. How to use IntelliJ with Play Framework and Scala
  27. Spark column string replace when present in other column (row)
  28. scala f-bounded types explanation
  29. Scala variable argument list with call-by-name possible?
  30. Scalaz Bind[Seq] typeclass

Leave a Comment