String Permutation Algorithm
Why Stack Overflow recommends it
Stack Overflow users link it when they are trying to understand how backtracking and recursion produce string permutations, including with duplicate characters.
Recommended by 2 people across 2 different months, 2019 to 2021.
What it is
Tushar Roy walks through an algorithm that generates all permutations of a string in lexicographic order, including strings with repeated characters. He explains the recursive backtracking approach with a character-count array, with Java and Python code on GitHub.
What people said
Recommends Garrett · 2020-03 · Stack Overflow · on “Get Word Permutations”
I have just finished watching [this video] . I will have to watch it at least one more time. There is code on his Github and he seems to explain it thoroughly, though I haven't gotten it yet. I'm not smart like I used to be...
Recommends shikha8757 · 2021-08 · Stack Overflow · on “Permutation of a string is failing for string having duplicate character”
I am trying to understand how backtracking works. I am working on permutation of a string. class Solution { public: void permute(string s,int count[], string res, int level, vector<string> &perS) { if( level == s.size()) { //cout<<res<<endl; perS.push_back(res); return; } int i; for(i=0; i<s.size(); i++) { if(count[i]==0) { continue; } res += s[i]; count[i]--; permute(s, count, res, level+1, perS); count[i]++; //this line is problem I think?? how to handle if s1 contains duplicates?? res.erase(res.end()-1); } } bool checkInclusion(string s1, string s2) { map<char, int> mp; for(int i=0; i<s1.size(); i++) { mp[s1[i]]++; } int *count = new int[mp.size()]; set<char> us; //to generate the count a
Cites colleen · 2019-09 · Stack Overflow · on “Why are some variables or lists preserved when exiting recursive calls and others not?”
I'm trying to understand what happens to your variables in Python when you exit a list. I thought all variables that are passed to a recursive function are pushed onto a stack. And when you exit a stack, those variables are popped off. However, I'm seeing this is not the case. I created a simple recursive string function to test this. When I run this code: def recursiveArr(n, listB): if(n==0): return True; else: listB.append(n); listC = listB; recursiveArr(n-1, listB[:]); print(n) print(listB) I get the following output: 1 [4, 3, 2, 1] 2 [4, 3, 2] 3 [4, 3] 4 [4] [4] This suggests that both the list and the variable n were preserved on the stack. Then, I modified the call to recursiveArr(n-1,