Java/Collections Data Structure/Algorithms

Перейти к: навигация, поиск

Anagrams

<source lang="java">

import java.io.IOException; public class AnagramApp {

static int size;
static int count;
static char[] charArray;
public static void main(String[] args) throws IOException {
String input = "Java Source and Support";
size = input.length();
count = 0;
charArray = new char[size];
for (int j = 0; j < size; j++)
charArray[j] = input.charAt(j);
doAnagram(size);
}
public static void doAnagram(int newSize) {
int limit;
if (newSize == 1) // if too small, return;
return;
// for each position,
for (int i = 0; i < newSize; i++) {
doAnagram(newSize - 1); // anagram remaining
if (newSize == 2) // if innermost,
display();
rotate(newSize); // rotate word
}
}
// rotate left all chars from position to end
public static void rotate(int newSize) {
int i;
int position = size - newSize;
// save first letter
char temp = charArray[position];
//shift others left
for (i = position + 1; i < size; i++)
charArray[i - 1] = charArray[i];
//put first on right
charArray[i - 1] = temp;
}
public static void display() {
System.out.print(++count + " ");
for (int i = 0; i < size; i++)
System.out.print(charArray[i]);
System.out.println();
}

}

</source>

Compute prime numbers

<source lang="java">

/* Compute prime numbers, after Knuth, Vol 1, Sec 1.3.2, Alg. "P".

* Unlike Knuth, I don"t build table formatting into
* computational programs; output is one per line.
*

* Note that there may be more efficient algorithms for finding primes. * Consult a good book on numerical algorithms. * @author Ian Darwin */ public class Primes { /** The default stopping point for primes */ public static final long DEFAULT_STOP = 4294967295L; /** The first prime number */ public static final int FP = 2; static int MAX = 10000; public static void main(String[] args) { long[] prime = new long[MAX]; long stop = DEFAULT_STOP; if (args.length == 1) { stop = Long.parseLong(args); } prime = FP; // P1 (ignore prime) long n = FP+1; // odd candidates int j = 1; // numberFound boolean isPrime = true; // for 3 do { if (isPrime) { if (j == MAX-1) { // Grow array dynamically if needed long[] np = new long[MAX * 2]; System.arraycopy(prime, 0, np, 0, MAX); MAX *= 2; prime = np; } prime[++j] = n; // P2 isPrime = false; } n += 2; // P4 for (int k = 2; k <= j && k < MAX; k++) { // P5, P6, P8 long q = n / prime[k]; long r = n % prime[k]; if (r == 0) { break; } if (q <= prime[k]) { // P7 isPrime = true; break; } } } while (n < stop); // P3 for (int i=1; i<=j; i++) System.out.println(prime[i]); } } </source>

Compute the area of a triangle using Heron"s Formula

<source lang="java">

/** Compute the area of a triangle using Heron"s Formula.

* Code and values from Prof W. Kahan and Joseph D. Darcy.
* See http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf.
* Derived from listing in Rick Grehan"s Java Pro article (October 1999).
* Simplified and reformatted by Ian Darwin.
*/

public class Heron {

public static void main(String[] args) {
// Sides for triangle in float
float af, bf, cf;
float sf, areaf;
// Ditto in double
// Area of triangle in float
af = 12345679.0f;
bf = 12345678.0f;
cf = 1.01233995f;
sf = (af+bf+cf)/2.0f;
areaf = (float)Math.sqrt(sf * (sf - af) * (sf - bf) * (sf - cf));
System.out.println("Single precision: " + areaf);
// Area of triangle in double
bd = 12345678.0;
cd = 1.01233995;
aread =        Math.sqrt(sd * (sd - ad) * (sd - bd) * (sd - cd));
}

}

</source>

Fibonacci

<source lang="java">

/*

* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/

/**

* This program prints out the first 20 numbers in the Fibonacci sequence. Each
* term is formed by adding together the previous two terms in the sequence,
* starting with the terms 1 and 1.
*/

public class Fibonacci {

public static void main(String[] args) {
int n0 = 1, n1 = 1, n2; // Initialize variables
System.out.print(n0 + " " + // Print first and second terms
n1 + " "); // of the series
for (int i = 0; i < 18; i++) { // Loop for the next 18 terms
n2 = n1 + n0; // Next term is sum of previous two
System.out.print(n2 + " "); // Print it out
n0 = n1; // First previous becomes 2nd previous
n1 = n2; // And current number becomes previous
}
System.out.println(); // Terminate the line
}

}

</source>

Find connections using a depth-first search

<source lang="java">

/*

* Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
* James Holmes McGraw-Hill/Osborne 2003
*
*/

//The entire depth-first search program follows: //Find connections using a depth-first search. import java.util.*; import java.io.*; //Flight information. class FlightInfo {

String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}

} public class Depth {

final int MAX = 100; // maximum number of connections
// This array holds the flight information.
FlightInfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack
public static void main(String args[]) {
String to, from;
Depth ob = new Depth();
ob.setup();
try {
System.out.print("From? ");
System.out.print("To? ");
ob.isflight(from, to);
if (ob.btStack.size() != 0)
ob.route(to);
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
//Initialize the flight database.
void setup() {
}
//Put flights into the database.
void addFlight(String from, String to, int dist) {
if (numFlights < MAX) {
flights[numFlights] = new FlightInfo(from, to, dist);
numFlights++;
} else
System.out.println("Flight database full.\n");
}
// Show the route and total distance.
void route(String to) {
Stack rev = new Stack();
int dist = 0;
FlightInfo f;
int num = btStack.size();
// Reverse the stack to display route.
for (int i = 0; i < num; i++)
rev.push(btStack.pop());
for (int i = 0; i < num; i++) {
f = (FlightInfo) rev.pop();
System.out.print(f.from + " to ");
dist += f.distance;
}
System.out.println(to);
System.out.println("Distance is " + dist);
}
/*
* If there is a flight between from and to, return the distance of flight;
* otherwise, return 0.
*/
int match(String from, String to) {
for (int i = numFlights - 1; i > -1; i--) {
if (flights[i].from.equals(from) && flights[i].to.equals(to)
&& !flights[i].skip) {
flights[i].skip = true; // prevent reuse
return flights[i].distance;
}
}
}
// Given from, find any connection.
FlightInfo find(String from) {
for (int i = 0; i < numFlights; i++) {
if (flights[i].from.equals(from) && !flights[i].skip) {
FlightInfo f = new FlightInfo(flights[i].from, flights[i].to,
flights[i].distance);
flights[i].skip = true; // prevent reuse
return f;
}
}
return null;
}
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
FlightInfo f;
// See if at destination.
dist = match(from, to);
if (dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
// Try another connection.
f = find(from);
if (f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}

}

</source>

Find connections using hill climbing.

<source lang="java">

/* The Art of Java by Herbert Schildt and James Holmes McGraw-Hill/Osborne ? 2003

• /

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; //Flight information. class FlightInfo {

String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}

} public class Hill {

final int MAX = 100;
// This array holds the flight information.
FlightInfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack
public static void main(String args[]) {
String to, from;
Hill ob = new Hill();
ob.setup();
try {
System.out.print("From? ");
System.out.print("To? ");
ob.isflight(from, to);
if (ob.btStack.size() != 0)
ob.route(to);
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
// Initialize the flight database.
void setup() {
}
// Put flights into the database.
void addFlight(String from, String to, int dist) {
if (numFlights < MAX) {
flights[numFlights] = new FlightInfo(from, to, dist);
numFlights++;
} else
System.out.println("Flight database full.\n");
}
// Show the route and total distance.
void route(String to) {
Stack rev = new Stack();
int dist = 0;
FlightInfo f;
int num = btStack.size();
// Reverse the stack to display route.
for (int i = 0; i < num; i++)
rev.push(btStack.pop());
for (int i = 0; i < num; i++) {
f = (FlightInfo) rev.pop();
System.out.print(f.from + " to ");
dist += f.distance;
}
System.out.println(to);
System.out.println("Distance is " + dist);
}
/*
* If there is a flight between from and to, return the distance of flight;
* otherwise, return 0.
*/
int match(String from, String to) {
for (int i = numFlights - 1; i > -1; i--) {
if (flights[i].from.equals(from) && flights[i].to.equals(to)
&& !flights[i].skip) {
flights[i].skip = true; // prevent reuse
return flights[i].distance;
}
}
}
// Given from, find the farthest away connection.
FlightInfo find(String from) {
int pos = -1;
int dist = 0;
for (int i = 0; i < numFlights; i++) {
if (flights[i].from.equals(from) && !flights[i].skip) {
// Use the longest flight.
if (flights[i].distance > dist) {
pos = i;
dist = flights[i].distance;
}
}
}
if (pos != -1) {
flights[pos].skip = true; // prevent reuse
FlightInfo f = new FlightInfo(flights[pos].from, flights[pos].to,
flights[pos].distance);
return f;
}
return null;
}
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
FlightInfo f = null;
// See if at destination.
dist = match(from, to);
if (dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
// Try another connection. f = find(from);
if (f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}

}

</source>

Find optimal solution using least-cost

<source lang="java">

/*

* Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
* James Holmes McGraw-Hill/Osborne ? 2003
*/

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; // Flight information. class FlightInfo {

String from;
String to;
int distance;
boolean skip; // used in backtracking
FlightInfo(String f, String t, int d) {
from = f;
to = t;
distance = d;
skip = false;
}

} public class Optimal {

final int MAX = 100;
// This array holds the flight information.
FlightInfo flights[] = new FlightInfo[MAX];
int numFlights = 0; // number of entries in flight array
Stack btStack = new Stack(); // backtrack stack
Stack optimal; // holds optimal solution
int minDist = 10000;
public static void main(String args[]) {
String to, from;
Optimal ob = new Optimal();
boolean done = false;
FlightInfo f;
ob.setup();
try {
System.out.print("From? ");
System.out.print("To? ");
do {
ob.isflight(from, to);
if (ob.btStack.size() == 0)
done = true;
else {
ob.route(to);
ob.btStack = new Stack();
}
} while (!done);
// Display optimal solution.
if (ob.optimal != null) {
System.out.println("Optimal solution is: ");
int num = ob.optimal.size();
for (int i = 0; i < num; i++) {
f = (FlightInfo) ob.optimal.pop();
System.out.print(f.from + " to ");
}
System.out.println(to);
System.out.println("Distance is " + ob.minDist);
}
} catch (IOException exc) {
System.out.println("Error on input.");
}
}
// Initialize the flight database.
void setup() {
}
// Put flights into the database.
void addFlight(String from, String to, int dist) {
if (numFlights < MAX) {
flights[numFlights] = new FlightInfo(from, to, dist);
numFlights++;
} else
System.out.println("Flight database full.\n");
}
// Save shortest route.
void route(String to) {
int dist = 0;
FlightInfo f;
int num = btStack.size();
Stack optTemp = new Stack();
for (int i = 0; i < num; i++) {
f = (FlightInfo) btStack.pop();
optTemp.push(f); // save route
dist += f.distance;
}
// If shorter, keep this route
if (minDist > dist) {
optimal = optTemp;
minDist = dist;
}
}
/*
* If there is a flight between from and to, return the distance of flight;
* otherwise, return 0.
*/
int match(String from, String to) {
for (int i = numFlights - 1; i > -1; i--) {
if (flights[i].from.equals(from) && flights[i].to.equals(to)
&& !flights[i].skip) {
flights[i].skip = true; // prevent reuse
return flights[i].distance;
}
}
}
// Given from, find any connection using least-cost.
FlightInfo find(String from) {
int pos = -1;
int dist = 10000; // longer than longest route
for (int i = 0; i < numFlights; i++) {
if (flights[i].from.equals(from) && !flights[i].skip) {
// Use the shortest flight.
if (flights[i].distance < dist) {
pos = i;
dist = flights[i].distance;
}
}
}
if (pos != -1) {
flights[pos].skip = true; // prevent reuse
FlightInfo f = new FlightInfo(flights[pos].from, flights[pos].to,
flights[pos].distance);
return f;
}
return null;
}
// Determine if there is a route between from and to.
void isflight(String from, String to) {
int dist;
FlightInfo f;
// See if at destination.
dist = match(from, to);
if (dist != 0) {
btStack.push(new FlightInfo(from, to, dist));
return;
}
// Try another connection.
f = find(from);
if (f != null) {
btStack.push(new FlightInfo(from, to, f.distance));
isflight(f.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
f = (FlightInfo) btStack.pop();
isflight(f.from, f.to);
}
}

}

</source>

Find the lost keys

<source lang="java">

/*

*
* Chapter 10 - AI-Based Problem Solving The Art of Java by Herbert Schildt and
* James Holmes McGraw-Hill/Osborne 2003
*/

import java.util.Stack; //Room information. class RoomInfo {

String from;
String to;
boolean skip;
RoomInfo(String f, String t) {
from = f;
to = t;
skip = false;
}

} public class Keys {

final int MAX = 100;
// This array holds the room information.
RoomInfo room[] = new RoomInfo[MAX];
int numRooms = 0; // number of rooms
Stack btStack = new Stack(); // backtrack stack
public static void main(String args[]) {
String to, from;
Keys ob = new Keys();
ob.setup();
from = "front_door";
to = "keys";
ob.iskeys(from, to);
if (ob.btStack.size() != 0)
ob.route(to);
}
// Initialize the room database.
void setup() {
}
// Put rooms into the database.
void addRoom(String from, String to) {
if (numRooms < MAX) {
room[numRooms] = new RoomInfo(from, to);
numRooms++;
} else
System.out.println("Room database full.\n");
}
// Show the route.
void route(String to) {
Stack rev = new Stack();
RoomInfo r;
int num = btStack.size();
// Reverse the stack to display path.
for (int i = 0; i < num; i++)
rev.push(btStack.pop());
for (int i = 0; i < num; i++) {
r = (RoomInfo) rev.pop();
System.out.print(r.from + " to ");
}
System.out.println(to);
}
/*
* If there is a path between from and to, return true, otherwise return
* false.
*/
boolean match(String from, String to) {
for (int i = numRooms - 1; i > -1; i--) {
if (room[i].from.equals(from) && room[i].to.equals(to)
&& !room[i].skip) {
room[i].skip = true; // prevent reuse
return true;
}
}
}
// Given from, find any path.
RoomInfo find(String from) {
for (int i = 0; i < numRooms; i++) {
if (room[i].from.equals(from) && !room[i].skip) {
RoomInfo r = new RoomInfo(room[i].from, room[i].to);
room[i].skip = true; // prevent reuse
return r;
}
}
return null;
}
// Determine if there is a path between from and to.
void iskeys(String from, String to) {
int dist;
RoomInfo r;
// See if at destination.
if (match(from, to)) {
btStack.push(new RoomInfo(from, to));
return;
}
// Try another connection.
r = find(from);
if (r != null) {
btStack.push(new RoomInfo(from, to));
iskeys(r.to, to);
} else if (btStack.size() > 0) {
// Backtrack and try another connection.
r = (RoomInfo) btStack.pop();
iskeys(r.from, r.to);
}
}

}

</source>

Hanoi puzzle

<source lang="java">

public class HanoiTower {

static int nDisks = 3;
public static void main(String[] args) {
hanoiTower(nDisks, "A", "B", "C");
}
public static void hanoiTower(int topN, char src, char inter, char dest) {
if (topN == 1)
System.out.println("Disk 1 from " + src + " to " + dest);
else {
// src to inter
hanoiTower(topN - 1, src, dest, inter);
// move bottom
System.out.println("Disk " + topN + " from " + src + " to " + dest);
//inter to dest
hanoiTower(topN - 1, inter, src, dest);
}
}

}

</source>

Print a table of fahrenheit and celsius temperatures 1

<source lang="java">

/* Print a table of Fahrenheit and Celsius temperatures

* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version \$Id: TempConverter.java,v 1.10 2004/03/16 01:43:31 ian Exp \$
*/

public class TempConverter {

public static void main(String[] args) {
TempConverter t = new TempConverter();
t.start();
t.data();
t.end();
}
protected void start() {
}
protected void data() {
for (int i=-40; i<=120; i+=10) {
float c = (i-32)*(5f/9);
print(i, c);
}
}
protected void print(float f, float c) {
System.out.println(f + " " + c);
}
protected void end() {
}

}

</source>

Print a table of fahrenheit and celsius temperatures 2

<source lang="java">

import java.text.*; /* Print a table of fahrenheit and celsius temperatures, a bit more neatly.

* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version \$Id: TempConverter2.java,v 1.6 2004/03/07 02:50:49 ian Exp \$
*/

public class TempConverter2 extends TempConverter {

protected DecimalFormat df;
public static void main(String[] args) {
TempConverter t = new TempConverter2();
t.start();
t.data();
t.end();
}
// Constructor
public TempConverter2() {
df = new DecimalFormat("#0.00");
}
protected void print(float f, float c) {
System.out.println(df.format(f) + " " + df.format(c));
}
protected void start() {
}
protected void end() {
System.out.println("-------------------");
}

} class TempConverter {

public static void main(String[] args) {
TempConverter t = new TempConverter();
t.start();
t.data();
t.end();
}
protected void start() {
}
protected void data() {
for (int i=-40; i<=120; i+=10) {
float c = (i-32)*(5f/9);
print(i, c);
}
}
protected void print(float f, float c) {
System.out.println(f + " " + c);
}
protected void end() {
}

}

</source>

Print a table of Fahrenheit and Celsius temperatures 3

<source lang="java">

import java.text.*; /* Print a table of Fahrenheit and Celsius temperatures, with decimal

* points lined up.
* @author Ian F. Darwin, http://www.darwinsys.ru/
* @version \$Id: TempConverter3.java,v 1.4 2004/03/07 02:50:49 ian Exp \$
*/

public class TempConverter3 extends TempConverter2 {

protected FieldPosition fp;
protected DecimalFormat dff;
public static void main(String[] args) {
TempConverter t = new TempConverter3();
t.start();
t.data();
t.end();
}
// Constructor
public TempConverter3() {
super();
dff = new DecimalFormat("#0.0");
fp = new FieldPosition(NumberFormat.INTEGER_FIELD);
}
protected void print(float f, float c) {
String fs = dff.format(f, new StringBuffer(), fp).toString();
fs = prependSpaces(4 - fp.getEndIndex(), fs);
String cs = df.format(c, new StringBuffer(), fp).toString();
cs = prependSpaces(4 - fp.getEndIndex(), cs);
System.out.println(fs + "  " + cs);
}
protected String prependSpaces(int n, String s) {
String[] res = {
"", " ", "  ", "   ", "    ", "     "
};
if (n<res.length)
return res[n] + s;
throw new IllegalStateException("Rebuild with bigger \"res\" array.");
}

}

class TempConverter2 extends TempConverter {

protected DecimalFormat df;
public static void main(String[] args) {
TempConverter t = new TempConverter2();
t.start();
t.data();
t.end();
}
// Constructor
public TempConverter2() {
df = new DecimalFormat("#0.00");
}
protected void print(float f, float c) {
System.out.println(df.format(f) + " " + df.format(c));
}
protected void start() {
}
protected void end() {
System.out.println("-------------------");
}

} class TempConverter {

public static void main(String[] args) {
TempConverter t = new TempConverter();
t.start();
t.data();
t.end();
}
protected void start() {
}
protected void data() {
for (int i=-40; i<=120; i+=10) {
float c = (i-32)*(5f/9);
print(i, c);
}
}
protected void print(float f, float c) {
System.out.println(f + " " + c);
}
protected void end() {
}

}

</source>

Sieve

<source lang="java">

/*

* This code is from the book Java Examples in a Nutshell, 2nd Edition.
* It is provided AS-IS, WITHOUT ANY WARRANTY either expressed or implied.
* You may study, use, and modify it for any non-commercial purpose.
* You may distribute it non-commercially as long as you retain this notice.
* For a commercial use license, or to purchase the book (recommended),
* visit http://www.davidflanagan.ru/javaexamples2.
*/

/**

* This program computes prime numbers using the Sieve of Eratosthenes
* algorithm: rule out multiples of all lower prime numbers, and anything
* remaining is a prime. It prints out the largest prime number less than or
* equal to the supplied command-line argument.
*/

public class Sieve {

public static void main(String[] args) {
// We will compute all primes less than the value specified on the
// command line, or, if no argument, all primes less than 100.
int max = 100; // Assign a default value
try {
max = Integer.parseInt(args);
} // Parse user-supplied arg
catch (Exception e) {
} // Silently ignore exceptions.
// Create an array that specifies whether each number is prime or not.
boolean[] isprime = new boolean[max + 1];
// Assume that all numbers are primes, until proven otherwise.
for (int i = 0; i <= max; i++)
isprime[i] = true;
// However, we know that 0 and 1 are not primes. Make a note of it.
isprime = isprime = false;
// To compute all primes less than max, we need to rule out
// multiples of all integers less than the square root of max.
int n = (int) Math.ceil(Math.sqrt(max)); // See java.lang.Math class
// Now, for each integer i from 0 to n:
//   If i is a prime, then none of its multiples are primes,
//   so indicate this in the array. If i is not a prime, then
//   its multiples have already been ruled out by one of the
//   prime factors of i, so we can skip this case.
for (int i = 0; i <= n; i++) {
if (isprime[i]) // If i is a prime,
for (int j = 2 * i; j <= max; j = j + i)
// loop through multiples
isprime[j] = false; // they are not prime.
}
// Now go look for the largest prime:
int largest;
for (largest = max; !isprime[largest]; largest--)
; // empty loop body
// Output the result
System.out.println("The largest prime less than or equal to " + max
+ " is " + largest);
}

}

</source>

Soundex - the Soundex Algorithm, as described by Knuth

<source lang="java">

/*

* Copyright (c) Ian F. Darwin, http://www.darwinsys.ru/, 1996-2002.
* \$Id: LICENSE,v 1.8 2004/02/09 03:33:38 ian Exp \$
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
*    notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
*    notice, this list of conditions and the following disclaimer in the
*    documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS""
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
* POSSIBILITY OF SUCH DAMAGE.
*
* Java, the Duke mascot, and all variants of Sun"s Java "steaming coffee
* cup" logo are trademarks of Sun Microsystems. Sun"s, and James Gosling"s,
* pioneering role in inventing and promulgating (and standardizing) the Java
* language and environment is gratefully acknowledged.
*
* The pioneering role of Dennis Ritchie and Bjarne Stroustrup, of AT&T, for
* inventing predecessor languages C and C++ is also gratefully acknowledged.
*/

/**

* Soundex - the Soundex Algorithm, as described by Knuth
* <p>
* This class implements the soundex algorithm as described by Donald
* Knuth in Volume 3 of The Art of Computer Programming.  The
* algorithm is intended to hash words (in particular surnames) into
* a small space using a simple model which approximates the sound of
* the word when spoken by an English speaker.  Each word is reduced
* to a four character string, the first character being an upper case
* letter and the remaining three being digits. Double letters are
* collapsed to a single digit.
*
*

EXAMPLES

* Knuth"s examples of various names and the soundex codes they map
* to are:
* Euler, Ellery -> E460
* <b>Gauss, Ghosh -> G200
* <b>Hilbert, Heilbronn -> H416
* <b>Knuth, Kant -> K530
* <b>Lukasiewicz, Lissajous -> L222
*
*

LIMITATIONS

* As the soundex algorithm was originally used a <B>long time ago
* in the United States of America, it uses only the English alphabet
* and pronunciation.
* <p>
* As it is mapping a large space (arbitrary length strings) onto a
* small space (single letter plus 3 digits) no inference can be made
* about the similarity of two strings which end up with the same
* soundex code.  For example, both "Hilbert" and "Heilbronn" end up
* with a soundex code of "H416".
* <p>
* The soundex() method is static, as it maintains no per-instance
* state; this means you never need to instantiate this class.
*
* @author Perl implementation by Mike Stok (<stok@cybercom.net>) from
* the description given by Knuth.  Ian Phillips (<ian@pipex.net>) and
* Rich Pinder (<rpinder@hsc.usc.edu>) supplied ideas and spotted
* mistakes.
* @author Ian Darwin, http://www.darwinsys.ru/ (Java Version)
* @version \$Id: Soundex.java,v 1.9 2004/02/23 00:30:49 ian Exp \$
*/

public class Soundex {

/* Implements the mapping
* from: AEHIOUWYBFPVCGJKQSXZDTLMNR
* to:   00000000111122222222334556
*/
public static final char[] MAP = {
//A  B   C   D   E   F   G   H   I   J   K   L   M
"0","1","2","3","0","1","2","0","0","2","2","4","5",
//N  O   P   W   R   S   T   U   V   W   X   Y   Z
"5","0","1","2","6","2","3","0","1","0","2","0","2"
};
/** Convert the given String to its Soundex code.
* @return null If the given string can"t be mapped to Soundex.
*/
public static String soundex(String s) {
// Algorithm works on uppercase (mainframe era).
String t = s.toUpperCase();
StringBuffer res = new StringBuffer();
char c, prev = "?";
// Main loop: find up to 4 chars that map.
for (int i=0; i<t.length() && res.length() < 4 &&
(c = t.charAt(i)) != ","; i++) {
// Check to see if the given character is alphabetic.
// Text is already converted to uppercase. Algorithm
// only handles ASCII letters, do NOT use Character.isLetter()!
// Also, skip double letters.
if (c>="A" && c<="Z" && c != prev) {
prev = c;
// First char is installed unchanged, for sorting.
if (i==0)
res.append(c);
else {
char m = MAP[c-"A"];
if (m != "0")
res.append(m);
}
}
}
if (res.length() == 0)
return null;
for (int i=res.length(); i<4; i++)
res.append("0");
return res.toString();
}
/** main */
public static void main(String[] args) {
String[] names = {
"Darwin, Ian",
"Davidson, Greg",
"Darwent, William",
"Derwin, Daemon"
};
for (int i = 0; i< names.length; i++)
System.out.println(Soundex.soundex(names[i]) + " " + names[i]);
}

}

</source>