shuffle strings

Hmm, another algorithm to be implemented. It is more sort of a simple math fundamental that we used to study in schools. "How many ways you can arrange a number with n digits? – The answer is n!". The algorithm is to write all the possible combinations.

I have a basic thing in my mind, how would it should work. Here it is:

1. If you have a string with n characters, go to the last character (i.e. nth character – not that I am not starting with 0) first, and keep it as it is.
2. Next step would be to go to (n-1) char. And then starting with this length, keep shifting it towards right. Repeating this procedure would result in two strings.

For example, if the givne string is "1234", at the 1st step you will get "4". In the second step, you will get "34", "43" (as you are shifting 3 towards right).

3. In the next step, go to the (n-2) character and repeat the same procedure as of step 2, but in both the output strings generated in step 2.

I.e., shift 2 to right on string "34" and "43". This will result in :

"234", "324", "342"
"243", "423", "432"

Hence you will get 6 strings.

4. In this step, go to (n-4) char, and repeat the same procedure as of step (2 or 3) on all the strings generated by previous step. This would result in total of 24 strings.

Problem solved for the string length 4. Total number of unique strings would be 4! = 24.

The main problem for me at the moment is implementation. How do I store the intermediate strings? Head is banging over the weekend – I think this is going to take me some time.

Edit:
=====
And idea came last night to store the string into a tree form, binary tree kind of data structure, and follow the following tree traversal techniques recursively.

1. in order
2. pre order
3. post order
4. level order(starting from bottom left)
5. level order(starting from bottom right)

going ahead with this idea may help in reducing the memory footprint, and just while i am writing this approach, i felt little sceptical about this approach as all the subtrees have to be traversed in these orders, and where the intermediate string would be stored?? confused!!

The above method of using Tree is bad, not at all practical :) Just try out string of length 5 and the algo strength will be revealed.

Enough is enough!! Here is the solution :(
http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture25.html

Advertisements

2 thoughts on “shuffle strings

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s