Effectively generate all possible permutations of a linked list?

Question

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

Suppose, however, that the elements for the permutation are represented as a doubly linked list. In this case, you cannot accidentally access the items in the list during O (1) time, so many permutation algorithms will experience unnecessary slowdown.

Is there an algorithm for generating all possible permutations of a linked list with the maximum possible time and space costs?

Answer 1

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

You start from the rightmost number and move one position to the left until you see a number smaller than its neighbor. Then you put the number next in value there and order all the remaining numbers in ascending order after it. Do this while you have nothing more to do. Think about it, and you can order numbers in linear time relative to their number.

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

Answer 2

You might want to learn the Steinhaus-Johnson-Trotter algorithm. It generates all permutations of a sequence only by replacing adjacent elements; what you can do in O (1) in a doubly linked list.

Answer 3

You have to read the linked list data into an array that takes O(n) and then uses the heap permutation ( http://www.geekviewpoint.com/java/numbers/permutation ) to find all the permutations.

Answer 4

You can use the Factoradic Permutation Algorithm and rebuild the node pointers accordingly to generate the resulting permutation without recursion.

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`