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());
        }
    }

}

Answer 1

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:

123
213
321
312

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.

Answer 2

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