Генерация перестановок из шаблона - PullRequest
Новая
       31

Генерация перестановок из шаблона

1 голос
/ 11 марта 2019

Моя цель - создать общую функцию, которая создает двумерный вектор, заполненный перестановками (вектор), на основе заданного шаблона и параметров следующим образом:

  • некоторые позиции вектора должны быть зафиксированы на основе шаблона как вектора параметров функции. Например, если задан шаблон {0, 1, 0, -1, 3, -1}, это означает, что перестановки будут варьироваться только числами в местах -1.
  • n. n-1 - это диапазон целых чисел, которые может включать в себя перестановка. Например. если n = 4, только 0, 1, 2, 3 может появиться в векторе
  • length, что является длиной вектора

Обратите внимание, что если число из шаблона уже присутствует в нем, оно не будет сгенерировано в перестановках.

Итак, приведем пример: 

n = 6, length = 5, template = {2, 1, 0, -1, 0, -1}
the permutations are:
{2, 1, 0, 3, 0, 3}
{2, 1, 0, 3, 0, 4}
{2, 1, 0, 3, 0, 5}
{2, 1, 0, 4, 0, 3}
{2, 1, 0, 4, 0, 4}
{2, 1, 0, 4, 0, 5}
{2, 1, 0, 5, 0, 3}
{2, 1, 0, 5, 0, 4}
{2, 1, 0, 5, 0, 5}

Как видите, числа генерируются только в индексах 3 и 5 (места, где это было -1), а также в местах, которые не включены 0, 1 or 2, так как они уже появляются в шаблоне.

Мне нужно сгенерировать эти перестановки без использования библиотеки <algorithm>.

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

Спасибо

1 Ответ

1 голос
/ 11 марта 2019

Поскольку вы не предлагали видимых попыток, я полагаю, вам может быть полезно изучить какой-то рабочий код.Это в JavaScript (я надеюсь, что он производит ожидаемый результат).Я надеюсь, что это поможет вам дать некоторые идеи, которые вы могли бы перевести на C ++. 

function f(template){
  console.log(JSON.stringify(template));

  var used = template.reduce((acc, x) => { if (x != -1) acc.add(x); return acc; }, new Set());

  console.log(`used: ${Array.from(used)}`);

  var needed = new Set(template.reduce((acc, x, i) => { if (!used.has(i)) acc.push(i); return acc; }, []));

  console.log(`needed: ${Array.from(needed)}`);

  var indexes = template.reduce((acc, x, i) => { if (x == -1) return acc.concat(i); else return acc; }, []);

  console.log(`indexes: ${indexes}`);

  function g(needed, indexes, template, i=0){
    if (i == indexes.length)
      return [template];

    var result = [];

    // Each member of 'needed' must appear in
    // each position, indexes[i]
    for (x of needed){
      let _template = template.slice();
      _template[ indexes[i] ] = x;

      result = result.concat(
        g(needed, indexes, _template, i + 1));
    }

    return result;
  }

  return g(needed, indexes, template);
}

var template = [2, 1, 0, -1, 0, -1];

var result = f(template);

var str = '\n';

for (let r of result)
  str += JSON.stringify(r) + '\n';

console.log(str);
...