want a starting of a problem!!

[gourav1]

hi. i want to print all the possible combinations of a string entered. for example:- string input is "abc"... then output is "abc bac acb bca cba cab" and it must be true for every length of string.. i have tried many times and applied as much logics i can. but i m not getting. just tell me starting that how to proceed. i am not asking for code here, even i don't want. i will implement own my own. please help!!

[subith86]

assume the string is abcde

first group "abc" and "de" separately
"abc" is the fixed part and "de" is the variable part.
keeping "abc" fixed, there are two possibilities with which you can arrange "de"

Iteration 1
abc|de --- (1)
abc|ed --- (2)

In the next iteration, take out the right most character from the fixed part "abc" and it has to be put in the variable part. In this case the character is "c". Take the case (1). "c" can be placed in the middle of "de" and at the end of "de".

Iteration 2
ab|dce --- (3)
ab|dec --- (4)

Taking case (2)

ab|ecd --- (5)
ab|edc --- (6)

Similarly, continue this process till the end where you reach "a". When you reach "a", stop the grouping and release all the reserved memory. Shift all the characters left by 1 place. New string becomes "bcdea". Continue the above process till you reach "b". Now shift left again and the new string is "cdeab". Repeat till the string "eabcd".

One drawback of this solution is you have to store the strings in each iteration. In iter1 you have to store 2 string. In iter2, you have to store 4 strings, and so on.
Another drawback is, when you have duplicate characters like in string "abccde" this logic will output duplicate results too. I will think of a better solution and get back. This is something which struck my mind immediately after seeing your question.

[WaltP]

Try Googling for permutations so you can learn the basic algorithms.

[gourav1]

Try Googling for permutations so you can learn the basic algorithms.

means ? can u give me link so that i can learn from there ? i have searched too much. i didn't get any relevant link. please help!!

[Adak]

Here's how I approach this problem:

1) sort the letters you have, lowest to highest. I always want the permutations to start with the lowest possible one, and work up to the highest one, and be in order. And have no repetitions.

2) You will work from right to left, making swaps. Frequently, you will resort the string. A good little sorter to use is insertion sort, because it's SO fast with small data items that are almost sorted anyway. WAY faster than even Quicksort at this.

3) Take an example, "abcd":

4321 number the columns of letters, from right to left
====
abcd in your mind. No code needed for this.

abcd - string is sorted, low to high
abdc - swap #1 with #2 letter
acbd - When the #2 letter, has reached #1 position, no more swaps with it are
possible. Increment the position you're swapping with, to #3, and swap #3
with #1. And resort the string, low to high, ONLY from the position BEHIND
#3. You're not sorting the whole string, just the letters BEHIND where
you swapped to.

acdb - And start again with #1, swapping it with #2

Tilt your head to the left, or draw a line between the letter c in the first swap, and now the letter b. You'll see a straight line of c's or b's, as the letter "walks" toward the #1 position in the string.

Now 'b' has "walked" all the way to #1 position, so we need another "head" swap, at the next highest position than what we did last time. Our "lead" or "head" position was #3, and now we increment it to #4, and swap #1 with #4:

bcda - and now resort the string, (note: bcda is never printed at this time), ONLY
behind the "head" position to make:
bacd - and print bacd.

Now you'll see a pattern emerge:

bacd - is our string, and we swap #1 with #2 again, just like before.
badc and print it. We started with d in #1, and now it's in #2, so
bdac - swap it into #3, but again, don't print it
bdac - until the letters behind the d have been sorted - in this case, they already
were in the right order. Print it.

When you have swaps taking place in positions #3 or higher, you have to "start back from #1" to the position of your highest swap, every time you make a new higher swap. So we need to:
bdca - swap #1 and #2.

etc.

This is faster than it sounds, but the faster ways involve strings that are out of order (so it's incredibly difficult to just scan the results and see if it's OK or not), or they have duplicates, or they're much more complicated. None of these is OK with me.

Work at it from that point of view, and see if it starts making sense to you.

[subith86]

means ? can u give me link so that i can learn from there ? i have searched too much. i didn't get any relevant link. please help!!

Try these links
http://programminggeeks.com/recursive-permutation-in-c/
http://www.codeguru.com/cpp/cpp/algorithms/article.php/c5123/

They do it using recursive algorithm.