Tag: knuth


Five Letter Words: Part 5: The Try Trie Tree

Posted in Computer Science

permalink

Tags:    python    computer science    graphs    algorithms    art of computer programming    knuth    five letter words    tries    trees   


Five Letter Words: Part 4: Revisiting Diff by One

Posted in Computer Science

permalink

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 …




4x4 Rubik's Cube: Part 4: Sequence Order

Posted in Rubiks Cube

permalink

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



Tags:    rubiks cube    combinatorics    permutations    python    puzzles    art of computer programming    knuth   


4x4 Rubik's Cube: Part 3: Factoring Permutations

Posted in Rubiks Cube

permalink

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



Tags:    rubiks cube    combinatorics    permutations    python    puzzles    art of computer programming    knuth   


4x4 Rubik's Cube: Part 2: Permutations

Posted in Rubiks Cube

permalink

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



Tags:    rubiks cube    combinatorics    permutations    python    puzzles    art of computer programming    knuth   


Let's Generate Permutations!

Posted in Computer Science

permalink

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 …




Five Letter Words: Part 3: Letter Coverage and Dynamic Programming

Posted in Computer Science

permalink

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

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




Five Letter Words: Part 2: More Five-Word Algorithms

Posted in Computer Science

permalink

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




Five Letter Words: Part 1: Getting Familiar With The List

Posted in Computer Science

permalink

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 …