This is the third in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.

• Part 1: Counting Variations
• Part 2: Generating Variations
• Part 3: Go Implementation of Recursive Backtracking

This is the second in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.

• Part 1: Counting Variations
• Part 2: Generating Variations (you are here)
• Part 3: Go Implementation of Recursive Backtracking

Table of Contents

• Problem Description
• Permutations vs Combinations vs Variations
• Recursion
  • Recursive Backtracking Pseudocode
• Appying to DNA Variations
  • Generating Visits with Binary Numbers
  • Assembling the …

This is the first in a series of three blog posts describing our solution to a bioinformatics problem from Rosalind.info, Problem BA1(i) (Find most frequent words with mismatches in a string). To solve this problem and generate variations of a DNA string as required, we implemented a recursive backtracking method in the Go programming language.

• Part 1: Counting Variations (you are here)
• Part 2: Generating Variations
• Part 3: Go Implementation of Recursive Backtracking

Table of Contents

• Problem Description
• Useful Functions
  • Binomial Function
  • Factorial Function
• Counting Permutations
  • Deriving the Formula
  • Term 1: Picking DNA Indices
  • Term 1: Side Note …

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 …

This is Part 1 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.

You are currently reading Part 1 of this blog post: 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

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

Table of Contents

• Introduction: Why the Rubik's Cube

  • Why the 4x4 Rubik's Cube

• How the Rubik's Cube Works

  • The Pieces
  • Face Notation
  • Color 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 …

The Lattice Paths Problem

I first came across the lattice paths problem in Project Euler problem 15. The question described a 2x2 square lattice, and illustrated the 6 ways of navigating from the top left corner to the bottom right corner by taking the minimum number of steps - 2 right …