Changing and Re-Arranging

Any time I go to a wedding or some kind of family gathering where we take a lot of pictures, it can seem like it goes on for a while. It seems like we have to take a picture with every different combination of people in it. Imagine how much worse it would be if we needed the also get every different ordering (or permutation) of people as well!

Even if it got to that level, it would still be easy to write a Haskell program to handle this problem! There are a couple specific list functions we can use. The "subsequences" function will give us the list of every subsequence of the input list.

subsequences :: [a] -> [[a]]

This would be helpful if all we want to know is the different combinations of people we would get in the pictures.

>> subsequences ["Christina", "Andrew", "Katharine"]
[[], ["Christina"], ["Andrew"], ["Christina", "Andrew"], ["Katharine"], ["Christina", "Katharine"], ["Andrew", "Katharine"], ["Christina", "Andrew", "Katharine"]]

Note a couple things. First, our result includes the empty sequence! Second of all, the order of the names is always the same. Christina is always before Andrew, who is always before Katharine.

Now let's suppose we have a different problem. We want everyone in the picture, but we can order them anyway we want. How would we do that? The answer is with the "permutations" function.

permutations :: [a] -> [[a]]

This will give us every different ordering of our three people.

>> permutations ["Christina", "Andrew", "Katharine"]
[["Christina", "Andrew", "Katharine"], ["Andrew", "Christina", "Katharine"], ["Katharine", "Andrew", "Christina"], ["Andrew", "Katharine", "Christina"], ["Katharine", "Christina", "Andrew"], ["Christina", "Katharine", "Andrew"]]

Be wary though! These functions are mostly useful with small input lists. The number of subsequences of a list grows exponentially. With permutations, it grows with the factorial! By the time you get up to 10, you're already dealing with over 3 million possible permutations!

>> length (subsequences [1, 2, 3, 4])
16
>> length (subsequences [1, 2, 3, 4, 5])
32
>> length (subsequences [1, 2, 3, 4, 5, 6])
64
>> length (permutations [1, 2, 3, 4])
24
>> length (permutations [1, 2, 3, 4, 5])
120
>> length (permutations [1, 2, 3, 4, 5, 6])
720

If such cases are really necessary for you to handle, you might need to take advantage of Haskell's laziness and treat the result similar to an infinite list, as we'll cover later this month.

If you want to keep learning about random interesting functions, you should subscribe to Monday Morning Haskell! You'll get access to all our subscriber resources, including our Beginners Checklist.