Tag: combinatorics


Recursive Backtracking in Go for Bioinformatics Applications: 3. Go Implementation of Backtracking

Posted in Rosalind

permalink

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.



Table of Contents



Tags:    go    golang    rosalind    bioinformatics    recursion    backtracking    strings    combinatorics   


Recursive Backtracking in Go for Bioinformatics Applications: 2. Generating Variations

Posted in Rosalind

permalink

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.



Table of Contents



Tags:    go    golang    rosalind    bioinformatics    recursion    backtracking    strings    combinatorics   


Recursive Backtracking in Go for Bioinformatics Applications: 1. Counting Variations

Posted in Rosalind

permalink

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.



Table of Contents



Tags:    go    golang    rosalind    bioinformatics    recursion    backtracking    strings    combinatorics   


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   


4x4 Rubik's Cube: Part 1: Representations

Posted in Rubiks Cube

permalink

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



Tags:    rubiks cube    mathematics    combinatorics    permutations    python    puzzles   


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 …




Shortest Lattice Paths and Multiset Permutations

Posted in Mathematics

permalink

Table of Contents

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 …