A programming kata is an exercise which helps a programmer hone his skills through practice and repetition.

This article is part of the series “Scala Tutorial Through Katas”. Articles are divided into easy, medium and hard. Beginners should start with easy ones and move towards more complicated once they feel more comfortable programming in Scala.

For the complete list of Scala katas and solutions please visit the index page

The article assumes that the reader is familiar with the basic usage of ScalaTest asserts and knows how to run them from his favorite Scala IDE (ours is IntelliJ IDEA with the Scala plugin).

Tests that prove that the solution is correct are displayed below. Recommended way to solve this kata is to write the implementation for the first test, confirm that it passes and move to the next. Once all of the tests pass, the kata can be considered solved.

One possible solution is provided below the tests. Try to solve the kata by yourself first.

# String Permutations

Create a program that returns all permutations of a given string

Following BDD scenario should be used as the acceptance criteria.

[BDD SCENARIO]

[code lang=scala]

class PermutationsTest extends FeatureSpec with GivenWhenThen with Matchers {

scenario("Program returns all permutations of a given string") {

When("permutation of a string ABC is performed")

val perm = Permutations("ABC")

Then("the result has 6 permutations")

perm should have size 6

Then("the result contains permutation ABC")

perm should contain ("ABC")

Then("the result contains permutation ACB")

perm should contain ("ACB")

Then("the result contains permutation BAC")

perm should contain ("BAC")

Then("the result contains permutation BCA")

perm should contain ("BCA")

Then("the result contains permutation CAB")

perm should contain ("CAB")

Then("the result contains permutation CBA")

perm should contain ("CBA")

}

}

[/code]

Test code can be found in the GitHub Permutations.scala.

[ONE POSSIBLE SOLUTION]

[code lang=scala]

object Permutations {

def apply(text: String) = text.permutations.toArray

}

[/code]

The solution code can be found in Permutations.scala solution.

What was your solution? Post it as a comment so that we can compare different ways to solve this kata.

utahkayobject Permutations {

def permuteImpl(text: Seq[Char]): List[String] = {

text match {

case Nil => List()

case Seq(head) => List(head.toString())

case seq =>

seq.flatMap(el => permuteImpl(seq.diff(Seq(el))).map(p => el +: p)).toList

}

}

def apply(text: String): List[String] = {

permuteImpl(text)

}

}