Now we’re set up to test that our Permutation. Let’s also rewrite our P ( n, k ) calculation as an Elixir helper function:ĭo: div(factorial(length(list)), factorial(length(list) - k)) Let’s write a quick factorial function to help calculate this value: 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: generate / 3 function is what we’d expect. 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. Running out test suite, we’ll see that our first property test passed with flying colors (well, mostly green). + Enum.map(permutations, &assert(&1 |> is_list))Īnd that’s all there is to it. We start by telling StreamData that we want it to generate lists of, at most, (which we’ll define at 5 for now) integers. Let’s start by creating a new property test to verify this for us: generate / 3 function across a wide range of inputs. Using Elixir’s StreamData package, we can easily model and check that this property holds for our Permuatation. generate / 3 should always have the structure of a list of lists. For example, we know that the results of our calls to Permutation. Permutations have some fairly well-known and easily testable properties. ,, ,, ,, ,, ]Īll looks good so far, but dragons hide in the depths. Iex(2)> Permutation.generate(, 2)Īnd we can tell our generator to allow repetitions in the final permutations: The permutation generator that we’ll be testing looks like this:ĭef generate(list, k \\ nil, repetitions \\ false)ĭef generate(, _k, _repetitions), do: ]ĭef generate(_list, 0, _repetitions), do: ]įor head Permutation.generate() This will give us quite a bit more variation on the inputs we test and might uncover some hidden bugs! Our Permutation Generator We can use property testing to test the underlying properties of our solution and the permutations we’re generating. 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. Unfortunately using unit tests to check the correctness of a permutation generator leaves something to be desired. Our first instinct might be to check our work using unit tests. Our final solution was fairly concise, but there are quite a few places where we could have made a mistake in our implementation. Last time we spent some time writing a function to generate permutations of length k of a given list.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |