Permutations, variations and combinations with/without repetition

[mmirwaldt]

Some tests use permutations, variations and combinations with/without repetition as test data.
E.g. you want to test whether your customized sorting algorithm works correct:
Then you want to check if permutations of your test data always lead to the same result.
So [1,4,3,5,7,6,9,2,0,8], [3,1,7,2,9,0,8,6,4,5], ... must all result in [0,1,2,3,4,5,6,7,8,9].
You might think now creating permutations is easy. If you, however, implement a generator, you might end up with this primitive brute force algorithm:

public static List<List<Integer>> permutateRecursiveSlow(List<Integer> elements) {
    List<List<Integer>> permutations = new ArrayList<>();
    permutateRecursiveSlow(elements, new ArrayList<>(elements.size()), permutations);
    return permutations;
}

public static void permutateRecursiveSlow(List<Integer> elements, List<Integer> permutation, List<List<Integer>> permutations) {
    if (elements.size() == permutation.size()) {
        permutations.add(List.copyOf(permutation));
    } else {
        for (int i = 0; i < elements.size(); i++) {
            Integer element = elements.get(i);
            if (!permutation.contains(element)) {
                permutation.add(element);
                permutateRecursiveSlow(elements, permutation, permutations);
                permutation.remove(permutation.size()-1);
            }
        }
    }
}

Unfortunately, this solution doesn't scale very well.
E.g. if you want to generate all permutations of all 10 digits from 0 to 9, you end up trying out 10^10=10,000,000,000 combinations although only 10!=3,628,800 permutations exist.
You can, of course, lookup on wikipedia solutions for better permutation generators but a more efficient solution can just look like this:

public static List<List<Integer>> permutateRecursiveFast(List<Integer> elements) {
    List<List<Integer>> permutations = new ArrayList<>();
    List<Integer> permutation = new ArrayList<>();
    for (int i = 0; i < elements.size(); i++) {
        permutation.add(null);
    }
    permutateRecursiveFast(elements, 0, permutation, permutations);
    return permutations;
}

public static void permutateRecursiveFast(List<Integer> elements, int index, List<Integer> permutation, List<List<Integer>> permutations) {
    if (index == permutation.size()) {
        permutations.add(List.copyOf(permutation));
    } else {
        int maxLength = permutation.size() - index;
        for (int i = 0; i < maxLength; i++) {
            Integer element = elements.get(index);
            int position = permutation.indexOf(null);
            for (int j = 1; j <= i; j++) {
                position = position + permutation.subList(position + 1, permutation.size()).indexOf(null);
            }
            permutation.set(position, element);
            permutateRecursiveFast(elements, index + 1, permutation, permutations);
            permutation.set(position, null);
        }
    }
}

This solution only produces the possible permutations without brute force.
Therefore, writing generators for permutations, variations and combinations with/without repetition can be very tricky.
And they can be a very nice future feature for testers who use JUnit-Pioneer.
(Please ignore for the moment that the result is a list of all permutations. The permutations can also be provided by a stream on demand. And yes, support for primitive types like ints is possible as well. This code is only a draft.)
What do you think?

P.S.: Permutations would be the start and variations and combinations would follow as they all three are the most common cases of combinatorics.

[Michael1993]

Interesting idea! I'm not entirely sure I understand it correctly... How does this differ from @CartesianTest?

[mmirwaldt]

Interesting idea! I'm not entirely sure I understand it correctly... How does this differ from @CartesianTest?

A @CartesianTest combines the elements of two sets to pairs and tests them. This is very useful.
However, it won't help you if you want to test your sorting algorithm, e.g. an implementation of Counting Sort.
You need the elements of an unsorted set as a list in all kinds of different orders for that, i.e. you need their permutations.
All those input permutations must always lead to the one and only sorted output permutation in all tests.
That's what my idea is about. I have started to prepare a demo on a github repo to help you understand that idea better and easier. I can't fiinish it tonight, unfortunately. I come back soon with concrete examples.

