a little project I worked on today Next is a graphical version that swaps the letters with a fun little animation.
Code:
Code:
import java.util.*;
/**
*Authored by Thomas Dickerson
*Thanks to Quicksort code from Sedgewick 7.1, 7.2
*Because I am lazy, and there's no reason to reimplement an existing solution
*/
public class AnagramShuffler {
public AnagramShuffler(){}
public String shuffleAnagram(String s1, String s2) {
s1 = s1.toUpperCase();
s2 = s2.toUpperCase();
System.out.println(s1);
Vector<AnagramCharacter> nospaces = stripSpaces(s1);
AnagramCharacter[] anagram = new AnagramCharacter[nospaces.size()];
nospaces.toArray(anagram);
Vector<AnagramCharacter> finalAns = stripSpaces(s2);
quicksort(anagram, 0, anagram.length - 1, finalAns);
return insertSpaces(anagram, s2);
}
protected void quicksort(AnagramCharacter[] anagram, int left, int right, Vector<AnagramCharacter> newPhrase) {
if (right <= left) return;
int i = partition(anagram, left, right, newPhrase);
quicksort(anagram, left, i-1, newPhrase);
quicksort(anagram, i+1, right, newPhrase);
}
protected Vector<AnagramCharacter> stripSpaces(String s){
Vector<AnagramCharacter> buf = new Vector<AnagramCharacter>();
Hashtable<Character,Integer> occurrences = new Hashtable<Character,Integer>();
for(int i = 0; i<s.length(); i++){
char c = s.charAt(i);
if(Character.isLetterOrDigit(c)){
//System.out.println("Contains " + Character.valueOf(c).toString() + " ? " + occurrences.containsKey(Character.valueOf(c)));
int numOcc = occurrences.containsKey(Character.valueOf(c)) ? (1 + occurrences.get(Character.valueOf(c)).intValue()) : 0;
buf.add(new AnagramCharacter(c, numOcc));
//System.out.println("Character: " + c + " occurrence: " + numOcc);
occurrences.put(Character.valueOf(c), Integer.valueOf(numOcc));
}
}
return buf;
}
protected String arrayToString(AnagramCharacter[] charList){
StringBuffer buf = new StringBuffer();
for(int i = 0; i<charList.length; i++) buf.append(charList[i].toString());
return buf.toString();
}
protected String insertSpaces(AnagramCharacter[] charList, String spacesList){
int spacesCount = 0;
StringBuffer buf = new StringBuffer();
for(int i = 0; i<spacesList.length(); i++){
char c = spacesList.charAt(i);
if(Character.isLetterOrDigit(c)) buf.append(charList[i - spacesCount].toString());
else{
buf.append(spacesList.charAt(i));
spacesCount++;
}
}
return buf.toString();
}
protected int partition(AnagramCharacter[] anagram, int left, int right, Vector<AnagramCharacter> newPhrase) {
int i = left - 1;
int j = right;
while (true) {
while (less(anagram[++i], anagram[right], newPhrase));
while (less(anagram[right], anagram[--j], newPhrase)) if (j == left) break;
if (i >= j) break;
exch(anagram, i, j);
System.out.println(arrayToString(anagram));
}
exch(anagram, i, right);
System.out.println(arrayToString(anagram));
return i;
}
// is x < y ?
protected boolean less(AnagramCharacter x, AnagramCharacter y, Vector<AnagramCharacter> newPhrase) {
//System.out.println("x: " + x + " y: " + y);
int xPos= newPhrase.indexOf(x);
int yPos = newPhrase.indexOf(y);
//System.out.println("xPos: " + xPos + " yPos: " + yPos);
return (xPos < yPos);
}
// exchange a[i] and a[j]
protected void exch(AnagramCharacter[] a, int i, int j) {
AnagramCharacter swap = a[i];
a[i] = a[j];
a[j] = swap;
}
// test client
public static void main(String[] args) {
AnagramShuffler shuffleItUp = new AnagramShuffler();
System.out.println("<==><==><==><=====><==><==><==>");
System.out.println("Welcome to the Anagram Shuffler");
System.out.println("<==><==><==><=====><==><==><==>");
System.out.println("");
System.out.println(" Program Design By");
System.out.println(" Thomas D. Dickerson");
System.out.println("");
System.out.println("+-----------------------------+");
System.out.println("| Please note that unmatching|");
System.out.println("|letters and numbers between |");
System.out.println("|phrases may result in strange|");
System.out.println("|things happening... |");
System.out.println("+-----------------------------+");
System.out.println("");
Scanner myScanner = new Scanner(System.in);
System.out.print("Enter the first phrase: ");
String s1 = myScanner.nextLine();
System.out.println("");
System.out.print("Enter the second phrase: ");
String s2 = myScanner.nextLine();
System.out.println("");
System.out.println(shuffleItUp.shuffleAnagram(s1, s2));
}
private class AnagramCharacter{
private int count;
private char val;
public AnagramCharacter(char c, int i){ val = c; count = i; }
public int getCount(){ return count; }
public String toString(){ return Character.toString(val); }
public char charValue(){ return val; }
public boolean equals(Object o){
try{
return equals((AnagramCharacter)o);
} catch(Exception e){
e.printStackTrace();
return super.equals(o);
}
}
public boolean equals(AnagramCharacter o){ return (o.count == count) && (o.val == val);}
}
}