Permutation of String

Hey guys..I know Most of You Stuck with this Question...here i am posting a excellent so0lution fro problem hope this will help you ..lot..
A permutation, also called an “arrangement number” or “order,” is a rearrangement of the elements of an ordered list S into a one-to-one correspondence with S itself. A string of length n has n! permutation.
Explanation
Let’s assume a given string S represented by the letters A1, A2, A3, ..., An
To permute set S, we can select the first character, A1, permute the remainder of the string to get a new list. Then, with that new list, we can “push” A1 into each possible position.
For example, if our string is “abc”, we would do the following:
1. Let first = “a” and let remainder = “bc”
2. Let list = permute(bc) = {“bc”, “cd”}
3. Push “a” into each location of “bc” (--> “abc”, “bac”, “bca”) and “cb” (--> “acb”, “cab”, “cba”)
4. Return our new list

?

import java.util.*; class Permutation { public static ArrayList getPerms(String s) { ArrayList permutations = new ArrayList(); if (s == null) { // error case return null; } else if (s.length() == 0) { // base case permutations.add(""); return permutations; } char first = s.charAt(0); // get the first character String remainder = s.substring(1); // remove the first character ArrayList words = getPerms(remainder); for (String word : words) { for (int j = 0; j <= word.length(); j++) { permutations.add(insertCharAt(word, first, j)); } } return permutations; } public static String insertCharAt(String word, char c, int i) { String start = word.substring(0, i); String end = word.substring(i); System.out.println("start=" + start + "\t c=" + c + "\t end=" + end ); return start + c + end; } public static void main(String a[]) { ArrayList perm = new ArrayList(); perm=getPerms("abc"); //for(String ele:perm) //System.out.println(ele); } }

Compile: javac Permutation.java
Run: java Permutation
/*output analysis
start= c=c end=
start= c=b end=c
start=c c=b end=
start= c=a end=bc
start=b c=a end=c
start=bc c=a end=
start= c=a end=cb
start=c c=a end=b
start=cb c=a end=
*/



2nd Method

# include
# include

int printPermutations(char *str,int size, int pos)
{
int i;
int total=0;

if(pos==(size-1))
{
puts(str);
return 1;
}

total+=printPermutations(str,size,pos+1);
for(i=pos+1;i
{
int j;
for(j=pos;j
if(*(str+j)==*(str+i))
break;

if(j==i)
{
char tmp=*(str+pos);
*(str+pos)=*(str+i);
*(str+i)=tmp;

total+=printPermutations(str,size,pos+1);

tmp=*(str+pos);
*(str+pos)=*(str+i);
*(str+i)=tmp;
}
}

return total;
}

int main()
{
char str[]="aabc";
int size,total;



size=strlen(str);

printf("\n\nAll permutations of the input string are:\n");
total=printPermutations(str,size,0);

printf("\n\nThe total number of permutations of the given string is %d",total);


return 0;
}

Run here https://ideone.com/iXkV6

String Permutation Using  Iterative Appropach https://tropenhitze.wordpress.com/2010/01/25/steinhaus-johnson-trotter-permutation-algorithm-explained-and-implemented-in-java/