recursive-backtracking - 如何使用一些数字生成所有可能的数字

Question

我正在尝试生成所有可能的数字，这些数字以我不希望出现的数字向量超过它们在该向量中出现的次数。我的第一个想法是回溯，但如何.... 例如：3 7 5 => 3 5 7 35 37 53 57 73 75 357 375 537 573 735 753

Answer 1

基本上我会使用一个递归函数，从向量中选择每个数字，将该数字附加到结果中，并在递归调用中使用一个缩减的向量和数字作为“前缀”。结果我会在之后过滤具有唯一函数的重复项，例如数组中的唯一值

function selectOne(data,res,prependNumber){
  var current,reduced,i,len;
  for(i=0,len = data.length;i<len;i++){
    current = data[i];
    if(prependNumber!==false){
      current = prependNumber+ '' + current;
    }
    reduced = data.slice(0);
    reduced.splice(i,1);
    res.push(parseInt(current));
    selectOne(reduced,res,current);
  }
}
function onlyUnique(value, index, self) { 
    return self.indexOf(value) === index;
}

样品调用

var test = [3,5,7];
var res = [];
selectOne(test,res,false);
console.log(res.filter( onlyUnique ));

该算法的工作原理如下。

1. 获取输入数组并跨过它
2. 在此迭代中生成一个由元素减少的新数组
   • 我使用 .slice(0) 来克隆实际的输入数组，因为 slice 会生成一个从给定索引开始的新数组
   • 我使用 .splice 从位置 i 开始提取 1 个元素
3. 推数字结果
4. 使用缩减的数组再次调用该函数并在此迭代中使用当前数字，在我拖动下一个数字并将其推送到结果时添加它

例如，取输入数组 [3,5,7]。我迭代它。首先我抓取 3 并生成缩减数组 [5,7]。我将 3 推送到结果中，并使用此数组和 3 作为 prependNumber 递归调用我的函数。在循环中，我首先选择 5，但是因为我已经给出了 prependNumber，所以我没有将 5 推送到结果中，而是 35 并且有一个缩减的数组 [7]。等等。

将发生以下递归：

selectOne - level 1
res: [3]
selectOne - level 2
res: [3,35]
selectOne - level 3
res: [3,35,357]
selectOne - level 2
res: [3,35,357,37]
selectOne - level 3
res: [3,35,357,37,375]
selectOne - level 1
res: [3,35,357,37,375,5]
selectOne - level 2
res: [3,35,357,37,375,53]
selectOne - level 3
res: [3,35,357,37,375,53,537]
selectOne - level 2
res: [3,35,357,37,375,53,537,57]
selectOne - level 3
res: [3,35,357,37,375,53,537,57,573]
.
.
.