import java.util.ArrayList;
/** 
  PermuteR calculates, by brute force, the number of permutations, 
  without replacement and taking duplicate choices into account 
  There are different methods: 2 slots using loops, 3 slots using loops, and a general recursive.
  @author Fred Kral
  @version 1.0, 1/27/2015
  */
public class PermuteR {
   /** print more than the basics for explanations and for debugging */
   private static final boolean PRINTMORE = false;
   /** a list for making it easier to communicate with the recursive method */   
   public static ArrayList<String> alist = new ArrayList<String>();
   
   public static void main (String [] args) {
   

      //permuteLoop2();
  
      //permuteRecurse("zachary", 7);
   
      //permuteRecurse("STREET", 6);
      
      //permuteLoop3();
   
      permuteRecurse("122234", 3);
            
   
   } //End main
  

   public static void permuteLoop2 () {
   
      ArrayList<String> slist = new ArrayList<String>();
      slist.add("1");
      slist.add("2");
      slist.add("2");
      slist.add("3");
      //slist.add("4");
      //slist.add("4");
      //slist.add("3");
      //slist.add("2");
      //slist.add("1");
      // Permutations of 1223 taken 2 at a time (answer: 7)
      // 12234 taken 3 at a time
      System.out.println();
      System.out.println("Welcome to the Permutation Machine");
      System.out.println("Number of slots = 2");
      System.out.println(slist);
      System.out.println();
      ArrayList<String> answers = new ArrayList<String>();
      
      int count = 0;
      for (int n = 0; n < slist.size(); n++) {
         String result1 = slist.get(n);
         for (int m = 0; m < slist.size(); m++) {
            if (m == n) 
               continue; // cannot use the same choice twice (no replacement)
            count++;
            String result = result1 + slist.get(m);
            answers.add(result);
            if (PRINTMORE) 
               System.out.printf("count= %3d: %s\r", count, result);
         }
      }    
      System.out.printf("Number of permutations with duplicates = %d\n", answers.size());
      System.out.println(answers);
   
      int p = 0;
      for (String s : answers) {
         p++;
         int q = 0;
         for (String t : answers ) {
            q++;
            if (s == t) 
               continue;
            if (t.equals(s)) {
               System.out.printf("  at %3d, %3d -- marking \"%s\"\n", p, q, answers.get(q-1));
               answers.set(q-1, "");
            }
         }
      }
      for (int i = answers.size() - 1; i >= 0; i--) {
         if (answers.get(i).equals("")) {
            answers.remove(i);
         }
      }
      System.out.printf("Number of permutations without duplicates = %d\n", answers.size());
   
      System.out.println(answers);
   
   } // End method
      
   
   public static void permuteLoop3() {
      ArrayList<String> slist = new ArrayList<String>();
      slist.add("1");
      slist.add("2");
      slist.add("2");
      slist.add("3");
      slist.add("4");
      //slist.add("4");
      //slist.add("3");
      //slist.add("2");
      //slist.add("1");
      // Permutations of 1223 taken 2 at a time (answer: 7)
      // 12234 taken 3 at a time
      System.out.println();
      System.out.println("Welcome to the Permutation Machine");
      System.out.println("Number of slots = 3");
      System.out.println(slist);
      System.out.println();
      ArrayList<String> answers = new ArrayList<String>();
      
      int count = 0;
      for (int n = 0; n < slist.size(); n++) {
         String result1 = slist.get(n);
         for (int m = 0; m < slist.size(); m++) {
            if (m == n)
               continue; // do not replace
            String result2 = slist.get(m);
            for (int k = 0; k < slist.size(); k++) {
               if (k == m | k == n) 
                  continue; // do not replace
               count++;
               String result = result1 + result2 + slist.get(k);
               answers.add(result);
               if (PRINTMORE) 
                  System.out.printf("count= %3d: %s\r", count, result);
            }
         }    
      }
      System.out.printf("Number of permutations with duplicates = %d\n", answers.size());
      System.out.println(answers);
   
      int p = 0;
      for (String s : answers) {
         p++;
         int q = 0;
         for (String t : answers ) {
            q++;
            if (s == t) 
               continue;
            if (t.equals(s)) {
               if (PRINTMORE)
                  System.out.printf("  at %3d, %3d -- marking \"%s\"\n", p, q, answers.get(q-1));
               answers.set(q-1, "");
            }
         }
      }
      for (int i = answers.size() - 1; i >= 0; i--) {
         if (answers.get(i).equals("")) {
            answers.remove(i);
         }
      }
      System.out.printf("Number of permutations without duplicates = %d\n", answers.size());
   
      System.out.println(answers);
      
   } //End method
   
   /** permuteRecurse finds all permutations, chops off extras to have a limited
       number of slots, and then removes duplicates */
   public static void permuteRecurse (String choiceString, int numberOfSlots) {
   
      //String choiceString = "1223";
      //int numberOfSlots = 3;
      if (numberOfSlots > choiceString.length())
         numberOfSlots = choiceString.length();
         
      System.out.println();
      System.out.println("Welcome to the Amazing Permutation Machine");
      System.out.println("Number of slots = " + numberOfSlots);
      System.out.printf("Given \"%s\"\n", choiceString);

      alist.clear();
      /* do the permutations recursively */
      permutation(choiceString);
      //System.out.println(alist);
   
      ArrayList<String> answers = alist;
      System.out.printf("Number of permutations in all slots with duplicates = %d\n", answers.size());
      System.out.println(answers);
      
      /* chop off extra slots */
      
      int j = 0;
      for (String s : answers) {
      
         answers.set( j, answers.get(j).substring(0,numberOfSlots) );
         j++;
      }
   
      int p = 0;
      for (String s : answers) {
         p++;
         int q = 0;
         for (String t : answers ) {
            q++;
            if (s == t) 
               continue;
            if (t.equals(s)) {
               if (PRINTMORE)
                  System.out.printf("  at %3d, %3d -- marking \"%s\"\n", p, q, answers.get(q-1));
               answers.set(q-1, "");
            }
         }
      }
      for (int i = answers.size() - 1; i >= 0; i--) {
         if (answers.get(i).equals("")) {
            answers.remove(i);
         }
      }
      System.out.printf("Number of permutations without duplicates = %d\n", answers.size());
   
      System.out.println(answers);
   
   
   }
      
   public static void permutation(String str) {
      permutation("", str); 
   }

   private static void permutation(String prefix, String str){
      int n = str.length();
      if (n == 0){
         alist.add(prefix);
         if (PRINTMORE)
            System.out.println(prefix);
      }
      else {
         for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
      }
      return;
   }
   
   
} //End class