CODEWITHSUNDEEP
algorithmpermutation
user3711671
user3711671

Reputation: 853

Making algorithm for finding all possible permutations

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.

Upvotes: 1

Views: 556

Answers (3)

Joseph Fujimoto
Joseph Fujimoto

Reputation: 11

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.

https://www.geeksforgeeks.org/johnson-trotter-algorithm/

Upvotes: 1

Sam
Sam

Reputation: 104

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","");
    }
}

Upvotes: 0

samgak
samgak

Reputation: 24427

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

Upvotes: 1

Related Questions