Permutations as Functions

This is the first part of a series of posts detailing the theory behind Rubik’s cube solutions and tying it in to functional programming concepts. Permutations will be a major building block of our solution. In this post, we’ll show how they can be composed, inverted, and treated like functions.

Scrambles of a String

You might have learned to think of permutations as rearrangements of elements in a collection. In Scala, every SeqLike has a .permutations method that will return an iterator over every permutation of its elements. Consider this example from the REPL:

scala> "ABC".permutations.toList
res0: List[String] = List(ABC, ACB, BAC, BCA, CAB, CBA)

We get a list of six strings, all possible permutations of “ABC”. What might not be immediately obvious is that each of these permutations can be identified with a function of type Char => Char that goes from characters in the string "ABC" back to the same string. For example, consider the fourth element, "BCA". It permutes "ABC" by sending 'A' to 'B', 'B' to 'C', and 'C' to 'A'. We can encode this directly as a partial function in scala:

val bca: Char => Char = {
  case 'A' => 'B'
  case 'B' => 'C'
  case 'C' => 'A'
}

This can permute the characters of our original string via .map:

"ABC".map(bca) // "BCA"

So in a sense "BCA" is not just a permutation of "ABC"; it represents the function that permutes "ABC" into "BCA". This function permutes other strings too:

"BCA".map(bca) // "CAB"
"CAB".map(bca) // "ABC"

Even more generally, bca can be thought of as a function permuting any set of three elements. It sends the first to the second, the second to the third, and the third back to the first.

Bijections from a Set to Itself

So, we can use functions of type A => A to model permutations. However, not every function of this type is a valid permutation. Notice how every letter in a string is still present after it’s scrambled. For our function to preserve this property, it needs to pair off all the elements of its domain and range in an exactly one-to-one fashion.

Such functions are called bijective functions, or bijections. It’s “bi” in the sense of “bidirectional”; we can invert our function to send elements from the range back to the domain. Permutations are a special case of bijections where the parameter and result types are the same, so inverting a permutation gives you a function of the same type.

We can construct the inverse of a permutation, but it will be much easier to do so with a Map implementation, versus representing a permutation as a A => A function.

Implementing Permutations with `Map[A, A]`

Our initial encoding via a (Char => Char) function was a bit opaque. We’ll want want to print, compare, and transform our permutations, so to enable this, we’ll model our original six permutations using Map. For simplicity, let’s use a type inhabited by only three values:

sealed trait Point extends Product with Serializable
case object A extends Point
case object B extends Point
case object C extends Point
val allPoints = Set(A, B, C)

A permutation is then a Map[Point, Point]. Here’s a lightweight implementation using a type alias and some constructors:

type Perm = Map[Point, Point]

object Perm {
  def apply(pairs: (Point, Point)*): Perm = {
    require(pairs.map(_._1).toSet == allPoints, s"Domain must be $allPoints.")
    require(pairs.map(_._2).toSet == allPoints, s"Range must be $allPoints.")
    Map(pairs: _*)
  }

  def apply(p: Point => Point): Perm = {
    apply(A -> p(A), B -> p(B), C -> p(C))
  }

  def inverse(perm: Perm): Perm = perm.map(_.swap)
}

Our first constructor constrains our values to valid permutations as discussed earlier. Our second constructor allows us to lift regular functions into our Perm type. Inverting a permutation is done simply by swapping all the tuples in its map.

With this, we can re-implement our original bca example:

val bca = Perm(
  A -> B,
  B -> C,
  C -> A
)

In Scala, Map inherits from Function1, so we can still pass this as a function in .map:

scala> List(A, B, C).map(bca)
res0: List[Point] = List(B, C, A)

Or compose it with itself to perform successive permutations:

scala> List(A, B, C).map(bca compose bca)
res1: List[Point] = List(C, A, B)

scala> List(A, B, C).map(bca andThen bca)
res2: List[Point] = List(C, A, B)

But unlike a regular function, computing its inverse is trivial:

scala> List(B, C, A).map(inverse(bca))
res3: List[Point] = List(A, B, C)

scala> assert(bca == inverse(inverse(bca)))

As seen in the first section, there are only six permutations of three elements. Below we use our model to implement all six of them:

val abc = Perm(
  A -> A,
  B -> B,
  C -> C
)
val acb = Perm(
  A -> A,
  B -> C,
  C -> B
)
val bac = Perm(
  A -> B,
  B -> A,
  C -> C
)
val bca = Perm(
  A -> B,
  B -> C,
  C -> A
)
val cab = Perm(
  A -> C,
  B -> A,
  C -> B
)
val cba = Perm(
  A -> C,
  B -> B,
  C -> A
)

val allPerms = Set(abc, acb, bac, bca, cab, cba)

Now we can compose and sequence these permutations like we can functions. Notice that since we’ve instantiated all possible permutations, the resulting permutation will be equal to one we’ve already computed:

scala> assert(Perm(acb compose bac) == cab)

scala> val bcaTwice = Perm(bca andThen bca)
bcaTwice: Perm = Map(A -> C, B -> A, C -> B)

scala> assert(bcaTwice == cab)

scala> val cabThrice = Perm(cab andThen cab andThen cab)
cabThrice: Perm = Map(A -> A, B -> B, C -> C)

scala> assert(cabThrice == abc)

The same is true when inverting functions. For example, when we invert bca, we get bac, and vice versa:

scala> assert(inverse(bca) == cab)

scala> assert(inverse(cab) == bca)

There two are inverses of each other. This makes sense if you look at their effect on a list. bca cycles the elements to the left, while cab cycles the elements to the right:

scala> List(A, B, C).map(bca)
res4: List[Point] = List(B, C, A)

scala> List(A, B, C).map(cab)
res5: List[Point] = List(C, A, B)

Another way to say this is that composing bca with cab results in the identity permutation, which sends every point back to itself. In our example, that abc:

scala> List(A, B, C).map(abc)
res6: List[Point] = List(A, B, C) // Same list

scala> assert(Perm(bca compose cab) == abc)

scala> assert(Perm(bca andThen cab) == abc)

A permutation can also be its own inverse, as in these examples:

assert(inverse(acb) == acb)
assert(inverse(bac) == bac)
assert(inverse(cba) == cba)

Each of these permutations swaps two elements, so it makes sense that swapping the elements twice results in no action. Lastly, the identity permutation is always its own inverse:

assert(inverse(abc) == abc)

Our original six permutations have gone from scrambled strings to scrambling functions, which can compare, compose, and invert. Now that’s functional programming! In the next post, we’ll see that permutations are essential to an algebraic structure called a Group.

The code used in this post is available in a scastie worksheet:
https://scastie.scala-lang.org/stewSquared/nNx923P0QyOiBaebwLZyJg

Permutations as Functions

Rubik's Series Part 1 - A demonstration of permutations as bijective functions

Scrambles of a String

Bijections from a Set to Itself

Implementing Permutations with `Map[A, A]`

Like what you are reading?

Permutations as Functions

Rubik's Series Part 1 - A demonstration of permutations as bijective functions

Scrambles of a String

Bijections from a Set to Itself

Implementing Permutations with Map[A, A]

Like what you are reading?

Implementing Permutations with `Map[A, A]`