March 10th, 2013, 12:13 AM

Find all the permutations of rearranging a string
I want a C Program to get all the combinations of rearranging a array. Like if i enter "abcd".
I want the program to calculate:
abdc
acdb
acbd
adbc
adcb
bacd
badc
bcda
bcad
bdac
bdca
...............(23 outputs in total)
so that i can check whether any of them satisfies my condition. (through a loop)
Reply ASAP
Thanks in advance
Daksh Shah
March 10th, 2013, 12:21 AM

what have you done so far?
March 10th, 2013, 01:25 AM

Originally Posted by bullet
what have you done so far?
What do u mean by this????
I had thought of replacing the 1st character by 2nd n then 3rd...
then 2nd with 3rd and so onn..
but it would leave many cases and i want to apply it on a array of length around 100 chars soooo..
pls help
March 10th, 2013, 10:45 AM

Recursion is a simple way to do this.
The permutations of a set of size n is found by removing one element from the set, taking the permutations of the other n1 elements, and then for each of those permutations, insert the element you removed into each possible spot in the permutation.
March 10th, 2013, 10:59 AM

Can you please tell me how can this be done; by writing a code in 'c'
March 10th, 2013, 03:08 PM

Up the Irons
What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
"Death Before Dishonour, my Friends!!"  Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
Down with Sharon Osbourne
"I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website."  Nilpo
March 10th, 2013, 03:51 PM

It might be more efficient to find a string that meets your condition and see if it is a permutation of the input.
[code]
Code tags[/code] are essential for python code and Makefiles!
March 10th, 2013, 11:18 PM

Originally Posted by Daksh
What do u mean by this????
I had thought of replacing the 1st character by 2nd n then 3rd...
then 2nd with 3rd and so onn..
but it would leave many cases and i want to apply it on a array of length around 100 chars soooo..
pls help
You might not realize this, but there are 9332621544394415268169923885626670049071596826438162146859296389521759999322991560894146397615651828 6253697920827223758251185210916864000000000000000000000000 permutations of a string of length 100. Good luck waiting many, many, many times longer than the age of the universe while your computer generates those permutations! If you are planning to do this computation for a real problem, then you're going about it the wrong way. Maybe you should give some information about the problem you're really trying to solve. (Just FYI  generating all the permutations of a string is almost never a good way to approach a situation.)
Originally Posted by bullet
Recursion is a simple way to do this.
The permutations of a set of size n is found by removing one element from the set, taking the permutations of the other n1 elements, and then for each of those permutations, insert the element you removed into each possible spot in the permutation.
Recursion is definitely the most natural way to do this. Here's a slightly different approach that is easier for me to think about (in C, anyway; yours is perfectly natural in a language like Python that has generators): recursively find all the permutations that have 'a' as the first letter, then the ones that have 'b' as the first letter, and so on up to however many letters you have. If you choose to permute the string in place, assume that each recursive call returns its part of the string to its original unpermuted state, and at the end, you should in turn return the string to its unpermuted state.
March 10th, 2013, 11:30 PM
