About the Five-Letter Words

In Volume 4 Fascicle 0 of Donald Knuth's Art of Computer Programming, Knuth introduces a tool for exploring concepts in graph theory: the five-letter words. This is a collection …

About the Five-Letter Words

In Volume 4, Facsimile 0 of Donald Knuth's Art of Computer Programming, in which Knuth covers graph theory, he introduces a list of five-letter words as part of a data set useful in exploring graph theory and graph algorithms.

The list of words is part of the Stanford Graph Base, a set of data sets that are useful for studying graph theory and networks.

See Five Letter Words on the charlesreid1.com wiki for details.

Different by 1, Revisited

This post …

This is Part 4 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

See Part 3 of this blog post here: Part 3: Factoring Permutations

You are currently reading Part 4 of this blog post: Part 4: Sequence Order

Table of Contents

• Introduction

  • Order of a Sequence
  • What We Have Covered So Far

• Factoring Rubik's Cube Permutations

  • Factoring Permutations: A Review
  • Factoring Rubik's …

This is Part 3 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

See Part 2 of this blog post here: Part 2: Permutations

You are currently reading Part 3 of this blog post: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

Table of Contents

• Introduction: Cycles, Sequences, and Order

  • Cycles
  • Sequences
  • Order

• Intercalation Product

  • Definition
  • Properties

• Factoring Permutations Using Knuth's Theorem A

  • Significance of Factors …

This is Part 2 of a 4-part blog post on the mathematics of the 4x4 Rubik's Cube, its relation to algorithms, and some curious properties of Rubik's Cubes.

See Part 1 of this blog post here: Part 1: Representations

You are currently reading Part 2 of this blog post: Part 2: Permutations

See Part 3 of this blog post here: Part 3: Factoring Permutations

See Part 4 of this blog post here: Part 4: Sequence Order

Table of Contents

• Introduction: Sequences and Permutations

• Representing Permutations: Two-Row Notation

  • Two-Row Notation
  • Two-Row Notation for Rubik's Cube

• Sequences

  • Review of Move/Sequence Notation …

Generating Permutations

In today's post we're going to discuss the generation of permutations.

Often, in combinatorics problems, we are interested in how many different instances or configurations of a particular thing we can have (what we'll call "enumeration" or "counting"). However, that is different from wanting to actually see all of those configurations. Indeed, if we are counting something with an astronomical number of configurations, we don't want to try to list all of them.

However, as usual, Donald Knuth, who covers the topic of permutation generation in Volume 4A of his classic work, The Art of Computer Programming, uncovers …

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

Table of Contents

• Introduction
• A Simple Manual Exmaple
• Pseudocode
• Python Code
• Output and Timing

Introduction

The letter/word coverage problem, as presented by Donald Knuth in Volume 4, Facicle 0 of his masterpiece Art of …

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

Table of Contents

• Introduction
• Five-Letter Words with k Distinct Letters
  • Examining a Variation
• Lexicographic Ordering of Letters
  • Five-Letter Words with Lexicographically Ordered Letters
  • Five-Letter Words with Lexicographically Reversed Letters
• Finding Palindromes
  • Palindromes
  • Palindrome Pairs
  • Near …

NOTE: The code covered in this post uses Python 3. The scripts can be converted to Python 2 with minimal effort, but the author would encourage any user of Python 2 to "put on your big kid pants" and make the switch to Python 3. Let's all make this painful, drawn-out switch from Python 2 to Python 3 a thing of the past, shall we?

Table of Contents

• About the Five Letter Words
• The Usefulness of Five Letter Words
• Warm-Up Exercises
• Get Words Function
• Euclidean Distance
  • Euclidean Distance Code
  • Examples
  • Different-by-N Code
• Mo Words, Mo Problems
• References

About the Five-Letter …