All permutations of the pairs that add to squares

Question

Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number.

E.g: Given an input number of 16, one of the possible answers would be:

8:1:15:10:6:3:13:12:4:5:11:14:2:7:9:16

and its reverse.

Note that the function called hasIntegerRoot has been commented out for a purpose. I would appreciate if reviewer would chose me to use hasIntegerRoot over currently used List<Integer> squareList.

I'm looking for code review, best practices, optimizations etc.

Verifying Complexity (where \$n\$ is the input number):

• Time: \$O(n!)\$
• Space: \$O(n!)\$

public final class PairSquare {

    private PairSquare() {};

    /**
     *  Given a number, this program would find "all permutations of the pairs that add to squares" from 1 to number"
     * 
     * @param num        The number upto which adjacent numbers should sum to a sqaure 
     * @return           A List of all the lists/chains of integers such that adjacent numbers sum upto a square.
     */
    public static List<List<Integer>> pairSquare (int num) {
        if (num <= 0) throw new IllegalArgumentException("The input number " + num + " should be less than equal to zero.");

        final List<List<Integer>> pairSquaresList = new ArrayList<List<Integer>>();
        final List<Integer> squareList = squareList(num);
        final LinkedHashSet<Integer> elements = new LinkedHashSet<Integer>();
        for (int i = 1; i <= num; i++) { 
            elements.add(i);
            getSqaureLists(i, num, elements, pairSquaresList, squareList);
            elements.remove(i);
        }
        return pairSquaresList;
    }

    private static List<Integer> squareList(int num) {
        int limit = num + (num  - 1);
        int n = 2;
        final List<Integer> sqaureList = new ArrayList<Integer>();
        int square;
        while ((square = n * n) <= limit) {
            sqaureList.add(square);
            n++;
        }
        return sqaureList;
    }

//    private static boolean hasIntegerRoot(int x) {
//        double root = Math.sqrt(x);
//        return  root == (int)root;
//    }

    private static void getSqaureLists(int currNum, int num, LinkedHashSet<Integer> elements, List<List<Integer>> pairSquareList, List<Integer> squareList) {
        if (elements.size() == num) {
            pairSquareList.add(new ArrayList<Integer>(elements));
            return;
        }

        for (int i = 1; i <= num; i++) {
            // a number has already been added in the list. deduping.
            if (elements.contains(i))  continue;

//            // checking if the adjacent numbers add up to a square of an int.
//            if (hasIntegerRoot(i + currNum)) {
//                elements.add(i);
//                getSqaureLists(i, num, elements, pairSquareList, squareList);
//            }

            if (squareList.contains(i + currNum)) {
                elements.add(i);
                getSqaureLists(i, num, elements, pairSquareList, squareList);
            }

            elements.remove(i);
        }
        return;
    }

    public static void main(String[] args) {
        List<Integer> list1 = Arrays.asList(8, 1, 15, 10, 6, 3, 13, 12, 4, 5, 11, 14, 2, 7, 9, 16);
        List<Integer> list2 = Arrays.asList(16, 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8);

        List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
        listOfLists.add(list1);
        listOfLists.add(list2);

        Assert.assertEquals(listOfLists, pairSquare(16));
    }
}

Answer 1

Since you don't seem to be concerned with the order of any of the collections of objects you use, only membership in those collections, Set is probably the better Collection to use, instead of List. I imagine that Set.contains is going to be more efficient than List.contains.

Also, it's not clear to me that recursion is the way to go here. If I were you, I would try to walk through the code with a low value for the input number and see what it's doing. It looks like for every integer between 1 and num, you're calling getSqaureLists num x num times. That seems like overkill. Recursion typically does some work and then passes a smaller set of work to the recursive call. You need to clarify how you split up that work. If that's not working, a iterative solution might be clearer.

You also have some code to check for duplicates. You shouldn't need to do that. Whether you a doing an iterative or recursive solution, you should be able to avoid ever testing duplicate values.

Answer 2

Meaningful names - names like PairSqaure, squareList, pairSquareList do not add any information about the code, and are similar enough to confuse. Other names like i, num, elements are even less helpful. findPairsThatAddUpToSquares(int maxValue) is much more valuable, and make most of the documentation redundant.

Don't use the same name twice - you use squareList as a method name as well as a variable name, this is unreadable, and potentially error prone.

Don't overkill - the problem is finding all pairs of numbers which correspond to some restriction - it's like writing a big table with n lines and n rows, and marking each one which fits - that would be \$O(n^2)\$, anything more complex would be wrong. Your use of recursion is unclear, and I can't see the point of it a simple loop would suffice:

for (int highNum = 2; highNum <= maxNum; highNum++) {
    for (int lowNum = 1; lowNum < highNuml; lowNum++) {
        if (fitsTheBill(lowNum, highNum)) {
            results.add(new int[] { lowNum, highNum });
            results.add(new int[] { highNum, lowNum });
        }
    }
}

Use correct container - using a pre-calculated table of squares is fine, but if you put it in an ArrayList, each contains will cost you \$O(n)\$. Using Set will do the same thing in \$O(1)\$.

Unclear requirements - "all permutations of the pairs that add to squares" - what I understand from this is that the result should be a list of pairs containing [n,m] and [m,n] for each pair that adds to a square, you sample output though is two arrays containing a list of numbers in which every item[i]+item[i+1] adds up to a square. This may be what you meant, but this hardly constitutes all permutations of such an answer - 15:10:6:3:13:12:4:5:11:14:2:7:9:16:8:1 will also qualify, but it is not part of your answer...

Here is a refactored solution with complexity of \$O(n^2)\$ in time and \$O(n)\$ in space:

public final class PairsThatAddUpToSquaresFinder {

    private PairsThatAddUpToSquaresFinder() {};

    public static List<List<Integer>> findPairsThatAddUpToSquares (int maxValue) {
        if (maxValue <= 0) throw new IllegalArgumentException("The input number " + maxValue + " should be less than equal to zero.");

        final List<Integer> pairsThatAddUpToSquares = new ArrayList<Integer>();
        final Set<Integer> precalculatedSquares = calculateAllSquaresUpTo(maxValue);
        for (int highNum = 2; highNum <= maxValue; highNum++) {
            for (int lowNum = 1; lowNum < highNuml; lowNum++) {
                if (precalculatedSquares.contains(lowNum + highNum)) {
                    pairsThatAddUpToSquares.add(lowNum);
                    pairsThatAddUpToSquares.add(highNum);
                }
            }
        }
        final List<List<Integer>> result = new ArrayList<List<Integer>>();
        result.add(pairsThatAddUpToSquares);
        result.add(Collections.reverse(pairsThatAddUpToSquares.clone()));
        return result;
    }

    private static List<Integer> calculateAllSquaresUpTo(int maxValue) {
        int limit = maxValue + (maxValue  - 1);
        int n = 2;
        final List<Integer> sqaureList = new ArrayList<Integer>();
        int square;
        while ((square = n * n) <= limit) {
            sqaureList.add(square);
            n++;
        }
        return sqaureList;
    }
}