Question

Create a class that generates permutations of a set of symbols.

Requirements

The class must be named PermutationGenerator.

The PermutationGenerator class has two methods as follows.
hasNext
This method has no parameters.  It returns true if at least one permutation remains to be generated.
next
This method has no parameters.  It returns an array of the symbols (char[]) in a permutation (if any remain) or null otherwise.

The following main method MUST be used, with NO CHANGES to test your class.

public static void main(String[] args) { int count = 0; PermutationGenerator pg = new PermutationGenerator(new char[] { 'R', 'E', 'G', 'A', 'L' }); while (pg.hasNext()) { count++; char[] permutation = pg.next(); for (char symbol : permutation) System.out.print(symbol + " "); System.out.println(); } System.out.println("Total permutations = " + count); }

Recursion MUST NOT be used.

Answer 1

Here is the program in java

import java.util.ArrayList;
import java.util.List;

class PermutationGenerator{
List<String> permutation;
int currentIdx = 0;
PermutationGenerator(char word[]) {
  
String s = new String(word);
   // create an empty ArrayList to store partial permutations
       permutation = new ArrayList<>();
  
       // initialize the list with the first character of the string
       permutation.add(String.valueOf(s.charAt(0)));
  
       // do for every character of the specified string
       for (int i = 1; i < s.length(); i++)
       {
           // consider previously constructed partial permutation one by one
           // (iterate backwards to avoid ConcurrentModificationException)
           for (int j = permutation.size() - 1; j >= 0 ; j--)
           {
               // remove current partial permutation from the ArrayList
               String str = permutation.remove(j);
              
               // Insert next character of the specified string in all
               // possible positions of current partial permutation. Then
               // insert each of these newly constructed string in the list
  
               for (int k = 0; k <= str.length(); k++)
               {
                   permutation.add(str.substring(0, k) + s.charAt(i) + str.substring(k));
               }
           }
       }
       //System.out.println(permutation);
       //System.out.println(permutation.size());
}
public char[] next() {
  
if((currentIdx+1) <= permutation.size())
return permutation.get(currentIdx++).toCharArray();
return new char[0];
}
public boolean hasNext() {
return (currentIdx < permutation.size());
}
  
}

public class Main
{
   public static void main(String[] args) {
   int count = 0;
   PermutationGenerator pg = new PermutationGenerator(new char[] { 'R', 'E', 'G', 'A', 'L' });
  
   while (pg.hasNext()) {
   count++;
   char[] permutation = pg.next();
   for (char symbol : permutation)
   System.out.print(symbol + " ");
   System.out.println();
   }
  
   System.out.println("Total permutations = " + count);
  
   }
}

The part of Sample output:

It generate 120 permutations of the word. which is correct , because the length of the array is 5 and fact(5) = 120.