c++ - 从模板生成排列

Question

我的目标是创建一个通用函数，该函数根据给定的模板和参数创建一个填充有排列( vector )的二维 vector ，如下所示:

• vector 的一些位置必须固定，基于模板作为函数参数 vector 。例如，如果给定的模板是 {0, 1, 0, -1, 3, -1} ，这意味着排列只会因 -1 处的数字而异。 .
• n . n-1是排列可以包括的整数范围。例如。如果n = 4 , 只有 0, 1, 2, 3可以出现在 vector 中
• length , 这是 vector 的长度

请注意，如果模板中的数字已经出现在其中，则不会在排列中生成它。

举个例子:

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> 的情况下生成这些排列图书馆。

我认为创建递归函数是最佳选择，但我不知道如何继续。任何建议都会有所帮助。

谢谢

Answer 1

由于您没有提供明显的尝试，我认为研究一些工作代码可能对您有所帮助。这是在 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);