[nipafx]

This is a cool idea! 😎

What I didn't quite get so far is how exactly this leads to test cases. As far as I understand, the sequence is:

1. configure something that states "give me permutations of [x, y. z]
2. extension generates [x, y, z], [x, z, y], [y, x, z], [y, z, x], [z, x, y], [z, y, x]
3. six tests get executed, each with one permutation

But we need more than one parameter, right? In the sorting example from earlier, [x, y, z] as the correct solution should also be passed to the test, right? This leads me to the question, which of these should it be:

• a new TestTemplate extension
• a generator for parameterized tests (not sure whether that's possible)
• a generator for a single parameter of a cartesian test

We don't need to answer this question immediately. On the contrary, it may be interesting to pursue all two or three for a bit and see where that leads.

[mmirwaldt]

I have created this github repo for you with a generator and a demo (called sample in that project):
https://github.com/mmirwaldt/CombinatoricsForJunitPioneer
If you want to understand for what you need my stuff, then just ask yourself for a moment how would you properly test a sorting algorithm with JUnit Pioneer as it is.

IMPORTANT: This project is a DRAFT and I am pretty sure you will immediately find a lot what can be improved.
Moreover, the test suite in that project has got 20140 tests which are too many.

A short description:
/
You can find two modules:

• generators includes the interface CombinatorialGenerator with three implementations.
• samples includes the two samples CountingSort and LargestNumberCombiner.

The generators are LoopingGenerator, RecursionGenerator and BruteForceGenerator.
BruteForceGenerator only exists to test LoopingGenerator while LoopingGenerator should be used for tests.
RecursionGenerator only exists to understand better how permutations, variations and combinations can be generated.

The sample is about two counting sort implementations:
One which accepts duplicates (ByteArrayCountingSorter) and one which doesn't accept duplicates (BitSetCountingSorter).
They are tested by permutations and variations.

If you can't remember what the differences were:
Look into the extensive javadoc comments to CombinatorialGenerator which explain you a lot.
Look into BasicGeneratorTest which tests CombinatorialGenerator implementations.
Look into RecursionGenerator and BruteForceGenerator to understand how generators can work.

I hope you find it interesting.
Feel free to ask questions.

[mmirwaldt]

/> This is a cool idea! 😎

Thanks. I have always wanted to contribute something wonderful to your great JUnit Pioneer project!

What I didn't quite get so far is how exactly this leads to test cases. As far as I understand, the sequence is:

1. configure something that states "give me permutations of [x, y. z]

2. extension generates [x, y, z], [x, z, y], [y, x, z], [y, z, x], [z, x, y], [z, y, x]

3. six tests get executed, each with one permutation

Yes, exactly. Those are permutations without repetition. Just look into BitSetCountingSorterTest and ByteArrayCountingSorterTest to watch them in action.

But we need more than one parameter, right? In the sorting example from earlier, [x, y, z] as the correct solution should also be passed to the test, right? This leads me to the question, which of these should it be:

* a new TestTemplate extension

* a generator for parameterized tests (not sure whether that's possible)

* a generator for a single parameter of a cartesian test

You always need a list of elements which can be numbers, strings or other objects.
That alone is enough for permutations without repetition.
You must tell how many elements must be used for variations and combinations (the k-parameter).
Only for permutations with repetition, you must tell how frequent the elements occur.
Have a look on the interface CombinatorialGenerator for the needed parameters.

It seems to me "a generator for parameterized tests" might be a good way to integrate the combinatorial generator into JUnit Pioneer. It can look similar to a CartesianTest.

We don't need to answer this question immediately. On the contrary, it may be interesting to pursue all two or three for a bit and see where that leads.

I am very confident we find a good way to integrate the combinatorial generator into JUnit Pioneer.

[Michael1993]

We had a call and the demo looks great. I asked @mmirwaldt to go ahead with a PR. 😄