Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 12 of 12

Thread: permutations of a string using iteration

  1. #1
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default permutations of a string using iteration

    im trying to find permutation of a given string but i want to use iteration. The recursive solution i found online and i do understand it but converting it to an iterative solution is really not working out. Below i have attached my code. i would really appreciate the help:
    public static void combString(String s) {
        char[] a = new char[s.length()];
        //String temp = "";
        for(int i = 0; i < s.length(); i++) {
            a[i] = s.charAt(i);
        }
        for(int i = 0; i < s.length(); i++) {
            String temp = "" + a[i];    
     
            for(int j = 0; j < s.length();j++) {
                //int k = j;
                if(i != j) {
                    System.out.println(j);
                    temp += s.substring(0,j) + s.substring(j+1,s.length());
                }               
            }
            System.out.println(temp);
        }
    }
    Last edited by helloworld922; August 11th, 2012 at 12:00 PM. Reason: please use [code] tags


  2. #2
    Member
    Join Date
    Jul 2012
    Posts
    90
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: permutations of a string using iteration

    Could you please your code in [key] here enter your code [/key] in order to be more clear to everybody?

    in order to work write code instead of key

  3. #3
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: permutations of a string using iteration

     
    public static void combString(String s) {
    char[] a = new char[s.length()];
    //String temp = "";
    for(int i = 0; i < s.length(); i++) {
    a[i] = s.charAt(i);
    }
    for(int i = 0; i < s.length(); i++) {
    String temp = "" + a[i]; 
     
    for(int j = 0; j < s.length();j++) {
    //int k = j;
    if(i != j) {
    System.out.println(j);
    temp += s.substring(0,j) + s.substring(j+1,s.length());
    } 
    }
    System.out.println(temp);
    }
    }

  4. #4
    Member
    Join Date
    Jul 2012
    Posts
    90
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: permutations of a string using iteration

    Actually can you provide a small example.For example the word "Sam" what permutations does it have?I remember that the number of them is 2³,but i am not sure i know what the goal is.Sorry for my noobness :/

  5. #5
    Junior Member
    Join Date
    Jul 2012
    Posts
    14
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Re: permutations of a string using iteration

    if u have a string "abc" then the output should be: abc, acb,bac,bca,cba,cab

  6. #6
    Member
    Join Date
    Jul 2012
    Posts
    90
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: permutations of a string using iteration

    So the formula was n! where n is the number of the letters of the word.So you have to output that many words.As for what should be changed,still thinking of it
    Last edited by Samaras; August 11th, 2012 at 09:22 AM.

  7. #7
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: permutations of a string using iteration

    Take a small sample like your abc char set. You have 3 characters. So you need to output 3 things:
    All possible with a first...
    All possible with b first...
    All possible with c first...

    Within a being first, you need to output all possible with b second, and all possible with c second.
    Within b being first, you need to output all possible with a second, and all possible with c second.
    Within c being first...........

    recursion comes to mind
    Edit.. ok I missed the part about iteration..
    Last edited by jps; August 11th, 2012 at 10:00 AM.

  8. #8
    Member
    Join Date
    Jul 2012
    Posts
    90
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: permutations of a string using iteration

    Ok,so i thought that if we let the letters of the words to be different among them,then we have to output n! permutations,where n is the number of the word's letters.So i also saw that given a string "abcd" with n=4 then it's permutations are the following
    abcd
    abdc
    acbd
    acdb
    adbc
    adcb
    bacd
    badc
    bcad
    bcda
    bdac
    bdca
    cabd
    cadb
    cbad
    cbda
    cdab
    cdba
    dabc
    dacb
    dbac
    dbca
    dcab
    dcba
    So i noticed that at 1st postition of the permutation every letter should appear (n-1)! times,at the 2nd position every letter(without the first included) should appear (n-2)! -in the set where the 1st's position letter remains the same-,at the 3rd position every letter(without the first two) should appear (n-3)! and at the 4rth position every letter(without the first three) should appear (n-4)!=(4-4)!=0!=1 times .So in general at m-th position every letter(without previous appearance of it) should appear (n-m)! times.
    .
    So this concept led me to a recursion code.But then i remember you wanted an iterative one.So i came around this code
    public static void combString(String s) {
            int numberOfPermutations = 0;
            for (int i = 0; i < s.length(); i++) {
                for (int j = 0; j < s.length(); j++) {
                    for (int k = 0; k < s.length(); k++) {
                        for (int z = 0; z < s.length(); z++) {
                            if (i != j && j != k && i != k && i != z && j != z && k != z) {
                                System.out.format("%c%c%c%c%n", s.charAt(i), s.charAt(j),
                                        s.charAt(k), s.charAt(z));
                                numberOfPermutations++;
                            }
                        }
                    }
                }
            }
            System.out.println(numberOfPermutations);
        }
    The problem is that depending the number of letters of the word ,this code has to use the same number of for-loops(so the number of the letters is going to be equal with the number of the variables(with the counter for permutations not included.).This code is for a word with four letters and lets letters to appear as many times they found in the word,iterates of letters are enabled in other words.

    The logic of the code is similar as you would do it in a piece of paper .The important thing is the if statement,which has this form because we do not want to permute a letter more than one time in every permutation.Try to remove this statement or some parts of it in order to get yourself convinced how this is need.

  9. #9
    Member
    Join Date
    Jul 2012
    Posts
    90
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: permutations of a string using iteration

    Quote Originally Posted by jps View Post
    recursion comes to mind
    And that's better than the iterative one i provided.If you consider the complexity of what i wrote ,you will be dissapointed.

  10. #10
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: permutations of a string using iteration

    I'm a little surprised no one's posted a google/wikipedia answer yet.

    Wikipedia - Generating Permutations in lexicographic order

    A more efficient recursive answer is presented here:

    Steinhaus-Johnson-Trotter algorithm

  11. #11
    Member
    Join Date
    Jul 2012
    Posts
    90
    Thanks
    1
    Thanked 2 Times in 2 Posts

    Default Re: permutations of a string using iteration

    However he stated that he wants no recursive method

  12. #12
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: permutations of a string using iteration

    The first link isn't recursive.

Similar Threads

  1. Replies: 1
    Last Post: April 19th, 2012, 02:46 AM
  2. hash map iteration
    By uniqe_mohini in forum Member Introductions
    Replies: 2
    Last Post: September 10th, 2011, 10:14 AM
  3. Finding all Permutations that add up to a number.
    By godsfearme in forum What's Wrong With My Code?
    Replies: 0
    Last Post: December 28th, 2010, 03:54 PM
  4. While (return value will terminate an iteration or loop?)
    By chronoz13 in forum Loops & Control Statements
    Replies: 3
    Last Post: April 27th, 2010, 09:05 AM
  5. Converting a recursion to iteration
    By javaplus in forum Algorithms & Recursion
    Replies: 7
    Last Post: March 3rd, 2010, 05:38 PM