Background
Every morning when you wake up, you need to perform a set of tasks before you go to work or do something else you'd like. Have you ever thought of each and every possible order you can start your day in?Using Permutations, you can try all combinations of an input set. As you will learn in this post, there is an astonishing number of combinations even for a moderately numbered set. For example, if you have just ten items, you can combine them in over three million ways.
In this post, we will build a small Java 8 support class named Permutations that can be used in unit testing, games strategy evaluation, problem solving and in many other powerful applications.
The Mathematics
You do not have to read this chapter in order to understand this post. However, it helps. So, try to stay on as long as you can before skipping to the next chapter.The term permutation relates to the process of arranging all the members of a set in an order or, if the set is already ordered, rearranging (or mathematically speaking permutating) the order of the set. For example, if we have a set {1, 2, 3} we can arrange that set in six different ways; {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.
The number of permutations for n distinct objects in a set is said to be n-factorial, mathematically written as n!. The value of n! can be calculated as the factor of one multiplied by all positive integers less than or equal to n. So, if we take our previous set {1, 2, 3}, we will see that it has three distinct members. Thus, there will be 3! = 1*1*2*3 = 6 unique combinations. Encouragingly enough, this is consistent with the example above, where we listed all the six combinations. The observant reader now concludes that one may ignore the serial factor of one since one is the multiplicative identity number, i.e. for any number a, it is true that 1*a = a. In pure English, this means that you can skip multiplying with 1 since you will get back the same result anyhow. So, n! is really 1 multiplied with 2*3*....*n.
Now, if we produce a list of the number of distinct members in a set and calculate the corresponding n-factorial, we will arrive at the following table:
0! 1 (by definition, 1 without multiplying with anything)
1! 1 (obviously you can only arrange a single item in one way)
2! 2
3! 6 (as in the example above)
4! 24
5! 120 (the largest n-factorial value that can fit in a byte (max 2^7 = 127))
6! 720
7! 5040 (the largest n-factorial value that can fit in a short (max 2^15 = 32768))
8! 40320
9! 362880
10! 3628800
11! 39916800
12! 479001600 (the largest n-factorial value that can fit in an int (max 2^31 = 2147483647))
13! 6227020800
14! 87178291200
15! 1307674368000
16! 20922789888000
17! 355687428096000
18! 6402373705728000
19! 121645100408832000
20! 2432902008176640000 (the largest n-factorial value that can fit in a long (max 2^63))
21! 51090942171709440000
...
42! 1405006117752879898543142606244511569936384000000000 (~number of atoms on earth)
As can be seen, you have to take care when applying permutations in your code, because you might experience extremely long execution times even for a small number of items. If you, for example, can evaluate any given combination in 1 ms and you have 16 items, the wall clock time for a single thread will be 16!/1000 s > 600 years!
The Permutations class
There are many ways to implement a permutator in a programming language. In this post, my objective was to present the shortest possible code for a permutator in Java 8, so if you can come up with a shorter one, please leave a comment below. Thus, I have opted for simplicity rather than performance.Secondly, I wanted to work with Java 8 Streams, allowing integration with the powerful Stream functions that are available.
Implementation
The first method we need is the n-factorial function that calculates the number of unique combination of a distinct set. I have written a post on this before and you can read the details here. This is how it looks like:public long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
Note that the function will only handle an input range of 0 <= n <= 20 because 0 is the lowest defined input value for n-factorial and 20 corresponds to the maximum return value a long can hold.Next thing we need is a method that returns a numbered permutation of any given input List. So if we, for example, have a List with two items "A" and "B", the first permutation (0) is {A, B} and the second permutation (1) is {B, A}. If we have a List with tree items {A, B, C}, then we have the following permutations:
no Permutation
-- ---------------
0 {A, B, C}
1 {A, C, B}
2 {B, A, C}
3 {B, C, A}
4 {C, A, B}
5 {C, B, A}
We need to make yet another table of a List before the pattern that I am going to exploit becomes obvious. The complete permutations for the List {A, B, C, D} looks like this:
no Permutation
-- ---------------
0 {A, B, C, D}
1 {A, B, D, C}
2 {A, C, B, D}
3 {A, C, D, B}
4 {A, D, B, C}
5 {A, D, C, B}
6 {B, A, C, D}
7 {B, A, D, C}
8 {B, C, A, D}
9 {B, C, D, A}
10 {B, D, A, C}
11 {B, D, C, A}
12 {C, A, B, D}
13 {C, A, D, B}
14 {C, B, A, D}
15 {C, B, D, A} (Used in an example below)
16 {C, D, A, B}
17 {C, D, B, A}
18 {D, A, B, C}
19 {D, A, C, B}
20 {D, B, A, C}
21 {D, B, C, A}
22 {D, C, A, B}
23 {D, C, B, A}
This means that we, for any input List, can reduce the problem by picking the first item according to the algorithm above and then recursively invoke the same method again, but now with a reduced number of items in the input list. A classical divide-and-conquer approach. This is how it looks like:
private static <T> List<T> permutationHelper(long no, LinkedList<T> in, List<T> out) {
if (in.isEmpty()) return out;
long subFactorial = factorial(in.size() - 1);
out.add(in.remove((int) (no / subFactorial)));
return permutationHelper(no % subFactorial, in, out);
}
This helper method takes the permutation number no, an input List in with the initial ordered items and then an out List used to build up the result as the recursion progresses.As common recursion practice dictates, we start with the base case where we handle the trivial case where recursion shall stop. If the in List is empty, then we are ready and just return the now completed out list.
If the in List was not empty, then we first calculate the previously mentioned subFactorial which is (in.size()-1)! as explained above. This value is then used later on in the method.
The next line is really all logic in the method. We first calculate the index of the item we want to put first in the out List. The index of the item is (int)(no/subFactorial) and we remove this from the in List. As the remove method conveniently returns the item we just removed, we can use remove's return value directly and just add it to the end of the out List in one step.
Now that we have reduced the problem from n to n-1 we need to recurse in a proper way. We call our permutationHelper() method with the same in and out lists we got as input parameters but the permutaion number no is now the remainder of the previous division. This is logical because we handled only the corresponding whole part of the division before. So, we invoke with no%subFactorial which is the remainder that remains to handle.
This is really all there is to do. Those five innocent lines can execute in under 1 ms or perhaps in over 2000 years depending on your input.
The helper method is just there to help us write the real permutator that we are exposing in the class. Here is the exposed wrapper:
public static <T> List<T> permutation(long no, List<T> items) {
return permutationHelper(
no,
new LinkedList<>(Objects.requireNonNull(items)),
new ArrayList<>()
);
}
We provide the permutation number no and the List we want to use as input for our method and we just create the in and out List and call the helper method. Simple.So now we can compute any permutation of a given List. But the Stream support remains, the one that can give us streams of permutated lists. Providing such a method is really trivial now that we got our permutation() method. This is how it can be done:
public static <T> Stream<Stream<T>> of(T... items) {
List<T> itemList = Arrays.asList(items);
return LongStream.range(0, factorial(items.length))
.mapToObj(no -> permutation(no, itemList).stream());
}
All the hard work is done by the LongStream which supports laziness, parallelism, etc for free and we only map the long Stream to what we would like to have. The long stream provides the input longs 0, 1, 2, ..., (items.lenght)! and then we map those longs to the corresponding permutation. It is really simple.
Note that I have opted to return a Stream of Stream rather than a Stream of List or something similar. If you want a Stream of List, you just change the return type and the mapping.
Now that we have completed everything we need, I will provide the entire Permutations class before we start putting it to use with some examples:
public class Permutations {
private Permutations() {
}
public static long factorial(int n) {
if (n > 20 || n < 0) throw new IllegalArgumentException(n + " is out of range");
return LongStream.rangeClosed(2, n).reduce(1, (a, b) -> a * b);
}
public static <T> List<T> permutation(long no, List<T> items) {
return permutationHelper(no,
new LinkedList<>(Objects.requireNonNull(items)),
new ArrayList<>());
}
private static <T> List<T> permutationHelper(long no, LinkedList<T> in, List<T> out) {
if (in.isEmpty()) return out;
long subFactorial = factorial(in.size() - 1);
out.add(in.remove((int) (no / subFactorial)));
return permutationHelper((int) (no % subFactorial), in, out);
}
@SafeVarargs
@SuppressWarnings("varargs") // Creating a List from an array is safe
public static <T> Stream<Stream<T>> of(T... items) {
List<T> itemList = Arrays.asList(items);
return LongStream.range(0, factorial(items.length))
.mapToObj(no -> permutation(no, itemList).stream());
}
}
Examples
We start with testing our factorial() method a bit with the following code snippet:
List<String> items = Arrays.asList("A", "B", "C");
long permutations = Permutations.factorial(items.size());
System.out.println(items + " can be combined in " + permutations + " different ways:");
which will print out:[A, B, C] can be combined in 6 different ways:This looks encouraging. We know from the previous chapter that one can combine three distinct objects in six ways. So now we want to see facts on the table: What are those combinations? One way of seeing them all is to use our permutation() method. If we add the following code to our existing snippet:
LongStream.range(0, permutations).forEachOrdered(i -> {
System.out.println(i + ": " + Permutations.permutation(i, items));
});
We will get the following output:[A, B, C] can be combined in 6 different ways: 0: [A, B, C] 1: [A, C, B] 2: [B, A, C] 3: [B, C, A] 4: [C, A, B] 5: [C, B, A]Wow! It works. It looks exactly the same as in the table in the previous chapter. Now let's take the Permutaions.of() method for a spin like this:
Permutations.of("A", "B", "C")
.map(s -> s.collect(toList()))
.forEachOrdered(System.out::println);
The Permutations.of() method will provide all permutations of {A, B, C} and then we will collect those permutations into lists and subsequently print the lists like this:[A, B, C] [A, C, B] [B, A, C] [B, C, A] [C, A, B] [C, B, A]Sometimes we are interested in just generating a single sequence in all possible orders and this can also be done easily in a similar way like this:
Permutations.of("A", "B", "C")
.flatMap(Function.identity())
.forEachOrdered(System.out::print);
Which will produce:ABCACBBACBCACABCBA
Parallelism
As I mentioned, the Stream we get from Permutations.of() supports parallelism which is nice if you have a large number of permutaions and you want to put all your CPU:s to use. To be able to examine which threads are executing what, we will use a small support method:private static <T> void printThreadInfo(Stream<T> s) {
System.out.println(Thread.currentThread().getName() + " handles " + s.collect(toList()));
}
Now, let us examine which threads are being used by running the following line:Permutations.of("A", "B", "C").forEach(Main::printThreadInfo);
We will see something like this:main handles [A, B, C]
main handles [A, C, B]
main handles [B, A, C]
main handles [B, C, A]
main handles [C, A, B]
main handles [C, B, A]
This is logical. All our permutations are handled by the same thread (because we did not ask for a parallel stream). Now, let's modify the test line so it looks like this:Permutations.of("A", "B", "C").parallel().forEach(Main::printThreadInfo);
This will produce something similar to this;main handles [B, C, A]
main handles [C, B, A]
ForkJoinPool.commonPool-worker-2 handles [C, A, B]
ForkJoinPool.commonPool-worker-2 handles [A, B, C]
ForkJoinPool.commonPool-worker-2 handles [B, A, C]
ForkJoinPool.commonPool-worker-1 handles [A, C, B]
Apparently, on my computer, two combinations continued to execute on the main thread where as there were two other threads that (unevenly) shared the rest of the work.Laziness
It should be noted that the Stream in Permutations.of() produces the sequence of combinations lazily (or using other words, as they are needed). So, if we set up an enormous amount of combinations, but only need one, the stream will only produce that one and only combination. Let's take an example with 16 input items which corresponds to an extremely large number of permutations, something comparable with the national dept:
System.out.println(
Permutations.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
.findFirst()
.get()
.collect(toList())
);
This line will complete instantly and will return [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] which, unsurprisingly, is the first combination.
Testing
Permutations are great for testing! How many times have you asked yourself: "Have I tried all the possible combinations". Using Permutations, you can now be sure that you have tested every input combinations like in this simple outline (obviously, you need to replace System.out.println with something more useful):
Runnable setup = () -> System.out.println("setup connection");
Runnable send = () -> System.out.println("send data");
Runnable close = () -> System.out.println("close connection");
Permutations.of(setup, send, close)
.flatMap(Function.identity())
.forEachOrdered(Runnable::run);
The Morning
So, how does the optimal morning look like? Well, if you are alone at home, your day might start in many different ways, perhaps like this:Permutations.of(
"Get up",
"Brush teeths",
"Eat breakfast",
"Get dressed",
"Find wallet",
"Find computer"
)
.map(s -> s.collect(toList()))
.forEach(System.out::println);
So now you can pick your favorite from:[Get up, Brush teeths, Eat breakfast, Get dressed, Find wallet, Find computer]
[Get up, Brush teeths, Eat breakfast, Get dressed, Find computer, Find wallet]
[Get up, Brush teeths, Eat breakfast, Find wallet, Get dressed, Find computer]
[Get up, Brush teeths, Eat breakfast, Find wallet, Find computer, Get dressed]
[Get up, Brush teeths, Eat breakfast, Find computer, Get dressed, Find wallet]
[Get up, Brush teeths, Eat breakfast, Find computer, Find wallet, Get dressed]
... (713 other combinations) ...
[Find computer, Find wallet, Get dressed, Eat breakfast, Brush teeths, Get up]
With some preparation, even the last combination is really doable... Conclusions
Permutation is a powerful tool that is worth mastering.In this post, I have devised a very short and simple, yet reasonably efficient, implementation of a permutation support class for Java 8.
If you are writing unit tests, you should definitely know how to use permutations.
Take care, not to hit the "asymptotic wall" and limit the number of items that you work with when you are generating permutations.
Life is about picking the right choices, is it not?
This is a pretty cool post. What about combinations? Did you write about it?
ReplyDelete