No Description

Charles Reid 6f3da0a366 updating final print statement in both letter coverages 4 weeks ago
output d2ad99bfb6 Add near palindrome output, and fix palindrome pairs to exclude palindromes 1 month ago
.gitignore 587a24094c adding memo to gitignore. 2 months ago
LICENSE d98c093f1a updating license, readme, and adding words. 2 months ago
README.md ef62283c91 update readme with new scripts. 1 month ago
diff_by_n.py 3963e6a40a updating diff by n to print, for n equals 2 through 2 1 month ago
diff_by_one.py 563a8799b0 updating diff-by-one script comment 1 month ago
distinct.py 4dd57760fa Make distinct.py more efficient: one loop over words. 1 month ago
euclidean_distance.py 26b5f9394d reverse order of printed distances 1 month ago
get_words.py b16c360103 adding get words function. 2 months ago
letter_coverage.py 6f3da0a366 updating final print statement in both letter coverages 4 weeks ago
letter_coverage_dbg.py 6f3da0a366 updating final print statement in both letter coverages 4 weeks ago
lexico.py 5ea6a87e46 fix comments. 1 month ago
near_palindromes.py d2ad99bfb6 Add near palindrome output, and fix palindrome pairs to exclude palindromes 1 month ago
palindromes.py d2ad99bfb6 Add near palindrome output, and fix palindrome pairs to exclude palindromes 1 month ago
reverse_lexico.py 5ea6a87e46 fix comments. 1 month ago
sgb-words.txt bd17061751 Adding Stanford GraphBase list of five-letter words 2 months ago
stats.py c902691810 remove particular bigrams 2 months ago

README.md

five-letter-words

This repository contains Donald Knuth's GraphBase list of five-letter words, as well as scripts to run various combinatoric experiments, graph algorithms, and other algorithms to explore the relationships among these words.

The list of words comes from [1] and is in the public domain.

Get Words

A Python program that contains a method for getting all of the five letter words from a file, and that's about it.

Warm Up Exercises

Exercises 26-37 of Knuth's Volume 4 Fascile 0 are intended as a warm up to get to know the SGB five letter word list. Solutions to these exercises are listed below.

distinct.py- computes the number of SGB words containing exactly k distinct letters.

diff_by_one.py - computes the number of words in the SGB that are off by a single letter, shifted a single place. For example, "might" and "night" or "large" and "marge". There is a surprisingly large number of such pairs.

euclidean_distance.py - computes the euclidean distance between two words. This uses the traditional Euclidean distance definition but reinterprets distance to mean edit distance.

lexico.py - find words that are sorted by lexicographic order (front to back, a-z).

palindromes.py - look for five letter words that are either a palindrome, or a palindrome pair.

Variations

diff_by_n.py - computes words in SGB that have an edit distnace of n.

reverse_lexico.py - variation on lexico.py that finds words whose letters are in reverse lexicographic order.

Letter Coverage

letter_coverage.py - computes coverage of the alphabet (minimum number of words required to provide X letters of the alphabet)

Knuth mentions, in the text, a couple of facts about how many words cover how much of the alphabet. We authored a dynamic program to compute precisely this - given a number of letters N from the alphabet, this program computes the minimum number of words it takes to cover all N letters.

Also see https://charlesreid1.com/wiki/Letter_Coverage..

Sources

  1. Knuth, Donald. The Stanford GraphBase: A Platform for Combinatorial Computing. New York: ACM Press, 1994. <http://www-cs-faculty.stanford.edu/~knuth/sgb.html>