#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    22
    Rep Power
    0

    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
  2. #2
  3. Java Junkie
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jan 2004
    Location
    Mobile, Alabama
    Posts
    4,021
    Rep Power
    1285
    what have you done so far?
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    22
    Rep Power
    0
    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
  6. #4
  7. Java Junkie
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jan 2004
    Location
    Mobile, Alabama
    Posts
    4,021
    Rep Power
    1285
    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 n-1 elements, and then for each of those permutations, insert the element you removed into each possible spot in the permutation.
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    22
    Rep Power
    0
    Can you please tell me how can this be done; by writing a code in 'c'
  10. #6
  11. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,616
    Rep Power
    4247
    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
  12. #7
  13. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,841
    Rep Power
    480
    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!
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Intermediate (1500 - 1999 posts)

    Join Date
    Feb 2004
    Location
    San Francisco Bay
    Posts
    1,939
    Rep Power
    1313
    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 n-1 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.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    22
    Rep Power
    0
    Thanks buddy

IMN logo majestic logo threadwatch logo seochat tools logo