CODEWITHSUNDEEP
javaalgorithmpermutation
Srini Kandula
Srini Kandula

Reputation: 1001

Algorithm for finding all permutations for n alphabets

I wrote the following algorithm for finding all possible permutations of n unique alphabets. 

Set<String> results = new HashSet<String>();
    int size = 1;
            //find the total permutations possible
    for(int i=0;i<array.length;i++){
        size*=(i+1);            
    }
    // i is the number of items remaining to be shuffled.
    while(results.size()<size){
        for (int i = array.length; i > 1; i--) {
            // Pick a random element to swap with the i-th element.
            int j = rng.nextInt(i);  // 0 <= j <= i-1 (0-based array)
            // Swap array elements.
            char tmp = array[j];
            array[j] = array[i-1];
            array[i-1] = tmp;
        }
        StringBuffer str = new StringBuffer();          
        for(int i=0;i<array.length;i++)
            str.append(array[i]);
        results.add(str.toString());
    }
    System.out.println(results);

1) Is there anything to be done to improve this algorithm?
2) What would be the time complexity of this algorithm?

PS: I apologize to the people who who reacted to my previous post. I'll try on my own before asking for help.

Upvotes: 4

Views: 2422

Answers (4)

Srini Kandula
Srini Kandula

Reputation: 1001

Thank you for your inputs. I think I have got a better algorithm. Please provide comments

private static List<String> allPerms(char[] array) {    
  List<String> perms = new ArrayList<String>();
  if(array.length<=1 )
      perms.add(String.valueOf(array[0]));
  else{
      char[] newarray = Arrays.copyOf(array, array.length-1);
      char lastChar = array[array.length-1];
      List<String> soFar = allPerms(newarray);
      for(int i=0; i<soFar.size(); i++) {       
          String curr = soFar.get(i);
          for(int j=0;j<array.length;j++){
              StringBuffer buff = new StringBuffer(curr);
              perms.add(buff.insert(j, lastChar).toString());                 
          }
      }       
    }
return perms; }

Upvotes: 0

J&#233;r&#233;mie
J&#233;r&#233;mie

Reputation: 1373

The best way to generate permutations is to do so iteratively: finding a scheme to go from one permutation to the next until you've seen them all. Knuth has exposed such a scheme in one of the combinatorial fascicles of TAOCP, and without going into his assembly-like pseudo code, you might want to check these nifty C implementation of those algorithms. The algorithm you are looking for is the one that generates permutations.

The advantage of such an algorithm by opposition to (what I understand of) yours, is that it is deterministic and will generate a different permutation every single time.

Upvotes: 2

jpalecek
jpalecek

Reputation: 47770

1) Is there anything to be done to improve this algorithm?

Yes. Just to give you some hints how you could generate the permutations deterministically:

  • imagine the lexicographic order of all permutations on N elements. Imagine, how could you generate the next permutation in that order given the previous

  • think about what would the set of permutations with a common prefix (eg. 435 126, 435 162 etc.) be and how could you use it in an algorithm.

Upvotes: 3

Will A
Will A

Reputation: 25018

By utilizing a random shuffling, you're going to have a massive number of iterations that end up not actually putting a new item into the set - you should look for an approach that ensures that on each iteration a new item is placed into the set (by 'new' I simply mean a permutation that hasn't been seen previously).

I wouldn't like to guess at the time complexity of the algorithm supplied above - it's going to be big.

Upvotes: 3

Related Questions