Efficiently generating all possible permutations o

Question

There are many algorithms for generating all possible permutations of a given set of values. Typically, those values are represented as an array, which has O(1) random access.

Suppose, however, that the elements to permute are represented as a doubly-linked list. In this case, you cannot randomly access elements in the list in O(1) time, so many permutation algorithms will experience an unnecessary slowdown.

Is there an algorithm for generating all possible permutations of a linked list with as little time and space overhead as possible?

Answer 1

You might want to look into the Steinhaus–Johnson–Trotter algorithm. It generates all permutations of a sequence only by swapping adjacent elements; something which you can do in O(1) in a doubly linked list.

Answer 2

You should read the linked-list's data into an array, which takes O(n) and then use Heap's permutation ( http://www.geekviewpoint.com/java/numbers/permutation) to find all the permutations.

Answer 3

Try to think of how you generate all permutations on a piece of paper.

You start from the rightmost number and go one position to the left until you see a number that is smaller than its neighbour. Than you place there the number that is next in value, and order all the remaining numbers in increasing order after it. Do this until there is nothing more to do. Put a little thought in it and you can order the numbers in linear time with respect to their number.

This in fact is the typical algorithm used for next permutation as far as I know. I see no reason why this would be faster on array than on list.

Answer 4

You can use the Factoradic Permutation Algorithm, and rearrange the node pointers accordingly to generate the resulting permutation in place without recursion.

A pseudo description:

element_to_permute = list
temp_list = new empty list
for i = 1 in n! 
   indexes[] = factoradic(i)
   for j in indexes[]
      rearrange pointers of node `indexes[j]` of `element_to_permute` in `temp_list`