My code that determines if two arrays are permutations always returns false, why?

Question

I've written this to sort two arrays and then compare the values to see if they're the same, but it always returns false, and I can't figure out why.

It is supposed to find if two arrays are permutations of each other.

public class Permutations {

    public static void main(String[] args) {
        int[] a = {1,4,6,7,8,34};
        int[] b = {34,6,8,1,4,7};

        System.out.println(arePermutations(a, b));
    }

    public static boolean arePermutations(int[] a, int[] b)
    {
        int count = 0;
        int temp = 0;
        if(a.length == b.length)
        {
            for(int i=0; i<a.length-1; i++)
                for(int j=0; j<a.length-1; j++)
                    if(a[i] > a[j+1] && i>j+1)
                    {
                        temp = a[i];
                        a[i] = a[j+1];
                        a[j+1] = temp;
                    }
            {
                for(int i=0; i<b.length-1; i++)
                    for(int j=0; j<b.length-1; j++)
                        if(b[i] > b[j+1] && i>j+1)
                        {
                            temp = b[i];
                            b[i] = b[j+1];
                            b[j+1] = temp;
                        }
            }
            for(int i=0; i<a.length; i++)
                if(a[i] == b[i])
                {
                    count++;
                }
            if (count == a.length)
            {
                return true;
            }
            else return false;
        }
        else return false;

    }
}

You should make sorting into a separate function and test it by itself. — Ry-, Jun 04 '17 at 22:03
Please explain the steps so about what you are trying to do in this program. Also as pointed out above make the separate function for sorting and comparison. — Denis, Jun 04 '17 at 22:05
Why implement your own sort, which is potentially flawed, when the Java Runtime Library will do it for you? *FYI:* After "sorting", `a` is `[1, 8, 7, 6, 4, 34]` and `b` is `[34, 8, 6, 4, 1, 7]`. — Andreas, Jun 04 '17 at 22:14
Suggesting an alternative solution: use a key/value dictionary to map items to their number of occurrence. fill the dictionary while linearly iterating over the first array. update the dict data with a sweep through the second array, subtracting occurrences. the arrays are permutations of each other iff all entries of the second array exist as keys in the dict and all dict values after both passes are 0. Correctness (sketch): permutation equivalence means turning lists to multisets. Complexity: O(n) instead of O(n log n) when hashing keys (const dict lookup), ie. no sorting. — collapsar, Jun 05 '17 at 00:27

Jason · Answer 1 · 2017-06-04T22:38:11.063

The problem is in the implementation of the bubble sort. Change your sorting loops to the following:

    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a.length - 1; j++) {
            if (a[j] > a[j + 1]) {
                temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }

    for (int i = 0; i < b.length; i++) {
        for (int j = 0; j < b.length - 1; j++) {
            if (b[j] > b[j + 1]) {
                temp = b[j];
                b[j] = b[j + 1];
                b[j + 1] = temp;
            }
        }
    }

This code works because a bubble sort just swaps adjacent elements if they need swapping, but needs to run through the entire array multiple times (up to the number of items in the array) to get all the items into the correct position.

Your help is appreciated – Ski Mask The Slump God Jun 04 '17 at 22:49 — Ski Mask The Slump God, Jun 04 '17 at 22:49

My code that determines if two arrays are permutations always returns false, why?

1 Answers1