Recursive Permutation Generator.
-
Hi, I've an assignment to make a program that should generate all the permutations of a string one by one. I know many algorithm of generating permutations using recursion, but question has asked to generate it one by one. So deliverable should contain a class called "PermutationIterator" which should have a method "hasNextPermutation" and "nextPermutation". They have given one hint, make a "tailIterator" object of type "PermutationIterator" inside a "PermutationIterator" class (like a node of LinkedList) and then do some funny things with it. I can't figure out where should I start....any help would be appreciated. Note: You can't generate all permutations at one time, then store it into an array and then call each of them one by one. Please don not suggest this way. Thank you Shivam Kalra
-
Hi, I've an assignment to make a program that should generate all the permutations of a string one by one. I know many algorithm of generating permutations using recursion, but question has asked to generate it one by one. So deliverable should contain a class called "PermutationIterator" which should have a method "hasNextPermutation" and "nextPermutation". They have given one hint, make a "tailIterator" object of type "PermutationIterator" inside a "PermutationIterator" class (like a node of LinkedList) and then do some funny things with it. I can't figure out where should I start....any help would be appreciated. Note: You can't generate all permutations at one time, then store it into an array and then call each of them one by one. Please don not suggest this way. Thank you Shivam Kalra
-
Nonetheless, generating permutations is something that suits recursion. And the
yieldkeyword would be useful too, see a little experiment here[^]. :)Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Hi, I've an assignment to make a program that should generate all the permutations of a string one by one. I know many algorithm of generating permutations using recursion, but question has asked to generate it one by one. So deliverable should contain a class called "PermutationIterator" which should have a method "hasNextPermutation" and "nextPermutation". They have given one hint, make a "tailIterator" object of type "PermutationIterator" inside a "PermutationIterator" class (like a node of LinkedList) and then do some funny things with it. I can't figure out where should I start....any help would be appreciated. Note: You can't generate all permutations at one time, then store it into an array and then call each of them one by one. Please don not suggest this way. Thank you Shivam Kalra
smells a lot like homework, and we don't do other people's homework... :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
smells a lot like homework, and we don't do other people's homework... :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
Thank you guys. I'm very excited right now because I've just finished the question, and I did it all by myself :-\ . It took 1/2 hour to think, 1 hour to write and 1 hour to correct it using hit and trial..But finally I succeeded. I'm attaching code below, it is in java but it will still run in C# because all syntax-es are same.
public class PermutationIterator
{
private String s;
private int index = 0;
private PermutationIterator tailIterator = null;public PermutationIterator(String s) { this.s = s; if(s.length() > 0) tailIterator = new PermutationIterator(s.substring(1)); } public boolean hasMorePermutations() { if(tailIterator == null) return false; if(s.length() == 1) return true; return index != s.length() - 1 || tailIterator.hasMorePermutations(); } public String nextPermutation() { if(s.length() == 1) { tailIterator = null; return s; } if(!tailIterator.hasMorePermutations()) tailIterator = new PermutationIterator(s.substring(0, ++index) + s.substring(index + 1)); return s.charAt(index) + tailIterator.nextPermutation(); }}
It is still less readable because I just used hit trial thing to correct array out of bound exceptions. I've started to love recursion..There are only few things in world that gives to pain and pleasure and one of them is recursion :-D, lol I just made that up.. Anyways, if you could improve my code and I would really appreciate it. Thanks Shivam K
-
Very nice article. I've bookmarked it. But in my case, if I do it non recursively then I'll get 0 marks because question clearly says USE RECURSION.
-
Thank you guys. I'm very excited right now because I've just finished the question, and I did it all by myself :-\ . It took 1/2 hour to think, 1 hour to write and 1 hour to correct it using hit and trial..But finally I succeeded. I'm attaching code below, it is in java but it will still run in C# because all syntax-es are same.
public class PermutationIterator
{
private String s;
private int index = 0;
private PermutationIterator tailIterator = null;public PermutationIterator(String s) { this.s = s; if(s.length() > 0) tailIterator = new PermutationIterator(s.substring(1)); } public boolean hasMorePermutations() { if(tailIterator == null) return false; if(s.length() == 1) return true; return index != s.length() - 1 || tailIterator.hasMorePermutations(); } public String nextPermutation() { if(s.length() == 1) { tailIterator = null; return s; } if(!tailIterator.hasMorePermutations()) tailIterator = new PermutationIterator(s.substring(0, ++index) + s.substring(index + 1)); return s.charAt(index) + tailIterator.nextPermutation(); }}
It is still less readable because I just used hit trial thing to correct array out of bound exceptions. I've started to love recursion..There are only few things in world that gives to pain and pleasure and one of them is recursion :-D, lol I just made that up.. Anyways, if you could improve my code and I would really appreciate it. Thanks Shivam K
I haven't checked it at all, however it looks sufficiently clean for me to trust you either have it right or could easily get it right. one comment: I would put some parentheses in this line, to make it even more obvious:
return index != s.length() - 1 || tailIterator.hasMorePermutations();
( )Now here is something to think about: assume there could be some duplicate characters (say street), now generate all permutations without any duplicates. I'm not claiming this is easy! I could offer a hint if you were to need one. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Thank you guys. I'm very excited right now because I've just finished the question, and I did it all by myself :-\ . It took 1/2 hour to think, 1 hour to write and 1 hour to correct it using hit and trial..But finally I succeeded. I'm attaching code below, it is in java but it will still run in C# because all syntax-es are same.
public class PermutationIterator
{
private String s;
private int index = 0;
private PermutationIterator tailIterator = null;public PermutationIterator(String s) { this.s = s; if(s.length() > 0) tailIterator = new PermutationIterator(s.substring(1)); } public boolean hasMorePermutations() { if(tailIterator == null) return false; if(s.length() == 1) return true; return index != s.length() - 1 || tailIterator.hasMorePermutations(); } public String nextPermutation() { if(s.length() == 1) { tailIterator = null; return s; } if(!tailIterator.hasMorePermutations()) tailIterator = new PermutationIterator(s.substring(0, ++index) + s.substring(index + 1)); return s.charAt(index) + tailIterator.nextPermutation(); }}
It is still less readable because I just used hit trial thing to correct array out of bound exceptions. I've started to love recursion..There are only few things in world that gives to pain and pleasure and one of them is recursion :-D, lol I just made that up.. Anyways, if you could improve my code and I would really appreciate it. Thanks Shivam K
Shivamkalra wrote:
tailIterator = new PermutationIterator(s.substring(0, ++index) + s.substring(index + 1));
While fine in C#, I don't like it a bit; in other languages (e.g.C, C++) this statement's result would be undefined, as the big + operator is commutative (*) and nothing forces the left operator to be evaluated before the right one, so the right operand can't be sure the auto-increment has already been executed. Again, C# guarantees it, but a casual reader could port it to another language and inadvertently introduce something that goes wrong on some compilers or under some circumstances! :) [ADDED] (*) well, not fully commutative like an arithmetic addition, however both string operands could be evaluated in any order before they get concatenated. [/ADDED]
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
modified on Friday, February 25, 2011 11:34 PM
-
I haven't checked it at all, however it looks sufficiently clean for me to trust you either have it right or could easily get it right. one comment: I would put some parentheses in this line, to make it even more obvious:
return index != s.length() - 1 || tailIterator.hasMorePermutations();
( )Now here is something to think about: assume there could be some duplicate characters (say street), now generate all permutations without any duplicates. I'm not claiming this is easy! I could offer a hint if you were to need one. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
It sounds interesting and more practical. Give me hint, I'll try to work on it. Shivam :)
-
It sounds interesting and more practical. Give me hint, I'll try to work on it. Shivam :)
think of a way to get all permutations in a simple ordered fashion, before you tackle the duplicates! It is very cheap, however it may well influence a lot of your code... :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
think of a way to get all permutations in a simple ordered fashion, before you tackle the duplicates! It is very cheap, however it may well influence a lot of your code... :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
It still very hard to do. Let say you have string "aaabbbccc", you will get 9! combination..then you need to find repetitions using linear search for each of the element..it's gonna take too much time..is there any way of handling repetition within code so that it can be ignored and final result we get is list of length (9!/3!3!3!).
-
It still very hard to do. Let say you have string "aaabbbccc", you will get 9! combination..then you need to find repetitions using linear search for each of the element..it's gonna take too much time..is there any way of handling repetition within code so that it can be ignored and final result we get is list of length (9!/3!3!3!).
Shivamkalra wrote:
It still very hard to do
not really. all you need to do is, at each nesting level, not choose a letter you have already chosen at that level (in a previous iteration). Now think. very hard, if you must. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
-
Shivamkalra wrote:
It still very hard to do
not really. all you need to do is, at each nesting level, not choose a letter you have already chosen at that level (in a previous iteration). Now think. very hard, if you must. :)
Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
oh ya, that's actually easy and makes sense too. I found a good way..if u arrange letter so that repeated letters are together then it will even easier to skips letters in each iteration ex. "aabbcc". This way you can skip alternating alphabet in each recursion..this is really interesting..I'm gonna give it a try right now. Thanks :) Shivam
-
Nonetheless, generating permutations is something that suits recursion. And the
yieldkeyword would be useful too, see a little experiment here[^]. :)Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum
Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.
Luc Pattyn wrote:
generating permutations is something that suits recursion
I respectfully disagree.