2

我的任务是创建一个由所有排列/给定数字数组的 4 位数字组成的数组：[1,2,3,4,5,6,7,8,9]。不能有重复的数字，因为每个值必须是唯一的。以下是我的解决方案，但我正在努力将递归应用于该过程。我希望它具有适应性，因此如果条件发生变化，即函数必须生成 5 位数字甚至 6 位数字的所有组合，因为需要更改的代码很少，并且添加递归可以轻松实现这一点。正如您在下面看到的，代码确实可以工作，但如果条件改变，这将需要更多的嵌套 for 循环。我正在寻找递归解决方案。这似乎不是一个好的解决方案，但任何建议将不胜感激。我在网上看到很多关于创建 4P4 或 5P5 但不是 9P5 样式的解决方案。我试图应用堆的算法但没有成功。

function arrayCreate((availableNumbers, userNumberArray)) {

var possibleValues = []; //empty array to house all the possible combination of values that the user could enter i.e. 1234 to 9876
var numberOfPermutations = (factorial(availableNumbers.length) / factorial(availableNumbers.length - userNumberArray.length));

var adding = true;
var firstDigit, secondDigit, thirdDigit, forthDigit =0;
var possibleDigitValue = "";


while (adding === true) {
    for (var i = 0; i < availableNumbers.length; i++) {
        firstDigit = availableNumbers[i];
        availableNumbers.splice(i, 1);
        for (var j = 0; j < availableNumbers.length; j++) {
            secondDigit = availableNumbers[j];
            availableNumbers.splice(j, 1);
            for (var k = 0; k < availableNumbers.length; k++) {
                thirdDigit = availableNumbers[k]
                availableNumbers.splice(k, 1);
                for (var l = 0; l < availableNumbers.length; l++) {
                    forthDigit = availableNumbers[l];
                    possibleDigitValue = (firstDigit + secondDigit + thirdDigit + forthDigit);
                    possibleValues.push(possibleDigitValue);
                }
                availableNumbers.splice(k, 0, thirdDigit);
            }
            availableNumbers.splice(j, 0, secondDigit);
        }
        availableNumbers.splice(i, 0, firstDigit);
        if (possibleValues.length >= numberOfPermutations) {
            adding = false;
        }
    }
    console.log(possibleValues);
    return possibleValues;
}
}
arrayCreate([1,2,3,4,5,6,7,8,9],[0,0,0,0]);


var userNumberArray = ['0', '0', '0', '0']; //empty array of 0's as this value is not allowed, this array will store the computers auto-generated number
        var availableNumbers = ['1', '2', '3', '4', '5', '6', '7', '8', '9'] //array of available numbers to be picked and added to the computerNumber array
        


//this function is used later to calculate the possible permutations of combinations of user guess
function factorial(x) {
    if (x === 0) { return 1; }
    else{
        return x * factorial(x-1);
    }
}


function arrayCreate(availableNumbers, userNumberArray) {

    var possibleValues = []; //empty array to house all the possible combination of values that the user could enter i.e. 1234 to 9876
    var numberOfPermutations = (factorial(availableNumbers.length) / factorial(availableNumbers.length - userNumberArray.length));

    var adding = true;
    var firstDigit, secondDigit, thirdDigit, forthDigit =0;
    var possibleDigitValue = "";


    while (adding === true) {
        for (var i = 0; i < availableNumbers.length; i++) {
            firstDigit = availableNumbers[i];
            availableNumbers.splice(i, 1);
            for (var j = 0; j < availableNumbers.length; j++) {
                secondDigit = availableNumbers[j];
                availableNumbers.splice(j, 1);
                for (var k = 0; k < availableNumbers.length; k++) {
                    thirdDigit = availableNumbers[k]
                    availableNumbers.splice(k, 1);
                    for (var l = 0; l < availableNumbers.length; l++) {
                        forthDigit = availableNumbers[l];
                        possibleDigitValue = (firstDigit + secondDigit + thirdDigit + forthDigit);
                        possibleValues.push(possibleDigitValue);
                    }
                    availableNumbers.splice(k, 0, thirdDigit);
                }
                availableNumbers.splice(j, 0, secondDigit);
            }
            availableNumbers.splice(i, 0, firstDigit);
            if (possibleValues.length >= numberOfPermutations) {
                adding = false;
            }
        }
        return possibleValues;
    }
}
console.log(arrayCreate(availableNumbers, userNumberArray));

4

2 回答 2

3

您可以通过迭代项目并检查之前是否已选择该项目来采用递归方法。如果没有，则取出该项目并检查零件数组的长度。

如果它具有所需的长度，则将部分数组放入结果中。

如果不是，则迭代给定的数组并交出零件数组。

function arrayCreate(array, size) {
    var result = [];
    array.forEach(function iter(parts) {
        return function (v) {
            var temp = parts.concat(v);
            if (parts.includes(v)) {
                return;
            }
            if (temp.length === size) {
                result.push(temp);
                return;
            }
            array.forEach(iter(temp));
        }
    }([]));
    return result;
}

console.log(arrayCreate([1, 2, 3, 4, 5, 6, 7, 8, 9], 4).map(a => a.join('')));
console.log(arrayCreate([1, 2, 3, 4, 5, 6, 7, 8, 9], 5).map(a => a.join('')));
console.log(arrayCreate([1, 2, 3, 4, 5, 6, 7, 8, 9], 6).map(a => a.join('')));
.as-console-wrapper { max-height: 100% !important; top: 0; }

具有分离功能iter。

function arrayCreate(array, size) {

    function iter(parts) {
        return function (v) {
            var temp = parts.concat(v);
            if (parts.includes(v)) {
                return;
            }
            if (temp.length === size) {
                result.push(temp);
                return;
            }
            array.forEach(iter(temp));
        }
    }

    var result = [];
    array.forEach(iter([]));
    return result;
}

console.log(arrayCreate([1, 2, 3, 4, 5, 6, 7, 8, 9], 4).map(a => a.join('')));
console.log(arrayCreate([1, 2, 3, 4, 5, 6, 7, 8, 9], 5).map(a => a.join('')));
console.log(arrayCreate([1, 2, 3, 4, 5, 6, 7, 8, 9], 6).map(a => a.join('')));
.as-console-wrapper { max-height: 100% !important; top: 0; }

于 2018-04-04T13:50:37.027 回答
-1

任何尺寸和任何选项的解决方案

const makeUniqPermutations = (size, options) => {
    if (size > options.length) {
        throw new Error('Cannot make uniq permutations with that size and options');
    }

    if (size === 0) {
	return [''];
    }

    const permutations = options.reduce((acc, option, index) => {
	const restSize = size - 1;

        const restOptions = [
            ...options.slice(0, index),
            ...options.slice(index + 1),
        ];

	const restPermutations = makeUniqPermutations(restSize, restOptions);
	const newPermutations = restPermutations.map(permutation => `${option}${permutation}`);

	return [...acc, ...newPermutations];
    }, [])

    return permutations;
}

const options = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
const size = 4;

console.log(makeUniqPermutations(size, options));

于 2018-04-04T13:51:39.093 回答