Possible arrangement of characters in String

Hi All,

Let see how can we find all the possible arrangement of characters in String.

First we need to understand the basic concept how can we find all the arrangement. Consider if we have string "ABC" then how can we find the all possible arrangement.

We will trace the string backward from right to left (from 'C' to 'A')

1. get the Last char 'C'

2. get the second last char 'B' and try to place it before and after C. You will get the possible combination - "CB" and "BC"

3. Now take the 'A' and try find all the possible combination from "CB" and "BC". and You will get all the possible combination - ACB, CAB, CBA   and ABC,  BAC,  BCA.

now lets convert this concept in algorithm using Java Language.

import java.util.ArrayList;
import java.util.List;

public class perm
{
        static List<String> words = new ArrayList<String>();
        
 public static void main(String args[])
 {
  String str="XYZ";
                
  char c[] = str.toCharArray();
  
  for(int i=c.length-1; i > -1; i--)
                {
                    getPossibleCombination(c[i]);
                }
                                
                for(int i=0; i < words.size(); i ++)
                {
                    System.out.println(words.get(i));
                }                
 }

        public static void getPossibleCombination(char c)
        {
            String result;
            if(words.isEmpty())
            {
                words.add(String.valueOf(c));
            }
            else
            {     
                List<String> ll = new ArrayList<String>();
                for(String str : words)
                {
                    for(int i=0; i <= str.length(); i++)
                    {
                        result = charInsert(str, c, i);
                        if(ll.indexOf(result)==-1)
                        {
                            ll.add(result);   
                        }                        
                    }
                }
                words = ll;
                ll = null;
            }
        }
        
    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;
    }
}

Thats it.. when you will run this program we will get the output

Output :
XYZ
YXZ
YZX
XZY
ZXY
ZYX

Happy Knowledge sharing.. :)