Challenge

Technical challenge for an interview at Credimi S.p.A.

Suppose you're given a file with a single string of comma separated numbers like the following

$ cat input  
123,456,789

Your program must print to STDOUT all possible permutations with repetitions, like follows (actual order is not relevant)

$ cat input | <your program> > output  
$ cat output  
123,456,789  
123,789,456  
456,789,123  
456,123,789  
789,123,456  
789,456,123  

Your solution must print to STDOUT and any extraneous output will be considered an error (but you may print to STDERR at your convenience). Your program will be tested against inputs of growing size, the more they can take, the better!

The solution must contain documentation explaining time and space complexity of your implementation.

You should use only the standard library of your language of choice, any additional requirement should be documented and motivated.

Java, Python, Scala or Rust are preferred.

Solution

Typo

The challenge description contains an error.
It asks to print all possible permutations WITH repetitions, but the example shows the permutations without repetition.
If we consider permutations with repetitions, we would also need an additional parameter that is the desired length of the permutation. The typo is probably "with repetition" instead of "without repetition".

Algorithm

The most efficient algorithm to compute all permutations is Heap's Algorithm.
It minimizes elements swapping: every permutation is generated interchanging a single pair of elements from the previous one.

Heap algorithm cannot be parallelized, we could use a less efficient algorithm with better average time assuming thread count > 1 (see for example Ouellet Indexed).
However, the bottleneck of our program is the writing to stdout, in some tests I saw that the multi-threaded version is actually slower, because threads need to synchronize to write to the output.

Choices

Element types

The challenge description does not specify the type of the input elements, they are just "numbers".
I decided to represent them with the Java primitive type long.
There is no noticeable performance improvement representing them with an int instead.

Repeated elements

It's not specified what is the desired output if a number is repeated.
I've decided to not check for duplicate elements, since they affect the algorithm time and space complexity.
If one or more numbers is repeated, some permutations will be duplicated:

$ echo "1,1" | <my program>
1,1
1,1

Implementation

I wrote the project in Java because it's the language where I have more experience.
It's a maven project that targets JDK11+.

Time and space complexity

Given n elements, there are n! permutations. Heap's algorithm compute a new permutation in O(1) time. Each permutation of n elements must also be printed to the stdout (O(n) time).
Time complexity is O(n*n!).

The program uses two n sized arrays and a fixed buffer. Space complexity is O(n).

Classes

I divided the program into three classes:

• ElementsInputReader: to read the input elements.
• PermutationsGenerator: to compute all the elements permutations.
• PermutationsPrinter: to print permutations to the output.

Generics

I didn't use generics to compute permutations of an array T[] because the program performance would be a lot worse than using primitive types.

How to run the application

Compilation

If you have JDK11+ and Maven installed, you can simply run

mvn package

The jar file will be in target/permutations.jar.

Otherwise, you can use the provided Dockerfile

docker build -t permutations .

(Maven compilation fails if you had built the project locally, be sure to delete target directory).

Run

If you have built the project using Docker, you can simply run it

echo 1,2,3 | docker run --rm -i permutations

However running it with Docker has a big effect on performances.
To extract the jar file, run

docker create --name permutations permutations
docker cp permutations:/app/permutations.jar .

Then run it with locally installed JRE (11+)

echo 1,2,3 | java -jar permutations.jar