Algorithms

Importunate Permutations

John Sonmez · Nov 24, 2009 · 1 min read

As an Amazon Associate I earn from qualifying purchases.

Here is an interesting programming problem: Calculate all the permutations of a string.

For example, the permutations of “abc” are:

abc

acb

bac

bca

cab

cba

It is not as easy of a problem as it seems, but it has a rather simple solution.

Many times recursion is actually more complex to understand than a non-recursive solution, but in this case recursion is an elegant and simple solution.

A good way to solve these kinds of problems is to start with N, N+1, N+2, then solve for N+x.

Let’s start with N; we will define a function permutation which will give us the permutations of any string.

permutation(“a”) =

“a”

permutation(“ab”) =

“a” + permutation(“b”)

“b” + permutation(“a”)

permutation(“abc”) =

“a” + permutation(“bc”)

“b” + permutation(“ac”)

“c” + permutation(“ab”)

permutation(x)

foreach character c in x

c + permutation(x remove c)

Looking at it in C# code, it would look something like:

Update: Here is a pretty slick example in LINQ that I got from a stackoverflow.com question.

For a better understanding of permutations, check out this short booklet on How to Understand Permutations and Computations .

When You're Ready

Keep Learning. Build a Career Next.

Right now, focus on getting the basics down. When you're ready to turn those skills into a real developer career, RDU gives you a clear plan and coaching from John.

Learn About RDU →
John Sonmez

John Sonmez

John Sonmez is the founder of Simple Programmer, author of "The Complete Software Developer's Career Guide" and "Soft Skills: The Software Developer's Life Manual." He helps software developers build remarkable careers.

The developers who get the best offers are the ones people already know.The best offers go to developers people already know. Get a free YouTube channel plan built from your stackFree YouTube channel plan →