The Java Program: Perm.java

  1 // Perm.java -- From Java tutorial
  2 
  3 /*
  4   Try:  grep -v -e "[0-9\&\']" /usr/dict/words | java Perm 4
  5 
  6 5: [caret, carte, cater, crate, trace]
  7 4: [least, slate, stale, steal]
  8 4: [leapt, petal, plate, pleat]
  9 ....
 10 */
 11 
 12 import java.util.List;
 13 import java.util.Map;
 14 import java.util.Iterator;
 15 import java.util.HashMap;
 16 import java.util.ArrayList;
 17 import java.util.Collections;
 18 import java.util.Comparator;
 19 import java.util.Scanner;
 20 import java.io.*;
 21 
 22 public class Perm {
 23    public static void main (final String[] args) {
 24       final int minGroupSize = Integer.parseInt (args[0]);
 25       
 26       // Read words from file and put into simulated multimap
 27       final Map<String,List<String>> m = new HashMap<String,List<String>>();
 28 
 29       final Scanner scan = new Scanner (new BufferedInputStream (System.in));
 30 
 31       // Insert words using letters in alphabetical order as key
 32       while (scan.hasNextLine()) {
 33          final String word = scan.nextLine();
 34          final String alpha = alphabetize (word.toLowerCase());
 35          List<String> l = m.get (alpha);
 36          if (l==null) m.put (alpha, l=new ArrayList<String>());
 37          l.add(word);
 38       }
 39 
 40       // Compare by number in group; not consistent with equals
 41       class CompareSize implements Comparator <List<String>> {
 42          public int compare (List<String> o1, List<String> o2) {
 43             return o2.size() - o1.size(); // works for small integers
 44          }
 45       }
 46 
 47       // Make a list of all permutation groups above the size threshold
 48       final ArrayList<List<String>> list = new ArrayList<List<String>> ();
 49       for (List<String> l: m.values()) {
 50          if (l.size() >= minGroupSize) list.add(l);
 51       }
 52       Collections.sort (list, new CompareSize());
 53 
 54       // Print permutation groups according to size
 55       for (List<String> l: list) {
 56          System.out.format ("%2d: %s%n", l.size(), l);
 57       }
 58    }
 59 
 60    private static String alphabetize (final String s) {
 61       final int count[] = new int[256];
 62       final int len = s.length();
 63       for (int i=0; i<len; i++)  count[s.charAt(i)]++;
 64       final StringBuilder result = new StringBuilder (len);
 65       for (char c='a'; c<='z'; c++) {
 66          for (int i=0; i<count[c]; i++) result.append(c);
 67       }
 68       return result.toString();
 69    }
 70 }