December 17, 2016

Cljs Lexicographical Permutations

There's a few ways to solve Project Euler #24. One way is to figure out how to find the next lexicographical permutation of a list of digits.

If you're like me, then "Lexicographical Permuation" sounds scarier and more complex than it really is. Once you understand the terminology, it's really pretty easy.

At the end of this post, I have a live demo animation that shows how to find the next lexicographic permutation of any list of characters.

But first: if you're trying to solve Project Euler 24, stop reading now! Spoiler alert!

What the heck is a Lexicographic Permutation?

First: don't let the terms scare you.

"Lexicographical Order" is putting digits or characters in order from least to greatest. Easy, right?

A "permutation" is a rearrangement of digits or characters. For example, if you have digits 0, 1, and 2, you can rearrange them in 6 different ways.

Here are the 6 permutations of the digits 0, 1, and 2, ordered lexicographically:

0
1
2

0
2
1

1
0
2

1
2
0

2
0
1

2
1
0

How do you find the next permutation?

Now that we understand what a "Lexicographical Permutation" is, how do we find the next one?!

Before I go any further, I have to say, this post here gives a great explanation, and I borrowed some terminology from that post.

If you're given a list of things, how can you find the next lexicographical permutation?

For example, let's use "0123" as an example. In order to get the next biggest permutation, we need to keep the 0 and 1 in place, and switch the 2 and 3 at the end. That would give us "0132". There's no other permutation that is smaller than that and still larger than "0123", right?

So that's the basic idea: We need to try and keep the bigger digits to the right as much as possible.

Let's take that idea and come up with an algorithm. We'll start with "0132" this time:

0
1
3
2

Step 1

First, find the largest right most sequence of digits that are descending from left to right. In this case it's "3, 2". Let's call that the "suffix" and we'll mark all the digits in the suffix in dark blue. Let's call the digit just to the left the "pivot" and mark the pivot in green:

0
1
3
2

Step 2

Next we need to find the largest number in the suffix, starting from the right, that is greater than the pivot. In this example, it's the number "2". Let's mark this number in purple:

0
1
3
2

Step 3

Next step is to swap the purple and green numbers:

0
2
3
1

Step 4

And then the last step is to reverse all the numbers after the purple number. After that, we have our next lexicographical permutation of "0213"!

0
2
1
3

Pretty neat, right?!

Clojurescript Demo

I thought this was such a cool little algorithm that I created a demo to show it in action.

Here's a couple of notes about the implementation:

  • I used clojurescript, reagent, re-frame. Such an awesome stack.
  • I didn't think it was possible, but the re-frame developers just put out documentation that is even better than before! Even if you don't use re-frame, I definitely recommend anyone using reagent to read thru.
  • I think I understand how to use re-frame coeffects now. If you're interested, look into using reg-event-fx instead of reg-event-db.
  • I found this really nice react component library for animating listscalledreact-flip-move. Ihighly suggest you read thoughhis great articleabout how it works.
  • re-frame undo was so easy to wire up as well.

You can see the source code for the widget below here.

Demo

Enter any combination of characters. And then click the refresh button. Click play to sequence thru the lexicographical permutations.

Mesmerizing, isn't it?



Tags: clojure clojurescript