Finding all permutations of a number without duplicates (edited for clarity)

Question

I've finished this challenge from Coderbyte, but inelegantly:

Have the function PrimeChecker(num) take num and return 1 if any arrangement of num comes out to be a prime number, otherwise return 0. For example: if num is 910, the output should be 1 because 910 can be arranged into 109 or 019, both of which are primes.

My solution works by producing an array of all possible permutations of the digits in the num argument, then scanning it for primes:

function PrimeChecker(num) {
    // Accounting for 1 not being a prime number by definition
    if (num == 1) {
        return 0;
    }
    // Defining an empty array into which all permutations of num will be put
    var resultsArray = [];
    // Breaking num into an array of single-character strings
    var unchangedArray = num.toString().split('');
    // Function to push all permutations of num into resultsArray using recursion
    function getAllCombos (array, count) {
        if (count === num.toString().length) {
            return;
        }
        else {
            for (var i = 0; i < array.length; i++) {
                var temp = array[count];
                array[count] = array[i];
                array[i] = temp;
                resultsArray.push(array.join(''));
            }
            return getAllCombos(array, count+1) || getAllCombos(unchangedArray, count+1);
        }
    }

    getAllCombos(unchangedArray, 0);

    // Converting the results from strings to numbers and checking for primes
    var numArr = [];
    resultsArray.forEach(function(val, indx) {
        return numArr[indx] = Number(val);
    });

    for (var i = 0; i < numArr.length; i++) {
        var prime = 1;
        for (var j = 2; j < numArr[i]; j++) {
            if (numArr[i] % j == 0) {
                prime = 0;
            }
        }
        if (prime == 1) {
            return prime;
        }
    }
    return 0;
}

The problem is that the array of permutations of the num argument which I'm producing is full of duplicates.. I feel like this can be done more efficiently.

For example, running PrimeChecker(123) results in a permutations array of 20 entries, when there only need be 6.

Does anyone have an idea of how to do this more efficiently?

You can find some efficient and elegant solution for generating a permutation of an array here: http://stackoverflow.com/questions/9960908/permutations-in-javascript — Huy Hoang Pham, May 18 '15 at 03:54

score 3 · Accepted Answer · edited May 23 '17 at 11:43

3

This is how I would do it:

var permute = (function () {
    return permute;

    function permute(list) {
        return list.length ?
            list.reduce(permutate, []) :
            [[]];
    }

    function permutate(permutations, item, index, list) {
        return permutations.concat(permute(
            list.slice(0, index).concat(
            list.slice(index + 1)))
            .map(concat, [item]));
    }

    function concat(list) {
        return this.concat(list);
    }
}());

function isPrime(n) {
    for (var i = 2, m = Math.sqrt(n); i <= m; i++)
        if (n % i === 0) return false;
    return true;
}

function PrimeChecker(num) {
    return permute(num.toString(10).split("")).some(function (xs) {
        return isPrime(parseInt(xs.join(""), 10));
    }) ? 1 : 0;
}

alert(PrimeChecker(910));

Here's the explanation of the algorithm for finding the permutations of the elements of an array.

Hope that helps.

edited May 23 '17 at 11:43

Community

1
1

answered May 18 '15 at 04:07

Aadit M Shah

72,912
30
168
299

I like what my beginner's brain is able to understand of this! A few thoughts: 1) I noticed in PrimeChecker() that you have defined the radix value as 10.. was this necessary? 2) I was quite confused until I sorted out that permute is being defined as an anonymous and immediately executing(?) function which returns an internally defined function of the same name. Is this a standard convention, assigning a variable to the same name as a function defined within it? 3) In isPrime(), I like how you limited the loop by Math.sqrt(n)! Very clever, saves a lot of processing time. – Manningham May 18 '15 at 06:30
1

@Manningham Yes, it is necessary and here is why: [How do I work around JavaScript's parseInt octal behavior?](http://stackoverflow.com/q/850341/783743) No, it's not a standard convention. It's my own personal convention. The reason I did this is because the `permutate` and `concat` functions are only used by the `permute` function. Hence, there's no reason that they should be visible to other functions. Hence, I created an [immediately invoked function expression](http://en.wikipedia.org/wiki/Immediately-invoked_function_expression). – Aadit M Shah May 18 '15 at 06:47
Thanks so much! I'm going to dive back into this after dinner. – Manningham May 18 '15 at 06:52

Finding all permutations of a number without duplicates (edited for clarity)

1 Answers1