javascript - 查找一个数字的所有排列而不重复(为清楚起见进行了编辑)

Question

我已经完成了来自 Coderbyte 的挑战，但不够优雅:

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.

我的解决方案的工作原理是生成 num 参数中数字所有可能排列的数组，然后扫描它以查找素数:

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;
}

问题是我生成的 num 参数的排列数组充满了重复项。我觉得这可以更有效地完成。

例如，运行 PrimeChecker(123) 会产生一个包含 20 个条目的排列数组，而实际上只需要 6 个条目。

有没有人知道如何更有效地做到这一点？

Answer 1

我会这样做:

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));

这是 explanation of the algorithm for finding the permutations of the elements of an array .

希望对您有所帮助。