递归打印字符串的所有排列（Javascript）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/39927452/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Recursively print all permutations of a string (Javascript)
提问by singmotor
I've seen versions of this question for other languages, but not for JS.
我已经看到其他语言的这个问题的版本，但没有看到 JS。
Is it possible to do this recursively in one function?
是否可以在一个函数中递归地执行此操作？
I understand that I need to take the first element in the string, and then append it to each solution to the recursion on the remainder of the string. So logically, I understand how the recursion needs to go. I just don't understand how to append the first char onto each of the recursive solutions
我知道我需要获取字符串中的第一个元素，然后将其附加到每个解决方案中，以对字符串的其余部分进行递归。所以从逻辑上讲，我理解递归需要如何进行。我只是不明白如何将第一个字符附加到每个递归解决方案上
var myString = "xyz";
function printPermut(inputString){
var outputString;
if(inputString.length === 0){
return inputString;
}
if(inputString.length === 1){
return inputString;
}
else{
for(int i = 0; i<inputString.length(); i++){
//something here like:
//outputString = outputString.concat(printPermut(inputString.slice(1))??
//maybe store each unique permutation to an array or something?
}
}
}
回答by Syntac
Let's write a function that returns all permutations of a string as an array. As you don't want any global variables, returning the permutations is crucial.
让我们编写一个函数，将字符串的所有排列作为数组返回。由于您不想要任何全局变量，因此返回排列至关重要。
function permut(string) {
if (string.length < 2) return string; // This is our break condition
var permutations = []; // This array will hold our permutations
for (var i = 0; i < string.length; i++) {
var char = string[i];
// Cause we don't want any duplicates:
if (string.indexOf(char) != i) // if char was used already
continue; // skip it this time
var remainingString = string.slice(0, i) + string.slice(i + 1, string.length); //Note: you can concat Strings via '+' in JS
for (var subPermutation of permut(remainingString))
permutations.push(char + subPermutation)
}
return permutations;
}
To print them, just iterate over the array afterwards:
要打印它们，只需在之后遍历数组：
var myString = "xyz";
permutations = permut(myString);
for (permutation of permutations)
print(permutation) //Use the output method of your choice
Hope I could help you with your question.
希望我能帮助你解决你的问题。
回答by Syntac
The problem of permutations has been studied to death. Heap's algorithmis one well-known solution. Here is a version in JS, using a generator:
排列问题已经被研究到死。堆算法是一种众所周知的解决方案。这是使用生成器的 JS 版本：
function *permute(a, n = a.length) {
if (n <= 1) yield a.slice();
else for (let i = 0; i < n; i++) {
yield *permute(a, n - 1);
const j = n % 2 ? 0 : i;
[a[n-1], a[j]] = [a[j], a[n-1]];
}
}
console.log(Array.from(permute("abcabad".split('')))
.map(perm => perm.join(''))
.filter((el, idx, self) => (self.indexOf(el) === idx)));permuteis designed to take and generate arrays, not strings, so we split the string into characters before calling it, and paste the characters back into strings before printing out the results.
permute旨在获取和生成数组，而不是字符串，因此我们在调用之前将字符串拆分为字符，并在打印结果之前将字符粘贴回字符串。
回答by Nikhil Mahirrao
Use Recursive Functionto iterate through the string
使用递归函数遍历字符串
function getPermutations(string) {
var results = [];
if (string.length === 1)
{
results.push(string);
return results;
}
for (var i = 0; i < string.length; i++)
{
var firstChar = string[i];
var otherChar = string.substring(0, i) + string.substring(i + 1);
var otherPermutations = getPermutations(otherChar);
for (var j = 0; j < otherPermutations.length; j++) {
results.push(firstChar + otherPermutations[j]);
}
}
return results;
}
var permutation = getPermutations('YES').filter((el, idx, self) => (self.indexOf(el) === idx));
console.log("Total permutation: "+permutation.length);
console.log(permutation);回答by Ivan Hristov
Problem classification:You can look at this problem as an exploration problem, i.e., given a set of input characters explore the different ways you can arrange them.
问题分类：您可以将此问题视为一个探索问题，即，给定一组输入字符，探索您可以如何安排它们的不同方式。
Solution:Backtrackingalgorithm excels in solving exploratory problems, although it comes with high time complexity. To demonstrate a solution, imagine how you would solve this problem by hand for a small set of input characters: [a, b, c].
解决方案：回溯算法擅长解决探索性问题，尽管它的时间复杂度很高。为了演示一个解决方案，想象一下您将如何针对一小组输入字符手动解决这个问题：[a, b, c]。
Here are the steps:
以下是步骤：
- Take the left most character. This is the character at index 0 and swap it with target right character at index 0, i.e. with itself. This is because [a, b, c]is a valid permutation on its own therefore we want to keep it. Swapping characters normally requires two pointers which point to each of the characters. So let's say we will have a leftand rightpointer.
- With the same left most character (at index 0) do the swapping with target right character at index 0 + 1 = 1, i.e. move the target right pointer with 1 step further. This will give you the output: [b, a, c]
- With the same left most character (at index 0) do the swapping with the next next target right character (i.e. index 0 + 1 + 1 = 2). This will give you the output: [c, b, a]
Ok, now we need to stop as there are no more target right characters to be swapped with the left most character. So our rightpointer needs to stay less than the max index in the input. Moving the rightpointer with a step at a time we can do with a forloop which starts from the leftindex and ends with the input length - 1.
Now you need to do exact same steps from above but move the left pointer so that it points to the next left most character. However, keeping the input from step 2 and 3. Another way to imagine this situation is to say: 'Hey, I am done with the left most character. Now I do not want to work with it anymore but I would love to continue with the second left most from the results I have so far.'
When do we stop? When the left pointer has reached the length of the input string - 1, 'cause there is no more characters after this index. In recursive algorithms (such as the backtracking), the case where you need to stop is called base case. In our example the base case is: left === input.length - 1.
- 取最左边的字符。这是索引 0 处的字符并将其与索引 0 处的目标右侧字符交换，即与自身交换。这是因为[a, b, c]本身就是一个有效的排列，因此我们想保留它。交换字符通常需要两个指向每个字符的指针。所以我们可以说，我们将有一个左和右指针。
- 使用同一个最左边的字符（在索引 0 处）与索引 0 + 1 = 1 处的目标右字符进行交换，即，将目标右指针进一步移动 1 步。这将为您提供输出：[b, a, c]
- 使用相同的最左边字符（在索引 0 处）与下一个目标右边字符（即索引 0 + 1 + 1 = 2）进行交换。这会给你输出：[c, b, a]
好的，现在我们需要停止，因为没有更多的目标右侧字符要与最左侧的字符交换。所以我们的右指针需要保持小于输入中的最大索引。一次一步移动右指针，我们可以使用从左索引开始并以输入长度 - 1 结束的for循环。
现在您需要从上面执行完全相同的步骤，但移动左指针，使其指向最左边的下一个字符。但是，保留第 2 步和第 3 步的输入。想象这种情况的另一种方法是说：'嘿，我已经完成了最左边的字符。现在我不想再使用它了，但我很想继续使用到目前为止我所拥有的结果中的第二个。
我们什么时候停止？当左指针已达到输入字符串的长度 - 1 时，' 因为此索引之后没有更多字符。在递归算法（例如回溯）中，需要停止的情况称为base case。在我们的示例中，基本情况是：left === input.length - 1。
Here is a graphical visualisation:
这是一个图形可视化：
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]
Summary:
概括：
- To move the leftpointer to the right we will use recursive increment
- To move the rightpointer to the right we will use a forloop, however we need to start always from the left pointer or else we will explore things we have already explored.
- 要将左指针向右移动，我们将使用递归增量
- 为了将右指针向右移动，我们将使用for循环，但是我们需要始终从左指针开始，否则我们将探索我们已经探索过的东西。
Backtracking:A pseudo-code for backtracking algorithm takes the form of:
回溯：回溯算法的伪代码采用以下形式：
fun(input)
if(base_case_check(input)) {
//do final step
} else {
//choose
fun(reduce(input)) //explore
//un-choose
}
Our solution:
我们的解决方案：
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) {
//base case
result.add(string);
} else {
//recursive case
for(let right=left; right < string.length; right++) {
string = swap(string, left, right); //choose
permutationHelper(string, result, left+1); // explore
string = swap(string, left, right); //unchoose
}
}
}
function swap(string, left, right) {
let tmpString = string.split('');
let tmp = tmpString[left];
tmpString[left] = tmpString[right];
tmpString[right] = tmp;
return tmpString.join('');
}
/* End of solution */
/* Tests */
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`);
}
}Summary & Time Complexity:
总结和时间复杂度：
- We make our choice by swapping characters in the existing input string
- We explore what is left to be explored once we increment our left index with 1. This in fact means that we are reducing our input set for all subsequent recursions with 1. Therefore the work we need to do is: Nx(N-1)x(N-2)x(N-3)x...x1 = N!. However, as we needed a forloop to explore among the input we have, the total time complexity would be: 0(N*N!)
- We revert our choice by swapping characters back in the modified input string
- 我们通过交换现有输入字符串中的字符来做出选择
- 一旦我们用 1 增加我们的左索引，我们探索还有什么需要探索。这实际上意味着我们正在用 1 减少我们所有后续递归的输入集。因此我们需要做的工作是：Nx(N-1) x(N-2)x(N-3)x...x1 = N！. 但是，由于我们需要一个for循环来探索我们拥有的输入，因此总时间复杂度为：0(N*N!)
- 我们通过在修改后的输入字符串中交换字符来恢复我们的选择
回答by ankit gupta
permutation=(str,prefix)=>{
if(str.length==0){
console.log(prefix);
}
else{
for(let i=0;i<str.length;i++){
let rem = str.substring(0,i)+str.substring(i+1);
permutation(rem,prefix+str[i]);
}
}
}
let str="ABC";
permutation(str,"");
回答by Zibri
Semi-Off topic:
半离题：
random permutation of a given string is as simple as rndperm:
给定字符串的随机排列就像rndperm一样简单：
i = document.getElementById("word");
b = document.getElementById("butt");
rndperm = (z) => {
return z.split("").sort(() => ((Math.random() * 3) >> 0) - 1).join("")
}
function scramble() {
i.value = rndperm(i.value);
}
var z;
function sci() {
if (z != undefined) {
clearInterval(z);
b.innerText = "Scramble";
z=undefined;
} else {
z = setInterval(scramble, 100);
b.innerText = "Running...";
}
}<center><input id="word" value="HelloWorld"></input><button id="butt" onclick=sci()>Scramble</button></center>