Find All the Well Ordered Permutations of a Given String.

Objective: Write an algorithm to Print All the Well Ordered Permutations of a Given String.

What is Well Ordered String: When all the alphabets in a string occur in the increasing order irrespective of Lower Case or Upper case.

http://www.careercup.com/question?id=6206517812396032

Example :

"Sumit" - Not Well Ordered . 'u' occurred after 'S'.

"Now" - Well Ordered. N<o<W.

Input: Interview
Output: 
[e, e, I, i, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, I, i, n, r, t, v, w]

Approach:

Code:


import java.util.Arrays;
public class WellFormedStrings {
// Logic:
// 1. Get the input sequence
// 2. Find out all the permutations of a String
// 3. Before printing if the permutation is well formed.
char[] A;
public void wellFormedString(String S) {
A = S.toCharArray();
permutation(A, 0);
}
public void permutation(char[] A, int left) {
if (left == A.length) {
if (isWellFormed(A)) {
System.out.println(Arrays.toString(A));
}
return;
}
for (int i = left; i < A.length; i++) {
swap(i, left);
permutation(A, left + 1);
swap(i, left); // backtrack
}
}
public void swap(int a, int b) {
char temp = A[a];
A[a] = A[b];
A[b] = temp;
}
public boolean isWellFormed(char[] A) {
boolean wellFormed = true;
for (int i = 0; i < A.length 1; i++) {
if (Character.toLowerCase(A[i]) > Character.toLowerCase(A[i + 1])) {
wellFormed = false;
break;
}
}
return wellFormed;
}
public static void main(String[] args) {
String S = "Interview";
System.out.println("Given String – " + S);
WellFormedStrings i = new WellFormedStrings();
i.wellFormedString(S);
}
}


Output:

Given String - Interview
[e, e, I, i, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, i, I, n, r, t, v, w]
[e, e, I, i, n, r, t, v, w]

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.