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}
Take a look at the first item in each row and you will see that it is changing in sequence of the input list. Let
n be the number of items in the input
List (
n = 4) and
subFactorial be (
n-1)! (
subFactorial = (4-1)! = 3! = 6) then the first item in the list for permutation
no is at index
no/subFactorial. In the example above, the first item for permutation 15 is at index
no/subFactorial = 15/6 = 2, which corresponds to "C" (remember that "A" is at index 0, "B" is at index 1 and so forth).
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?
In my previous post, I wrote about Escape Analysis and how the JVM can allocate non-escaping objects on the stack rather than on the heap. I immediately got a very interesting question from Caleb Cushing asking if Objects that actually can escape could be optimized anyhow, provided that that escaped object is reasonably contained by the caller.
