// Anagrams.java
// Andrew Davison, ad@coe.psu.ac.th, Dec. 2022

/* Unlike SingleAnagrams.java, this program allows the input
   string to be split, in order to generate several words based
   on the input.

   For an input string of 11 characters or less, the 
   program can be implemented by calling
   WordUtils.permute() or WordUtils.ipermute(),
   the recursive and iteration permutation functions. However,
   the program runs out of memory when asked to find anagrams
   of a 12 character word.

   The problem is that both functions generate all the permutations
   at once, storing them in a single, very big, list
   before passing them to WordUtils.partitions() and
   Hunspell. This list is simply too large,
   with 12! strings (479001600). It's possible to give Java a larger 
   heap space, but a better solution is to calculate the permutations
   using the Factoradic number system. This is explained in 
   FactPermutes.java, and implementd as WordUtils.fpermute().

   From a practical point of view, the n! permutations can be generated
   incrementally (e.g. in a loop in the code below), rather than all
   at once. That means that there's no need to build a massive list
   before calling partitions() and Hunspell.

   For anagram input ideas, I referred to:
   https://sites.ualberta.ca/~jcc/Funny/anagrams.html

  Usage:
    > compile Anagrams.java
    > run Anagrams <word>
  e.g.
    > run Anagrams animosity       // 9-letters
    > run Anagrams evangelist      // 10-letters
    > run Anagrams desperation     // 11-letters

    > run Anagrams themorsecode    // 12-letters
    > run Anagrams elevenplustwo    // 13-letters
        -- still takes a VERY long time, but doesn't run out of memory
*/


import java.io.*;
import java.util.*;


public class Anagrams
{

  public static void main(String args[])
  {
    if (args.length != 1) {
      System.out.println("Usage: java Anagrams <word>");
      return;
    }
    String word = args[0];

    HunspellChecker hsc = new HunspellChecker();
        
    List<List<String>> anagrams = new ArrayList<>();

    char[] letters = word.toCharArray();
    long numPerms = factorial(letters.length);
         // We need to know how many permutations will be generated

    /* Here's the code that generates a single list
       of permutations before calling partitions() and Hunspell.  */
    // ArrayList<String> permutes = WordUtils.ipermutes(word);

    for(long i=0; i < numPerms; i++) {
      String perm = WordUtils.fpermute(i, letters);  
               // generates one string -- the ith permutation of letters
      List<List<String>> permParts = WordUtils.partitions(perm);
      for (List<String> sentence : permParts) {
        if (areWords(sentence, hsc)) {
          Collections.sort(sentence);
             /* the list of words (sentence) is sorted so that
                the words will be in a standard order, which can be
                compared to the sentences already in the anagrams list
             */
          if (!inList(anagrams, sentence)) {  // only keep sentence if it's new
            anagrams.add(sentence);
            System.out.println( Arrays.toString( sentence.toArray() ));
          }
        }
      }
    }

    hsc.close();
  } /* main */



  private static long factorial(int f)
  /* I've used long here rather than int, so that factorial
     can handle values up to 20. The int type can only
     deal with a maximum value of 12. 

    fact(13) is bigger than 2^32, fact(21) is bigger than 2^64
  */
  { if (f == 0)
      return 1L;
    else
      return f*factorial(f-1);
  }


  private static boolean inList(List<List<String>> anagrams, 
                                List<String> sentence)
  // is the sentence already in the anagrams list?
  {
    for(List<String> anagram : anagrams)
      if (anagram.equals(sentence))
        return true;
    return false;
  } // inList()


  private static boolean areWords(List<String> sentence,
                                    HunspellChecker hsc)
  { for(String s : sentence) {
      if (!hsc.isCorrect(s) || !isValid(s))
        return false;
    }
    return true;
  }


  private static boolean isValid(String word)
  /* Strip out most single letter words, 
     and unusual 2- and 3- letter words. The common words
     lists were added since Hunspell was letting through too
     many Scrabble-like words which don't seem like 'real' words
     to me.
  */
  {
    if (word.length() == 1) {
      char ch = word.charAt(0);
      if ((ch == 'a') || (ch == 'i') || (ch == 'o'))
        return true;
      else
        return false;
    }
    else if (word.length() == 2)
      return WordUtils.COMMON_TWOS.contains(word);
    else if (word.length() == 3)
      return WordUtils.COMMON_THREES.contains(word);

    return true;
  }  // end of isValid()


}  // end of Anagrams class