permutations of a string...logic error?

Question

i am trying to generate all the permutations of a given string.

the logic im using

suppose string =abcd

1) then i fix 'a'(and similarly each character.. first iteration - abcd, second-bacd, third-cabd.....)at first position in the first loop..

2) then generate strings by moving the second character ,i.e, 'b' at all the places.. like abcd,acbd,acdb...

3) then i replace the 3rd( 4th ,5th and so on ) character with the second charcter and repeat the second step again

4) i change abcd to bacd( n so for each character) and repeat steps 2,3...

now shouldn't this generate all the possible combinations..and also i use a tree set to remove duplicate entries... but somehow it is generating less permutations than there are actually..like for 4 characters, 20 permutations only...

here is the code for the same..

import java.util.*;

public class practice4 {


    public static void main(String[] args) {



        TreeSet t = new TreeSet();
        String arr[] = new String[100];
        int z = -1;
        StringBuffer s5 = new StringBuffer("abcde");


        for (int i = 0; i <= s5.length() - 1; i++) {

            char ch = s5.charAt(0);
            s5.setCharAt(0, s5.charAt(i));
            s5.setCharAt(i, ch);

            StringBuffer s3 = new StringBuffer(s5);

            for (int j = 1; j <= s3.length() - 1; j++) {

                StringBuffer s2 = new StringBuffer(s3);
                // System.out.println(s2);

                z++;
                arr[z] = s2.toString();

                for (int k = 1; k < s3.length() - 1; k++) {

                    char ch2 = s2.charAt(k);
                    s2.setCharAt(k, s2.charAt(k + 1));
                    s2.setCharAt(k + 1, ch2);
                    // System.out.println(s2);

                    z++;
                    arr[z] = s2.toString();

                }

                if (j >= s3.length() - 1)
                    break;
                char ch3 = s3.charAt(1);

                s3.setCharAt(1, s3.charAt(j + 1));
                s3.setCharAt(j + 1, ch3);

            }

            System.out.println("dooone");

            System.out.println(z);
            for (int x = 0; x <= z; x++) {

                t.add(arr[x]);

            }

        }

        System.out.println(t.size());
        Iterator i55 = t.iterator();
        while (i55.hasNext()) {
            System.out.println(i55.next());
        }
    }

}

I didn't quite follow your explanation, but just by looking at the fact that your code has 3 nested loops, I can tell it won't work for string lengths greater than 3. A better way to generate permutations, without duplicates, is to try putting each of the characters in position 1, and for each possibility, *calling the routine recursively to find a list of all the permutations of the remaining characters*. You then just append each such sub-permutation to your current first character. — j_random_hacker, Mar 30 '14 at 03:57
There is an excellent explanation of the algorithm needed on this post: http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer — Jem, Mar 30 '14 at 04:00
@j_random_hacker.. yes it is not working with 3 and more characters..infact it is working only with 3 characters.but this logic should generate ALL combinations,cuz each character is at every possible position...then i can't comprehend why it wont..pls help if u can or then i will have to try n do it recursively... — user2837260, Mar 30 '14 at 04:15

score 2 · Answer 1 · answered Mar 30 '14 at 06:20

Your 3 nested loops can generate a maximum of n^3 strings for an input string of length n. However, the number of permutations is much larger (n!), so the result set must be partial for large n.

In addition, your argument that the logic should generate all permutations because each character is at every possible position is incorrect. The fact that every single element visits all positions doesn't mean that all possible arrangements are visited. For instance, for n=3:

All items appear in all positions, but the list is still missing the sequences 132 and 231.

If recursion is acceptable, consider the following solution:

public static Collection<String> permutations(String s) {
    ArrayList<String> l = new ArrayList<String>();
    permutations(s.toCharArray(), 0, l);
    return l;
  }

  private static void permutations(char[] chars, int i, ArrayList<String> l) {
    if (i == chars.length) {
      l.add(new String(chars));
      return;
    }

    for (int j = i; j < chars.length; j++) {
      swap(chars, i, j);
      permutations(chars, i + 1, l);
      swap(chars, i, j);
    }
  }

  private static void swap(char[] chars, int i, int j) {
    char tmp = chars[i];
    chars[i] = chars[j];
    chars[j] = tmp;
  }

The inductive idea behind this algorithm is that the permutation set is the union of all permutations of length n-1 resulting by choosing the first character and continuing recursively with the tail. Assuming that the input string has no repeated characters, this union is disjoint, so we don't have to deal with duplicates.

A non recursive solution:

  private static Collection<String> permutations2(String str) {
    ArrayList<String> listNew = new ArrayList<String>();
    ArrayList<String> listPrev = new ArrayList<String>();

    char chr = str.charAt(0);
    listPrev.add("" + chr);

    for (int i = 1; i < str.length(); i++) {
      chr = str.charAt(i);

      for (String s : listPrev) {
        for (int idx = 0; idx <= s.length(); idx++) {
          String perm = s.substring(0, idx) + chr + s.substring(idx);
          listNew.add(perm);
        }
      }

      listPrev = listNew;
      listNew = new ArrayList<String>();
    }
    return listPrev;
  }

The idea is that in phase i we generate all permutations of length i, based on all permutation of length i-1 produced in the previous phase. This is done by inserting the new character in all possible positions of each of the permutations of length i-1. This solution also guarantees uniqueness of results, assuming that the original string has unique characters.

but instead of looking at the solutions , i will try an come up with another working algorith :) — user2837260, Jun 22 '14 at 08:32

score 0 · Answer 2 · edited May 23 '17 at 12:28

0

You can check any of these posts for help:

http://www.programmerinterview.com/index.php/recursion/permutations-of-a-string/

OR

Generating all permutations of a given string

edited May 23 '17 at 12:28

Community

1
1

answered Mar 30 '14 at 04:15

Viraj Pai

205
3
11

thanks but no thanks..please answer if u can help with the erroneous logic – user2837260 Mar 30 '14 at 04:28

permutations of a string...logic error?

2 Answers2