Рекурсивная функция для получения всех уникальных комбинаций двух или более

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

Вот еще один способ использования генераторов.Преимущество этого подхода состоит в том, что комбинации генерируются лениво.В зависимости от ваших расчетов иногда вы можете получить желаемый результат, прежде чем генерировать все комбинации.Поскольку многие комбинаторные задачи включают в себя огромные наборы комбинаций, мы можем потенциально сэкономить много ресурсов от пропуска генерации ненужных комбинаций.Кроме того, эта концепция может быть расширена для работы с бесконечными потоками, где возможно получение бесконечного числа комбинаций.

const append = (xs, x) =>
  xs .concat ([ x ])

const ncomb = function* (n, xs = [])
{ const gen = function* (n, acc)
  { if (n === 0)
      yield acc
    else
      for (const x of xs)
        yield* gen (n - 1, append (acc, x))
  }
  yield* gen (n, [])
}

const data =
  [ 1, 2, 3 ]

const print = (...xs) =>
  console .log (...xs .map (x => JSON .stringify (x)))

print
  ( Array .from (ncomb (0, data))
    // [[]]
    
  , Array .from (ncomb (1, data))
    // [[1],[2],[3]]
    
  , Array .from (ncomb (2, data))
    // [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[3,2],[3,3]]
    
  , Array .from (ncomb (3, data))
    // [[1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],[2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],[3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]]
  )

Выше комбинаций увеличивать крайний правый элемент, но этот порядок можно изменить.Если вы измените операцию append на prepend, вы сгенерируете комбинации, в которых вместо этого увеличивается левый элемент -

const prepend = (xs, x) =>
  [ x ] .concat (xs)

print
  ( Array .from (ncomb (3, data))
    // [[1,1,1],[2,1,1],[3,1,1],[1,2,1],[2,2,1],[3,2,1],[1,3,1],[2,3,1],[3,3,1],[1,1,2],[2,1,2],[3,1,2],[1,2,2],[2,2,2],[3,2,2],[1,3,2],[2,3,2],[3,3,2],[1,1,3],[2,1,3],[3,1,3],[1,2,3],[2,2,3],[3,2,3],[1,3,3],[2,3,3],[3,3,3]]
  )

Чтобы продемонстрировать поведение генератора при коротком замыкании, рассмотрим функцию solve, котораяпринимает любое количество чисел и возвращает первую пифагорейскую тройку .После того, как первый прямоугольный треугольник найден, дополнительные комбинации не будут сгенерированы -

const isRightTriangle = (a, b, c) =>
  // pythagorean triple
  (a ** 2) + (b ** 2) === (c ** 2)

const solve = (...numbers) =>
{ for (const [ a, b, c ] of ncomb (3, numbers))
    if (isRightTriangle (a, b, c))
      return `solution: ${a}, ${b}, ${c}`
  return `no solution`
}

console .log (solve (1, 2, 3, 4, 5, 6, 7, 9, 10))
// solution: 3, 4, 5

console .log (solve (8, 11, 6, 9, 5, 10, 12, 7))
// solution: 8, 6, 10

console .log (solve (19, 6, 8, 7, 21, 4, 3, 15))
// no solution

Разверните фрагмент ниже, чтобы проверить результаты в своем собственном браузере -

const append = (xs, x) =>
  xs .concat ([ x ])

const ncomb = function* (n, xs = [])
{ const gen = function* (n, acc)
  { if (n === 0)
      yield acc
    else
      for (const x of xs)
        yield* gen (n - 1, append (acc, x))
  }
  yield* gen (n, [])
}

const isTriangle = (a, b, c) =>
  // pythagorean theorem
  (a ** 2) + (b ** 2) === (c ** 2)

const solve = (...numbers) =>
{ for (const [ a, b, c ] of ncomb (3, numbers))
    if (isTriangle (a, b, c))
      return `solution: ${a}, ${b}, ${c}`
  return `no solution`
}

console .log (solve (1, 2, 3, 4, 5, 6, 7, 9, 10))
// solution: 3, 4, 5

console .log (solve (8, 11, 6, 9, 5, 10, 12, 7))
// solution: 8, 6, 10

console .log (solve (19, 6, 8, 7, 21, 4, 3, 15))
// no solution

Answer 2

Я думаю, это было бы более или менее каноническим способом для комбинаций размером 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));