Carl's Hacking Notes

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Permutations ======

A list of elements has ''n!'' Permutations.  There are a few ways to try out every permutation.


===== Iterating All Permutations =====

==== Mutable List ====

To iterate through all ''n!'' permutations of a list of elements, consider the following 

''[A, B, C, D, E]''

There are ''n'' possible elements to choose from, so remove the ''i''th one, where ''0 <= i < n''.  Let's say it's element 1: ''C'':


''[A, B, _, D, E]''

Next, remove the final element from the list, and place it at position 1:


''[A, B, E, D]''


Continue this process of removing any element, and moving the final element into its place.  This keeps the list dense, and it efficient to do with an array-like list.    Each time, the list shrinks by 1.  We can see the number of choices for elements to remove is ''n'' at each step, with ''n'' shrinking by 1 each time.   Thus the number of ways to remove all the elements is:

''n * (n-1) * (n-2) ... (1) = n!''

Thus, we are confident that the number of ways to remove elements and the number of permutations are both ''n!''.

== Analysis ==

Since we destroy the list in the process of iterating it, we need to make a copy of it. Usually it's the case that we need to iterating through the list again, so a fresh copy is needed each time.   Note that it is possible to 'undo' the operations by repeatedly placing the element back in the previous spot, and moving the exist element to the end.  This assume the list hasn't shrunk in capacity in the mean time,  Both making a copy of the list, and undoing the iteration are ''O(n)''.  

Removing a single element is ''O(1)'' which we do 'n' times, so iteration is linear in time.


===== Encoding a Permutation =====

A simple way to encode a permutation is to store a list of the elements removed.  This is impractical, as it may not be possible to encode the elements.  An alternative would be to store the indexes of the elements, assuming the replacement strategy described above.   

For example, assume we have the same list as above:

''[A, B C, D, E]''

Let's remove element at ''i = 2''.:

''[A, B, _, D, E] => [A, B, E, D]''

Next let's remove at ''i = 1'':

''[A, _, E, D] => [A, D, E]''

Next, at ''i= 2''

''[A, D, _] => [A, D]''

Next at ''i = 0''

''[_, D] => [D]''

And finally, there is only one element to remove at ''i = 0''

Our iteration order is thus: ''[2, 1, 2, 0, 0]''.

Notice that at each removal, the maximum size of each later index is decreased by 1.   The final index will always be 0.   This can be encoded densely as a [[https://en.wikipedia.org/wiki/Factorial_number_system|Factoradix]] number.