Last time we spent some time writing a function to generate permutations of length k of a given list. Our final solution was fairly concise, but there are quite a few places where we could have made a mistake in our implementation.
Our first instinct might be to check our work using unit tests. Unfortunately using unit tests to check the correctness of a permutation generator leaves something to be desired. The length of our resulting set of permutations grows rapidly when k and list increase in size, making it feasible to only manually calculate and test the smallest possible permutations.
Thankfully there’s another way. We can use property testing to test the underlying properties of our solution and the permutations we’re generating. This will give us quite a bit more variation on the inputs we test and might uncover some hidden bugs!
Our Permutation Generator
The permutation generator that we’ll be testing looks like this:
defmodule Permutation do
def generate(list, k \\ nil, repetitions \\ false)
def generate([], _k, _repetitions), do: [[]]
def generate(_list, 0, _repetitions), do: [[]]
def generate(list, k, repetitions) do
for head <- list,
tail <- generate(next_list(list, head, repetitions), next_k(k)),
do: [head | tail]
end
defp next_k(k) when is_number(k),
do: k - 1
defp next_k(k),
do: k
defp next_list(list, _head, true),
do: list
defp next_list(list, head, false),
do: list -- [head]
end
You’ll notice that it’s a little different than the generator we built last time. This generator supports the creation of permutations both with and without repetitions of elements from list, and lets you optionally pass in the length of the final permutations, k.
We can use our Permutation.generate/3 function like so:
iex(1)> Permutation.generate([1, 2, 3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
We can also specify a value for k:
iex(2)> Permutation.generate([1, 2, 3], 2)
[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]
And we can tell our generator to allow repetitions in the final permutations:
iex(3)> Permutation.generate([1, 2, 3], 2, true)
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]
All looks good so far, but dragons hide in the depths. Let’s dig deeper.
List of Lists
Permutations have some fairly well-known and easily testable properties. For example, we know that the results of our calls to Permutation.generate/3 should always have the structure of a list of lists.
Using Elixir’s StreamData package, we can easily model and check that this property holds for our Permuatation.generate/3 function across a wide range of inputs. Let’s start by creating a new property test to verify this for us:
property "returns a list of lists" do
end
We start by telling StreamData that we want it to generate lists of, at most, @max_length (which we’ll define at 5 for now) integers.
property "returns a list of lists" do
+ check all list <- list_of(integer(), max_length: @max_length) do
+ end
end
Next, we call our Permutation.generate/3 function to create the permutations of the list that was just generated for us:
property "returns a list of lists" do
check all list <- list_of(integer(), max_length: @max_length) do
+ permutations = Permutation.generate(list)
end
end
Finally we’ll make assertions about the structure of our resulting permutations. We want to assert that the result of our call to Permutation.generate/3 is a list, but also that every element in that result is a list as well:
property "returns a list of lists" do
check all list <- list_of(integer(), max_length: @max_length) do
permutations = Permutation.generate(list)
+ assert permutations |> is_list
+ Enum.map(permutations, &assert(&1 |> is_list))
end
end
And that’s all there is to it. Running out test suite, we’ll see that our first property test passed with flying colors (well, mostly green).
.
Finished in 0.06 seconds
1 property, 0 failures
Correct Number of Permutations
Now that we know that the structure of our resulting list of permutations is correct, the next obvious property that we can test is that the number of permutations returned by our Permutation.generate/3 function is what we’d expect.
Permutations are a well-defined mathematical concept, and so a nice equation exists to determine how many k-length permutations exist for a list of n elements:
P(n, k) = n! / (n - k)!
Let’s write a quick factorial function to help calculate this value:
defp factorial(n) when n <= 0,
do: 1
defp factorial(n),
do: n * factorial(n - 1)
Let’s also rewrite our P(n, k) calculation as an Elixir helper function:
defp pnk(list, k),
do: div(factorial(length(list)), factorial(length(list) - k))
Great!
Now we’re set up to test that our Permutation.generate/3 function is giving us the correct number of permutations for a given list and value of k.
property "returns the correct number of permutations" do
end
This time we’ll generate our list, along with a value for k that ranges from 0 to the length of list:
property "returns the correct number of permutations" do
+ check all list <- list_of(integer(), max_length: @max_length),
+ k <- integer(0..length(list)) do
end
end
Once we have values for list and k, we can generate our set of permutations and make an assertion about its length:
property "returns the correct number of permutations" do
check all list <- list_of(integer(), max_length: @max_length),
k <- integer(0..length(list)) do
+ assert pnk(list, k) ==
+ list
+ |> Permutation.generate(k)
+ |> length
end
end
Once again, our tests pass.
..
Finished in 0.06 seconds
2 properties, 0 failures
Only Include Elements From the List
Another neatly testable property of the permutations we’re generating is that they should only contain values from the list being permutated. Once again, we’ll start by defining the property we’ll be testing and generate our values for list and k:
property "permutations only include elements from list" do
check all list <- list_of(integer(), max_length: @max_length),
k <- integer(0..length(list)) do
end
end
Next, we’ll want to generate our set of permutations for list and k, and reject any permutations from that set that include values not found in list:
property "permutations only include elements from list" do
check all list <- list_of(integer(), max_length: @max_length),
k <- integer(0..length(list)) do
+ assert [] ==
+ list
+ |> Permutation.generate(k)
+ |> Enum.reject(fn permutation ->
+ [] ==
+ permutation
+ |> Enum.reject(&Enum.member?(list, &1))
+ end)
end
end
We’re asserting that the resulting list of permutations should be an empty list ([]). There should be no permutations left that contain elements not found in list!
And, as expected, our suite still passes.
...
Finished in 0.08 seconds
3 properties, 0 failures
Use Each Item Once
Our current implementation of Permutation.generate/3 allows for duplicate items to be passed in through list. When we generate each possible permutation, it’s important that each of these duplicate items, and more generally any item in the list, only be used once.
That is, if list is [1, 2, 2], our set of possible permutations should look like this:
[[1, 2, 2], [1, 2, 2], [2, 1, 2], [2, 2, 1], [2, 1, 2], [2, 2, 1]]
Note that 2 is used twice in each permutation, but never more than twice.
At first, it seems like we might need a new test to verify this property of our permutation generator. It’s conceivable that we could group each set of equal elements, count them, and verify that the resulting permutation have the correct count of each element group. But that sounds complicated, and an added test just introduces more code into our codebase that we need to maintain.
It turns out that we can tweak our previous property test to verify this new property.
Instead of identifying duplicates, counting them, and verifying the correct counts in the final set of permutations, let’s take a simpler approach. Let’s ensure that each element in list is unique by using Elixir’s Enum.with_index/1 function to bundle the element with its index value.
For example, our previous [1, 2, 2] value for list would be transformed into:
[{1, 0}, {2, 1}, {2, 2}]
Now both of our 2 elements are unique. The first is {2, 1}, and the second is {2, 2}. Using this technique, we can recycle our “permutations only include elements from list” with a few slight tweaks:
property "permutations only include elements from list" do
check all list <- list_of(integer(), max_length: @max_length),
k <- integer(0..length(list)) do
assert [] ==
list
+ |> Enum.with_index()
|> Permutation.generate(k)
|> Enum.reject(fn permutation ->
[] ==
permutation
- |> Enum.reject(&Enum.member?(list, &1))
+ |> Enum.reject(&Enum.member?(list |> Enum.with_index(), &1))
end)
end
end
And once again, our suite passes:
...
Finished in 0.08 seconds
3 properties, 0 failures
Final Thoughts
The current version of our property tests currently only test values of list composed entirely of integers. This doesn’t necessarily need to be the case. The list being permutated can contain literally anything, in theory. Expanding our property tests to support a wider range of types might be a great opportunity to try out writing a custom generator function!
Our current test suite also defines @max_length as 5. While testing, I noticed that values of @max_length up to 8 were very performant and finished in under a second on my machine. Running the suite with a @max_length of 9 took several seconds to complete, and using a value of 10 took nearly two minutes to come back green. I’m not sure if these performance problems can easily be improved, but I’m happy about how obvious they became through property testing.
You’ll also note that none of this testing covers generating permutations that allow infinite repetitions of elements from list. The properties for these sets of permutations are completely different, so I’m going to leave this as an exercise for the truly motivated reader.
I’m enjoying my experiences with property testing so far. Hopefully you find these write-ups useful as well. If so, let me know on Twitter!