Yan Cui
I help clients go faster for less using serverless technologies.
This article is brought to you by
Save money on RDS by moving your dev environments to Neon serverless Postgres, with instant scaling, scaling to zero (and only 500ms cold start!), and the ability to branch your database as easily as creating a Git branch.
Problem
A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | let rec distribute e = function | [] -> [[e]] | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]let rec permute = function | [] -> [[]] | e::xs -> List.collect (distribute e) (permute xs)let getLexicographic (list:bigint list) = list |> permute |> List.map (fun l -> l |> List.rev |> List.mapi (fun i e -> e * pown 10I i) |> List.sum) |> List.sortlet answer = List.nth (getLexicographic [0I..9I]) (1000000-1) |
I borrowed the first two functions which are responsible for generating all the permutations of a given list here. From there, I wrote the getLexicographic function which takes an int list, generates all permutations of the numbers in the list, and for each permutation work out its numeric value, i.e.
[0; 1; 2] –> [2; 1; 0] –> 2 * (10 POW 0) + 1 * (10 POW 1) + 0 * (10 POW 2) –> 2 + 10 + 0 –> 12
and then returns the sorted numeric values as a list.
To get to the answer, I simply return the millionth element in the list.
Whenever you’re ready, here are 3 ways I can help you:
- Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
- I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.