javascript - 递归函数以获得两个或多个的所有唯一组合

Question

我需要编写一个函数，从元素数组中获取两个或多个元素的所有唯一组合。我已经为此工作了几天。我最初编写了单独的函数来获得几个不同大小的组合，这帮助我了解了它们的相似之处，我希望能让我比目前更接近一个可行的解决方案。这是我目前所拥有的......

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 编写的。

Answer 1

我认为这或多或少是 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));