我需要编写一个函数,从元素数组中获取两个或多个元素的所有唯一组合。我已经为此工作了几天了。我最初编写了单独的函数来获得一些不同大小的组合,这帮助我了解它们的相似之处,并且我希望能让我比迄今为止更接近可行的解决方案。这就是我到目前为止所拥有的......
function getAll (elements, comboSize, startingIndex) {
let finalStartingIndex = /*startingIndex + */elements.length - comboSize;
let finalIndex = finalStartingIndex + 1;
let tmpStartingIndex = startingIndex;
let qstrings = [];
if (finalIndex >= elements.length) {
finalIndex = finalStartingIndex;
}
if (finalStartingIndex < finalIndex) {
while (tmpStartingIndex <= finalStartingIndex) {
let nextIndex = tmpStartingIndex + 1;
while (nextIndex <= finalIndex) {
let tmpComboSize = comboSize - 1;
let tmpQstring = '';
let newQstring = '';
if (tmpComboSize > 1) {
tmpQstring = getAll(elements, tmpComboSize, nextIndex);
console.log('tmpQstring :: ', tmpQstring);
}
if (tmpQstring != '') {
newQstring = elements[tmpStartingIndex] + ', ' + tmpQstring[nextIndex];
console.log('tmpQstring[nextIndex] :: ', tmpQstring[nextIndex]);
console.log('newQstring :: ', newQstring);
}
let qstring = elements[tmpStartingIndex] + ', ' + elements[nextIndex];
qstrings.push(qstring);
nextIndex++;
}
/*nextIndex = tmpStartingIndex;
let tmpComboSize = comboSize - 1;
if (tmpComboSize > 1) {
let tmpQstring = getAll(elements, tmpComboSize, nextIndex);
let stringVal = elements[tmpStartingIndex] + ', ' + tmpQstring[nextIndex];
qstrings.push(stringVal);
}*/
tmpStartingIndex++;
}
} else {
qstrings[finalStartingIndex] = elements[startingIndex] + ', ' + elements[finalStartingIndex];
console.log(qstrings);
}
return qstrings;
}
function getAllTwo (elements, comboSize, startingIndex) {
let finalStartingIndex = startingIndex + elements.length - comboSize;
let finalIndex = finalStartingIndex + 1;
let tmpStartingIndex = startingIndex;
let qstrings = [];
while (tmpStartingIndex <= finalStartingIndex) {
let finalNextIndex = tmpStartingIndex + 1;
while (finalNextIndex <= finalIndex) {
let qstring = elements[tmpStartingIndex] + ', ' + elements[finalNextIndex];
qstrings.push(qstring);
finalNextIndex++;
}
tmpStartingIndex++;
}
return qstrings;
}
function getAllThree (elements, comboSize, startingIndex) {
let finalStartingIndex = startingIndex + elements.length - comboSize;
let finalFirstNextIndex = finalStartingIndex + 1;
let finalIndex = finalFirstNextIndex + 1;
let tmpStartingIndex = startingIndex;
let qstrings = [];
while (tmpStartingIndex <= finalStartingIndex) {
let firstNextIndex = tmpStartingIndex + 1;
while (firstNextIndex <= finalFirstNextIndex) {
let finalNextIndex = firstNextIndex + 1;
while (finalNextIndex <= finalIndex) {
let qstring = elements[tmpStartingIndex] + ', ' + elements[firstNextIndex] + ', ' + elements[finalNextIndex];
qstrings.push(qstring);
finalNextIndex++;
}
firstNextIndex++;
}
tmpStartingIndex++;
}
return qstrings;
}
function getAllFour (elements, comboSize, startingIndex) {
let finalStartingIndex = startingIndex + elements.length - comboSize;
let finalFirstNextIndex = finalStartingIndex + 1;
let finalSecondNextIndex = finalFirstNextIndex + 1;
let finalIndex = finalSecondNextIndex + 1;
let tmpStartingIndex = startingIndex;
let qstrings = [];
while (tmpStartingIndex <= finalStartingIndex) {
let firstNextIndex = tmpStartingIndex + 1;
while (firstNextIndex <= finalFirstNextIndex) {
let secondNextIndex = firstNextIndex + 1;
while (secondNextIndex <= finalSecondNextIndex) {
let finalNextIndex = secondNextIndex + 1;
while (finalNextIndex <= finalIndex) {
let qstring = elements[tmpStartingIndex] + ', ' + elements[firstNextIndex] + ', ' + elements[secondNextIndex] + ', ' + elements[finalNextIndex];
qstrings.push(qstring);
finalNextIndex++;
}
secondNextIndex++;
}
firstNextIndex++;
}
tmpStartingIndex++;
}
return qstrings;
}
function getAllFive (elements, comboSize, startingIndex) {
let finalStartingIndex = startingIndex + elements.length - comboSize;
let firstFinalIndex = finalStartingIndex + 1;
let secondFinalIndex = firstFinalIndex + 1;
let thirdFinalIndex = secondFinalIndex + 1;
let finalIndex = thirdFinalIndex + 1;
let tmpStartingIndex = startingIndex;
let qstrings = [];
while (tmpStartingIndex <= finalStartingIndex) {
let firstIndex = tmpStartingIndex + 1;
while (firstIndex <= firstFinalIndex) {
let secondIndex = firstIndex + 1;
while (secondIndex <= secondFinalIndex) {
let thirdIndex = secondIndex + 1;
while (thirdIndex <= thirdFinalIndex) {
let finalNextIndex = thirdIndex + 1;
while (finalNextIndex <= finalIndex) {
let qstring = elements[tmpStartingIndex] + ', ' + elements[firstIndex] + ', ' + elements[secondIndex] + ', ' + elements[thirdIndex] + ', ' + elements[finalNextIndex];
qstrings.push(qstring);
console.log('qstrings being built: ', qstrings);
finalNextIndex++;
}
thirdIndex++;
}
secondIndex++;
}
firstIndex++;
}
tmpStartingIndex++;
}
return qstrings;
}
let finalStrings = [];
let elements = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
for (let comboSize = 2; comboSize <= elements.length; comboSize++) {
let finalString = [];
let tstFinalString = [];
switch (comboSize) {
case 2:
tstFinalString = getAll(elements, comboSize, 0);
//console.log('tstFinalString, comboSize 2 :: ', tstFinalString);
//finalString = getAllTwo(elements, comboSize, 0);
break;
case 3:
tstFinalString = getAll(elements, comboSize, 0);
console.log('tstFinalString, comboSize 3 :: ', tstFinalString);
//finalString = getAllThree(elements, comboSize, 0);
break;
/*case 4:
finalString = getAllFour(elements, comboSize, 0);
break;
case 5:
finalString = getAllFive(elements, comboSize, 0);
console.log(finalString);
break;*/
default:
break;
}
finalStrings.push(finalString);
}
第一个函数是我对正确递归的尝试。目前,它可以得到所有两个元素的组合,但不能超出这个范围。我觉得有一些简单的东西我错过了,但我就是看不到它。我编写了其他函数来帮助我思考逻辑并确保我得到了我期望的数据。这些功能确实有效,但显然它不可扩展。如果您能提供任何帮助来指出我所缺少的内容,我们将不胜感激。
哦,如果这很重要的话,目前这是用 Javascript 编写的。
最佳答案
我认为这或多或少是 k
大小组合的规范方式。
// return n choose k combinations
function choose(arr, k, prefix=[], i=0){
// if the remainder of the array will complete the
// combination length exactly, combine it with
// the current prefix and add to results
if (prefix.length + arr.length - i == k){
return [prefix.concat(arr.slice(i))];
// if the prefix is long enough, add it to the results
} else if (prefix.length == k){
return [prefix];
// otherwise, push combinations with and without
// the current element
} else {
return choose(arr, k, prefix.concat(arr[i]), i + 1)
.concat(choose(arr, k, prefix, i + 1));
}
}
let arr = ["A","B","C","D","E"];
console.log('Input: ' + JSON.stringify(arr) + '\n');
let cs = choose(arr, 3);
console.log('\nOutput:');
for (let c of cs)
console.log(JSON.stringify(c));
为了获得全部,我们可以这样做:
function powerset(arr, prefix=[], i=0){
if (i == arr.length)
return [prefix];
return powerset(arr, prefix.concat(arr[i]), i + 1)
.concat(powerset(arr, prefix, i + 1));
}
let arr = ['a', 'b', 'c', 'd', 'e'];
let ps = powerset(arr);
for (let s of ps)
console.log(JSON.stringify(s));
关于javascript - 递归函数以获得两个或多个的所有唯一组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54917181/