为什么我的代码两次推送每个排列？

我很困惑，为什么我的代码是两次推送每个排列。请有人帮忙。我使用的堆算法：为什么我的代码两次推送每个排列？

var regex = /(.)\1+/g; 

function permAlone(str) { 
    var newArray = str.split(''); 
    var n = newArray.length; 
    var permutations = []; 
    var tmp; 

    function swap(index1, index2) { 
    tmp = newArray[index1]; 
    newArray[index1] = newArray[index2]; 
    newArray[index2] = tmp; 
    } 

    function generate(n, newArray) { 
    if (n === 1) { 
     permutations.push(newArray.join('')); 
    } else { 
     for(var i = 0; i<n-1; i++) { 
     generate(n-1, newArray); 
     swap(n % 2 ? 0 : i, n-1); 
     permutations.push(newArray.join('')); 
     } 

     generate(n-1, newArray); 
    }  
    } 

    generate(n, newArray); 
    return permutations; 
}  

permAlone('aab');

返回的数组是：

["aab", "aab", "aab", "baa", "baa", "aba", "aba", "aba", "baa", "baa"]

因此，大家可以看到，排列是出现更多的时间比预期的每一件事情。任何帮助将是巨大的

来源

2017-01-20 Nick

除了重复，所述第二呼叫，以产生'（N-1，newArray）;'是不必要的。它只是做与循环的最后一次迭代相同的事情。 – samgak

只有一个问题：由于字符串是'aab'，你是否期望两个'aab'和两个'aba' ...（因为有两个'a'）或者只有一个？ –

...为什么正则表达式..？ – Redu

代码有点复杂，很难给出递归跟踪，但如果你想要的是只有唯一值的数组，可以将下面的代码只适用于结果数组：

function stripDuplicates(input) { 
    if (!input || typeof(input) !== 'object' || !('length' in input)) { 
     throw new Error('input argument is not array.'); 
    } 

    var newArray = []; 
    for (var i = 0; i < input.length; i++) { 
     if (newArray.indexOf(input[i]) === -1) { 
      newArray.push(input[i]); 
     } 
    } 

    return newArray; 
}

这也可以实现功能上，而不是势在必行，但是这确实更偏爱比的优化问题。

Bálint还指出，你可以只将结果转换为Set，然后将Set转换回Array，它会自动去除任何重复项。但请注意，Set是Javascript中的一种相对较新的功能，并且不会在ES6之前的环境中运行。

来源

2017-01-20 19:09:19 furkle

或者只是将它们放在一个集合中并将其转换为数组。似乎没有人喜欢套。 –

@Bálint还是那样！随意添加，作为你自己的答案 - 这是一个好主意。这样做的好处是，如果以后有任何其他要求，您也可以在循环中执行其他任何操作。我选择不这样做，因为我试图尽可能向后兼容我的SO答案，Set对象只存在于ES6 +中。 – furkle

不，你应该加上它。我现在没有时间。 –

你要的电话：里面的for循环

permutations.push(newArray.join(''));

。那不应该在那里。然后，当然如果你正在排列具有重复字符的字符串，那么，期望看到愚蠢。例如，如果您排列字符串“aa”，则会从该算法“aa”和“aa”中获得两个条目。堆的算法不会尝试删除模糊，它将每个元素视为字符串中唯一的元素。显然，使用删除模式很重要，如果这是你关心的事情。

来源

2017-01-20 19:42:22 aquinas

为什么我的代码两次推送每个排列？

回答

相关问题