CODEWITHSUNDEEP
javaarraysrecursionpermutation
Zvi vex
Zvi vex

Reputation: 53

Find whether 2 arrays are permutations of each other recursively in Java

I need to build a recursive function that returns true if array a is permutation of array b and false otherwise.

public static boolean isPermutation (int [] a, int [] b)

Does anyone have an idea?

Upvotes: 0

Views: 965

Answers (2)

st2rseeker
st2rseeker

Reputation: 483

The idea is the following: it's a permutation if the product of all members in a is equal to the product of all members in b AND the sum of all members in a is equal to the sum of all members in b.

Write a recursive helper function that will allow you to compute these sums and products and compare them.

Complexity: O(n)

Caveat: can overflow if dealing with many large numbers

See the comments for an important point made by John Carpenter

Upvotes: -1

Frank Bryce
Frank Bryce

Reputation: 8446

This should work for you, it's basically a loop implemented with recursion. This should execute in quadratic time.

public static boolean isPermutation(int[] a, int[] b, boolean[] ataken, boolean[] btaken, int iter, int totalTaken, int aidx, int bidx)
{
    if (a.length != b.length) return false;

    // totalTaken is a count of the number of matches we've "taken"
    if(totalTaken == a.length) return true;

    // don't "loop" b
    if(bidx >= b.length)
    {
        return false;
    }

    // we should loop through a... this will yield a quadratic runtime speed
    if(aidx >= a.length)
    {
        if (iter < a.length)
        {
            return isPermutation(a, b, ataken, btaken, iter + 1, totalTaken, 0, bidx);
        }

        // finished our loop, and "totalTaken" wasn't the whole array
        return false;
    }

    // found a match for this b[bidx]
    if(a[aidx] == b[bidx] && !ataken[aidx] && !btaken[bidx])
    {
        ataken[aidx] = true;
        btaken[bidx] = true;
        return isPermutation(a, b, ataken, btaken, iter, totalTaken + 1, aidx + 1, bidx + 1);
    }

    // loop through a
    return isPermutation(a, b, ataken, btaken, iter, totalTaken, aidx + 1, bidx);
}

You call it with ataken and btaken arrays filled with false, but of the same length as a and b, respectively.

var isPerm = staticClassName.isPermutation(a, b, ataken, btaken, 0, 0, 0, 0);

Upvotes: 3

Related Questions