This week's book giveaway is in the Java in General forum.
We're giving away four copies of Think Java: How to Think Like a Computer Scientist and have Allen B. Downey & Chris Mayfield on-line!
See this thread for details.
Win a copy of Think Java: How to Think Like a Computer Scientist this week in the Java in General forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

String combinations & permutations

 
Nick Georgides
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi,

I'm trying to program an algorithm that returns all the combinations & permutations that can be made out of a given string.

e.g. for a "abc" it must return:


So far I've come up with:


But that only works in the case of "abc". Any advice on how I could make this more dynamic?

~Nick
 
Henry Wong
author
Marshal
Pie
Posts: 21114
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But that only works in the case of "abc". Any advice on how I could make this more dynamic?


Notice the pattern in your code? You have a for loop that has an for loop that looks pretty much like itself.

Doesn't the pattern look recursive?

Henry
 
Nick Georgides
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Henry, thanks for your reply.

I don't seem to grasp the concept of recursion Any help is much appreciated.

So, I moved the for-loop in another method and created the following:



which I guess is really stupid judging from its output.

~Nick
 
Henry Wong
author
Marshal
Pie
Posts: 21114
78
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I don't seem to grasp the concept of recursion. Any help is much appreciated.


There are two parts to any recursive algorithm. The first part is that the algorithm should do part of the work, which results in nearly the same problem, but closer to the solution. For example, you do the 1st character of the string permutation, but you depend on the algorithm to do the rest.

The second part is the end game. There comes a point where the problem is so easy that the recursive algorith is not needed anymore. For example, if there is only 1 letter left, then the result is simply a single output line.

You have done the first part. Now how do you determine when you are done?

Henry
 
Sai Narasimha Reddy
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[edit]Add code tags. CR[/edit]
[ September 10, 2008: Message edited by: Campbell Ritchie ]
 
Sai Narasimha Reddy
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
output was
cab
abc
cba
bac
bca
acb
count = 6
 
Brighton Kukasira
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi Nick,

I have only reached your question a couple of months later, but I hope my solution will still be helpful to you or other visitors to this page.


If you like this post please put some emoticons. I really enjoy it when viewers put these emoticons to express their emotions about my posts.

Regards,
Brighton Kukasira

 
Campbell Ritchie
Sheriff
Posts: 48910
58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to JavaRanch

I am afraid, not only is such a reply to a year-old post of little use, but also it does nobody any good to be given a straight answer like that. Please look at this FAQ too. Look what it says at the top of the beginners' contents page:
We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.


I have reluctantly felt obliged to move your solution to our "deleted" forum.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic