问题分类:您可以将此问题视为探索性问题,即给定一组输入字符,探索不同的排列方式。
解决方案:回溯算法擅长解决探索性问题,尽管它具有高时间复杂度。为了演示解决方案,请想象一下如何手动解决这个小型输入字符集的问题:
[a, b, c]。
以下是步骤:
- 取最左边的字符。这是索引为0的字符,并将其与目标右字符在索引0交换,即与自身交换。这是因为[a, b, c]本身就是一个有效的排列,因此我们要保留它。交换字符通常需要两个指针,分别指向每个字符。所以我们假设有一个left和right指针。
- 使用相同的最左边的字符(索引为0),将其与目标右字符在索引0 + 1 = 1交换,即将目标右指针向前移动1步。这将给出输出:[b, a, c]
- 使用相同的最左边的字符(索引为0),将其与下一个目标右字符(即索引0 + 1 + 1 = 2)交换。这将给出输出:[c, b, a]
好的,现在我们需要停止,因为没有更多的目标右字符可以与最左边的字符交换了。因此,我们的right指针需要小于input中的最大索引。使用for循环逐步移动right指针,从left索引开始,以输入长度-1结尾。
现在,您需要执行与上述相同的步骤,但移动左指针,使其指向下一个最左边的字符。但保留步骤2和3中的输入。另一种想象这种情况的方式是说:“嘿,我已经完成了最左边的字符。现在我不想再使用它,但我很想继续使用到目前为止的第二个最左边的字符。”
何时停止?当左指针达到输入字符串长度-1时,因为此索引之后没有更多字符。在递归算法(如回溯)中,需要停止的情况称为基本情况。在我们的示例中,基本情况是:left === input.length - 1。
这是一个图形化可视化:
left index| Input String:
-------------------------------------------------------------------------------
left = 0 | in=[a, b, c]
(swap in[0] with in[0]) (swap in[0] with in[1]) (swap in[0] with in[2])
left = 1 | in=[a, b, c] in=[b, a, c] in=[c, b, a]
(swap in[1] with in[1]) (swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2]) (swap in[1] with in[1])(swap in[1] with in[2])
left = 2 | [a, b, c] [a, c, b] [b, a, c] [b, c, a] [c, b, a] [c, a, b]
概述:
- 为了将左指针向右移动,我们将使用递归增量。
- 为了将右指针向右移动,我们将使用一个for循环,但是我们需要始终从左指针开始,否则我们将探索我们已经探索过的东西。
回溯算法:
回溯算法的伪代码形式如下:
fun(input)
if(base_case_check(input)) {
} else {
fun(reduce(input))
}
我们的解决方案:
function permutate(string) {
if(!string || string.length === 0)
return new Set(['']);
let left = 0;
let result = new Set();
permutationHelper(string, result, left);
return result;
}
function permutationHelper(string, result, left) {
if(left === string.length-1) {
result.add(string);
} else {
for(let right=left; right < string.length; right++) {
string = swap(string, left, right);
permutationHelper(string, result, left+1);
string = swap(string, left, right);
}
}
}
function swap(string, left, right) {
let tmpString = string.split('');
let tmp = tmpString[left];
tmpString[left] = tmpString[right];
tmpString[right] = tmp;
return tmpString.join('');
}
let input = 'abc';
let result = permutate(input);
let expected = new Set(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']);
if(setsEquality(result, expected)) {
console.log('Congrats, you generated all permuations');
} else {
console.log('Sorry, not all permuations are generated');
}
function setsEquality(actualResult, expectedResult) {
if (actualResult.size !== expectedResult.size) {
return false;
}
for (let permutation of actualResult) {
if (!expectedResult.has(permutation)) return false;
}
return true;
}
function assert(condition, desc) {
if (condition) {
console.log(`${desc} ... PASS`);
} else {
console.log(`${desc} ... FAIL`);
}
}
总结和时间复杂度:
- 我们通过交换现有输入字符串中的字符来进行选择
- 当我们将左索引增加1时,我们会探索剩下要探索的内容。事实上,这意味着我们将所有后续递归的输入集合减少1。因此,我们需要完成的工作是:Nx(N-1)x(N-2)x(N-3)x...x1 = N!。然而,由于我们需要使用for循环来在输入中进行探索,所以总时间复杂度为:0(N*N!)
- 我们通过在修改后的输入字符串中交换字符来恢复选择。
function foo(x) { return [ x.substring(0, 1) ].push(foo(x.substring(1))) }
- Tibrogargan