Permutation – Java

What is the algorithm if we want to get the whole permutation combinations from a given array in java? I will introduce the algorithm in my own word:

We take [a, b, c] as an example.

We initialize an variable named as "cur", which means the current index we are concerning about how many different elements could be presented.

For example, when cur is 0. It means in index 0, how many different permutation we could have?

In this case, there are are 3 total results for the index 0. They are a, b, c. Because for the leading of our permutation combinations, we could let a, b, or c as the first elements.

1. a??
2. b??
3. c??

To achieve this target, we let the element in index 0 do a swap with all the rest elements including it-self:

cur - index 0
1. abc - a swap with indx 0: a
2. bac - a swap with index 1: b
3. cba - a swap with index 2: c

Till now, we have got all candidates in index 0 with swap. It’s turn to consider the next candidates in index 1. We will do a similar swap thing for each candidate in our first round.

cur - index 1
1.1 abc - b swap with index 1: b
1.2 acb - b swap with index 2: c
2.1 bac - a swap with index 1: a
2.2 bca - a swap with index 2: c
3.1 cba - b swap with index 1: b
3.2 cab - b swap with index 2: a

Now we have got all 6 candidates in our second index.

We can move forward for the third candidates in index 2, and swap the temporary candidate in index 2 with its following elements including its self. Finally, we could get our result as:

cur - index 2
abc - c swap with index 2 c
acb - b swap with index 2 b
bac ...
bca ...
cba ...
cab ...

For the time complexity:

O(N!/(N-k)!) = N * (N-1) * ... * (N-k+1)

To understand this, we could see when we are considering the candidates in index 0, we have to swap element in index 0 with all elements in the array, so that the time complexity would be O(N). However, when we are considering the element in index 1, we still need to swap the element in index 1 with the following elements except the element in index 0, so the time complexity is O(N-1). That’s the reason why we get the O(N (N-1) …. * (N-k+1)).