0

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)
  • Can add arguments to the function.
  • Can NOT use local array.
  • Can NOT use loops.
  • Can NOT use library functions.
  • Can NOT change the arrays.

Does anyone have an idea?

Frank Bryce
  • 8,076
  • 4
  • 38
  • 56
Zvi vex
  • 53
  • 5
  • 3
    `return Arrays.equals(Arrays.sort(a), Arrays.sort(b))` – SMA Jan 06 '16 at 18:35
  • @SMA can't use library functions – Zvi vex Jan 06 '16 at 18:38
  • You could recurse through list a, comparing each element in a with b to see if b also has that element, if it doesn't return false, if you have no more elements, return true – dbrown93 Jan 06 '16 at 18:48
  • @dbrown93 and if a = {1,2,3,4,4} b = {4,2,4,1,3}? – Zvi vex Jan 06 '16 at 18:49
  • @Zvikivex I don't really know what you're asking. A naive solution would be to recurse for each element in the first list, then either have another method that recurses through b to see if that element from a is in b, or use a for loop to see if that element is in b – dbrown93 Jan 06 '16 at 18:51
  • Was my answer a good answer for you, Zviki? – Frank Bryce Jan 12 '16 at 15:40

2 Answers2

3

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);
Frank Bryce
  • 8,076
  • 4
  • 38
  • 56
-1

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

st2rseeker
  • 473
  • 1
  • 5
  • 28
  • 1
    Your premise: Given `p` and `s`, if `x*y*z*... = p` and `x+y+z+... = s`, then there is a unique `x`, `y`, `z`, `...` that fulfills this requirement, but this is false. For instance, `[2,3,4]` and `[1,2,6]` would be permutations with this algorithm! – Frank Bryce Jan 16 '16 at 18:42
  • 1
    However, the idea is still a good one I think, but instead of `*` and `+`, you could conceivable create a commutative hashing function which takes a stream of inputs and outputs a value (perhaps an integer). Then you'd have very low probability of a false positive, but still there could be a collision because of the pigeon hole principle. `n^m > n`. – Frank Bryce Jan 16 '16 at 18:46
  • Good point, actually - thank you. I'll leave the answer to keep your comment. – st2rseeker Jan 16 '16 at 19:19