Pages

▼

Friday, September 18, 2015

String permutation

A permutation, also called an "arrangement number" or "order," is a rearrangement of the elements of an ordered list into a one-to-one correspondence with itself


Algorithm
To get all the permutations, we will first take out the first char from String and permute the remaining chars.

If String = “ABC”
First char = A and remaining chars permutations are BC and CB.

Now we can insert first char in the available positions in the permutations.
BC -> ABC, BAC, BCA
CB -> ACB, CAB, CBA

So we can write a recursive function call to return the permutations and then another function call to insert the first characters to get the complete list of permutations.



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
public class Permutations {
    public static Set<String> permutationFinder(String str) {
        Set<String> perm = new HashSet<String>();
        
        //whitespaces
        if (str.length() == 0) {
            perm.add("");
            return perm;
        }
        
        char initial = str.charAt(0); // first character
        String rem = str.substring(1); // Full string without first character
        Set<String> words = permutationFinder(rem);
        for (String strNew : words) {
            for (int i = 0;i<=strNew.length();i++){
                perm.add(charInsert(strNew, initial, i));
            }
        }
        return perm;
    }
 
    public static String charInsert(String str, char c, int j) {
        String begin = str.substring(0, j);
        String end = str.substring(j);
        return begin + c + end;
    }
 
    public static void main(String[] args) {
        String s = "1234";
        System.out.println("\nPermutations for " + s + " are: \n" + permutationFinder(s));
    }
}
at

No comments:

Post a Comment