check if two arrays are permutations of each other recursive

Question

I have tried to write this recursive function, i am new to this and it seems to be quite difficult for me, to understand a recursive question and "translate" it into code.

We are given two arrays of integer numbers, and want to see if they are permutations of each other.

ex. a = {1,2,3,4} is a permutation of b = {4,3,2,1}

This is my try, the problem is whenever the function finds two cell (one each array) that are equals, the function returns true and won't keep checking the rest

public static boolean isPermutation(int[] a, int[] b,int indexA, int indexB){
    if(a.length != b.length || indexA > a.length || indexB > b.length)
        return false;
    if(a[indexA] == b[indexB]) {
        return true;
    }
    if(a[indexA] != b[indexB])
        return false;
    return isPermutation(a,b,indexA+1,0) || isPermutation(a,b,indexA,indexB+1);
}

Answer 1

The problem is that the challenge here is fundamentally not particularly well suited to a recursive solution. If the aim is simply to understand how to write a recursive function, that makes it a particularly bad idea to try to solve this particular problem in a recursive way.

The general way recursive functions are designed is as follows. As an example, let's look at the function 'fibbonacci', where fib(n) is simply fib(n-2) + fib(n-1), with fib(0) and fib(1) defined as 0 and 1 respectively.

• The algorithm starts by checking if the inputs are a trivial case - a really really simple case that has a trivial answer. For example, for the fib functions, we check if n is 0 or 1 and just return that straight away if so.
• Then, the algorithm is stated in terms of itself, but simpler versions of itself - it can call its own function as long as the inputs are 'simpler' - closer to that corner case covered in the first bullet. For our fib example, we can call fib(n-1) and fib(n-2), because that's "closer" to the trivial cases of 0 and 1.

... and that's all you have to do. That's a recursive algorithm:

int fib(int n) {
  if (n == 0 || n == 1) return n;
  return fib(n-1) + fib(n-2);
}

Let's now look at the algorithm you are trying to implement:

Imagine 4/3/2/1 and 1/3/4/2. A recursive algorithm could exist, but we have to adhere to the notion of 'a trivial case' and 'state the problem in terms of a simpler version of itself'.

The trivial case is easy enough: We can trivially determine that the empty list is a permutation of the empty list without recursion.

That means we need to state e.g. 4/3/2/1 and 1/3/4/2 into a simple operation + a simpler version of itself. The only obvious way to do that, is to take an arbitrary number from the first list, lets say 4, and first do the simple operation of checking if '4' is indeed in the second list. If not, we can stop right there and return false. If it is, we need to remove 4 from both lists first and then continue the algorithm by checking if 3/2/1 is a permutation of 1/3/2 - which we can do with recursion.

The problem is, recursion cannot use shared state. Thus, we need to clone the lists, which is very painful. It's a possible way to run the algorithm but it is incredibly inefficient: For each number in the list, you run through the entire second list (so for 2 lists that each have 100 numbers, that's 100100 = 10k steps), and we clone the entire list, minus 1 element (so that's 100 clones, each clone taking about between 1 and 100 steps, so another 5k with memory load to boot): The algorithm grows by the square of the input (if the inputs have 1000 entries each, it's 10001000+1000*500 = over a million steps). This is called an O(n^2) algorithm.

Contrast to a vastly simpler algorithm:

• Only in case we can't 'destroy' the input, make clones ONCE.
• Sort the clones. This is an O(n*log n) algorithm and built into java.
• Now check if the lists are identical, which is O(n).

For an algorithm that is O(n*log n) in total which is nearly linear. Where a recursive algorithm will eventually start taking days to do the job, this algorithm will do it in seconds.

And it's not an algorithm that lends itself to breaking it down into 'a trivial case' + 'a simple operation + an application of a simpler version of itself' which is what a recursive approach would require.

NB: In theory you can make your recursive algorithm 'merely' a basic O(n^2) case by not removing anything, but now e.g. list [4/4/3/2/1] and list [1/1/2/3/4] would be considered identical which is not really what 'check if A is a permutation of B' would entail, therefore, the step of 'once you find a match you have to remove those' can't really be skipped. However, if you do, it's still a crappy algorithm whose computation complexity grows faster than the solution of 'sort em both, then check if they are identical'.

The simple sorting solution:

Arrays.sort(a);
Arrays.sort(b);
return Arrays.equals(a, b);