import java.util.SortedSet ;
import java.util.TreeSet ;
import java.util.Scanner ;
import java.util.Arrays ;

/**
 *
 * @author Ashu
 * Recursive method to find all permutations of a String without any duplicates
 *   (if exists).
 */
public final class PermutationRecursive
{
    private SortedSet <String> set = new TreeSet <String> () ;

    private void permuteString(String begStr, String endStr)
    {
        int length = endStr.length() ;
        if (length == 1) set.add(begStr + endStr) ;
        else
        {
            for (int i = 0 ; i < length ; i++)
            {
                String newStr = endStr.substring(0, i) + endStr.substring(i+1) ;
                permuteString(begStr + endStr.charAt(i), newStr) ;
            }
        }
    }

    private void print(SortedSet <String> list)
    {
        int k = 0 ;
        for (String str : list)
        {
            System.out.println(++k + " --> " + str) ;
        }
        System.out.println("Frequency of Permutations : " + k) ;
    }

    private void search(SortedSet <String> list, String sch)
    {
        int loc = Arrays.binarySearch(list.toArray(), sch) + 1 ;
        System.out.println("String Found At :: " + loc) ;
    }

    public static void main(String[] args)
    {
        PermutationRecursive pR = new PermutationRecursive() ;
        Scanner scan = new Scanner(System.in) ;

        System.out.print("Enter a String :: ") ;
        String str = scan.nextLine() ;

        pR.permuteString("", str) ;
        pR.print(pR.set) ;

        System.out.print("Enter the String to be searched :: ") ;
        String input = scan.nextLine() ;
        scan.close() ;
        pR.search(pR.set, input) ;
    }
}