I found out that permutations for 3 elements can be found easily by simply swapping last element with a middle element, and then the middle element by a first element and then repeat this until you find all permutations. I tried to apply this when there are more than 3 elements but it doesn't work (for n = 4 i found only 12 permutations), is it possible to make it work?I know there's an algorithm made by Steinhaus - Johnson - Trotter which might probably be what I'm talking about but I couldn't find a good explanation of their algorithm.By the way I don't need (pseudo)code of permutations algorithm.
3 Answers
Thinking about it recursively, if you have a set of n elements, then to generate all the possible permutations, put each of the n elements in the first position, and then generate all of the possible permutations of the remaining elements and add concatenate with the first element.
An easy way to implement this is to define a functuon that swaps the first element with each of the elements in the set in turn (including itself) then recursively calls itself to generate each of the possible permutations of the remaining elements, and then swaps the elements back after returning (backtracking). It's hard to go into more detail because you said you don't want pseudo-code.
This assumes no duplicate elements.
Worked example:
Generate permutations of (1, 2, 3):
Put each element as the first element and then generate all permutations of remaining elements:
0 + permutations of (1, 2)
Put each element as the first element and then generate all permutations of remaining elements:
0 + 1 + permutations of (2)
Put each element as the first element and then generate all permutations of remaining elements:
0 + 1 + 2
0 + 2 + permutations of (1)
Put each element as the first element and then generate all permutations of remaining elements:
0 + 2 + 1
1 + permutations of (0, 2)
Put each element as the first element and then generate all permutations of remaining elements:
1 + 0 + permutations of (2)
Put each element as the first element and then generate all permutations of remaining elements:
1 + 0 + 2
1 + 2 + permutations of (0)
Put each element as the first element and then generate all permutations of remaining elements:
1 + 2 + 0
2 + permutations of (0, 1)
Put each element as the first element and then generate all permutations of remaining elements:
2 + 0 + permutations of (1)
Put each element as the first element and then generate all permutations of remaining elements:
2 + 0 + 1
2 + 1 + permutations of (0)
Put each element as the first element and then generate all permutations of remaining elements:
2 + 1 + 0
4 Comments
user3711671
So swap first element in each position and then generate permutations of remaining elements?So how am I supposed to generate permutations of remaining elements?
samgak
That's the beauty of recursion. Generating the permutations of the remaining elements works the same way: select each element as the element in the first position and then generate the permutations of all the remaining elements etc. Until you get to generating the permutations of a list of one element, in which case there is just a single permutation: the element itself. If this doesn't make sense it's better to try working this out with a pen and paper so you can see how it works rather than asking for more intuitive explanations, because recursion is not necessarily intuitive.
user3711671
Well I did something like that before (swap first element with another element, then put the swapped element between every element in that permutation, repeat) but I didn't like it because swapping elements from left to right (or right to left) is much easier and I also want to find out how to make my method work for n>3 (and steinhaus' algorithm does this).
samgak
You need to revise your question in that case. Are you specifically asking for how to implement the Steinhaus–Johnson–Trotter algorithm? Because your question doesn't make that clear, it just mentions it as a possibility.
The Johnson Trotter algorithm is one with a lot of steps when it is being implemented, and also a slow one with a factorial Big-O notation. geeksforgeeks.com has a good example of implementing this, where entering a number will get you all premutations starting with 1.
1 Comment
yacc
Please add relevant code to your answer instead of linking to external sites.
Implementing @samgak algorithm in java code
/**
* Created by Balachandar on 21-01-2017.
*/
public class Permutation {
public static void permutation(String input, String ans)
{
if(input.isEmpty()){
System.out.println(ans);
}
else {
for (int i = 0; i < input.length(); i++) {
permutation( input.substring(0, i) + input.substring(i + 1, input.length()),ans + input.charAt(i));
}
}
}
public static void main(String[] args)
{
permutation("abcd","");
}
}
i-1. Then,Yiis defined asXi-1orXi+1depending on some properties of the permutation. Anyway, note that Wikipedia has not only the description of algorithm steps, but the whole explanation what is it trying to achieve.