Someone asks you to generate all the perumtations from a set of objects and you might think that this is an easy problem And it isn’t that challenging but I had to think about it for a bit to come up with away to do this. I thought it would be fun to code this up in F# to see if my algorithm was correct and to learn about the language a bit more.
The algorithm I came up with is essentially a depth first search like approach. Taking the first element and printing it and then moving it to the ancestor list and printing it with the next one and so on. This will print the permutations in lexicographic order providing the input elements are sorted. Here is the source code below.
#light
/// List printing function need a generic version
let ListPrinter format a n =
printf "%A. " n
a|> List.iter (fun x -> (printf format x))
printf "\n"
/// Print all the permutation of a list of elements
/// Algorithm Pseudo Code
/// PermutationGenerator(list items)
/// PermuationHelper([], items)
/// end
///
/// PermutationHelper(list ancestors, list descendants)
/// if descandants is null return
/// foreach descendant
/// newAncestors = ancestors + descendant
/// print(newAncestors)
/// newDescandants = descendants - descendant
/// PernumationHelper(newAncestors, newDescandants)
/// end
/// end
let PermutationGenerator printer items =
///internal counter function
let counter =
let count = ref 0I
fun () -> count.contents <- count.contents + 1I; !count
/// Helper recursive function that does the work
let rec PermutationHelper ancestors descendants =
if ancestors <> [] then printer ancestors (counter())
match descendants with
| [] -> ()
| y::ys -> let fn = (fun (front, back : 'a list) curr ->
let newFront = front @ [curr]
let newBack = back.Tail
let newAncestors = ancestors @ [curr]
let newDescendants = front @ newBack
PermutationHelper newAncestors newDescendants
(newFront, newBack))
in List.fold_left fn ([],descendants) descendants |> ignore
// call the nested function
PermutationHelper [] items
let items = ["apple";"banana"; "canteloupe";]
//"cherry"; "grape";"orange";
//"peach";"pear"; "strawberry"]
let numbers = [ 1..5 ]
let chars = ['a'..'e']
let StringPrinter = ListPrinter "%s "
let NumericPrinter = ListPrinter "%d"
let CharPrinter = ListPrinter "%c"
let StringPermutations = PermutationGenerator StringPrinter
let NumericPermutations = PermutationGenerator NumericPrinter
let CharPermutations = PermutationGenerator CharPrinter
You can load the above into the F# interactive window and run the following command and see the following results.
> StringPermutations items;;
1I. apple
2I. apple banana
3I. apple banana canteloupe
4I. apple canteloupe
5I. apple canteloupe banana
6I. banana
7I. banana apple
8I. banana apple canteloupe
9I. banana canteloupe
10I. banana canteloupe apple
11I. canteloupe
12I. canteloupe apple
13I. canteloupe apple banana
14I. canteloupe banana
15I. canteloupe banana apple
Some of the more interesting parts as someone learning functional programming include the use of curried functions, the fold operator, and pattern matching.
PermutationGenerator is a generic function that can work with any list of items of type a’ list as long as a corresponding printer for the items is supplied of type a’ list -> bigint -> unit. The basic algorithm is listed above PermutationGeneration in the comments. Although, F# supports loops the functional way to iterate over elements is to use a function like map or fold, so the foreach loop is replaced by List.fold_left with fn essentially being the body of the loop.
I then build a ListPrinter function that takes a format string. From this I create printers for three different types using partial application or currying, StringPrinter, NumericPrinter, and CharPrinter. This allows the creation of three new more specialized functions from the ListPrinter. Currying is also used to create three specific Permutation Generators, StringPermutations, NumericPermutations, CharPermutations from PermutationGenerator by applying the particular printer.
There are other techniques for generating permutations. Some involve shuffling of positions of elements after selecting the number of items. Another technique is to use factoradics which give a way to select elements or permutations based on the factorial number system.
