CareerCup

public class StringCombination {

	char[] array;
	boolean[] visited;
	String text = "abc";
	
	public static void main(String[] args) {
		StringCombination st= new StringCombination();
		st.printCombination("");
	}
	
	public StringCombination()
	{
		array = this.text.toCharArray();
		visited = new boolean[array.length];
	}
	
	
	public void printCombination(String val)
	{
		if(val != null && val.length()>0)
		{
			System.out.println(val);
		}
		
		for(int x = 0; x < text.length() ; x++)
		{
			if(visited[x] == false)
			{
				visited[x] = true;
				String val2 = text.charAt(x) + "";
				printCombination(val+val2);
				visited[x] = false;				
			}
		}		
	}
	
}

Let's assume the string to be "abcde.....". Now looking at the possibilities (of all possible lengths) :-
a, b, c, d, e, ...... --- single letters
ab, ac, ad,........, ba, bc, bd....., ca, cb,cd,..... --- dual letters
abc, abd, abe,..... acb, acd, ace, .... --- three letters
and so on...

The concept in generating these sequences is that, when you consider all the single letters, store them in a array, [a,b,c,d,....]
while you are forming dual letter sequences, take a letter and pair up with all other letters in the array, ex. if I consider 'a', I take 'a' out of array and form ab, ac, ad....
Similarly, when you are considering 3 letter sequences, take the two letters for consideration and pair up with all others, i.e, while considering "ab", my array under consideration will be [c,d,e,f,....](a, b removed from single letter arrya) and so we get abc, abd, abe.......
similarly repeat the procedure for "ac"(a,c removed from dual letter array) with array [b, d, e, f....] and the rest.
Following this process, you can get a bunch of required sequences and carefully designing algo can lead to a dictionary order by default !!!

That's my guess!! Hopefully correct.

This is a power set problem. Find power set of character in a string.

Power set generation is just a part of it, as we need to find permutation of the Strings as well. Power set will give us only the combination of the Strings

import java.util.ArrayList;

public class Permutation {
public static void main(String args[]){
// ArrayList<Character> set = new ArrayList<Character> ();
// set.add('a');
// set.add('b');
// set.add('c');
// helper(set,"",3);
permutations("abcd");
}
// time: n+n*(n-1)+n*(n-1)*(n-2)+...+n! = O(n!)
public static void permutations(String str) {
ArrayList<Character> set = new ArrayList<Character> ();
for(int i=0;i<str.length();i++)
set.add(str.charAt(i));
int i=1;
while (i <= str.length()) {
helper(set,"",i);
i++;
}
}

public static void helper(ArrayList<Character> set, String str, int m) {
if (m == 0) {
System.out.println(str);
}
for (int i = 0; i < set.size(); i++) {
Character c = set.get(i);
ArrayList<Character> newSet = (ArrayList<Character>) set.clone();
newSet.remove(c);
helper(newSet, str + c, m - 1);
}

}

}

import java.util.ArrayList;

public class Permutation {
	public static void main(String args[]){
//		ArrayList<Character> set = new ArrayList<Character> ();
//		set.add('a');
//		set.add('b');
//		set.add('c');
//		helper(set,"",3);
		permutations("abcd");
	}
// time: n+n*(n-1)+n*(n-1)*(n-2)+...+n! = O(n!)
	public static void permutations(String str) {
		ArrayList<Character> set = new ArrayList<Character> ();
		for(int i=0;i<str.length();i++)
			set.add(str.charAt(i));
		int i=1;
		while (i <= str.length()) {
			helper(set,"",i);
			i++;
		}
	}

	public static void helper(ArrayList<Character> set, String str, int m) {
		if (m == 0) {
			System.out.println(str);
		}
		for (int i = 0; i < set.size(); i++) {
			Character c = set.get(i);
			ArrayList<Character> newSet = (ArrayList<Character>) set.clone();
			newSet.remove(c);
			helper(newSet, str + c, m - 1);
		}

	}

}

package com.interviews.salesforce;

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

/**
 * Given a string generate permutations of all possible lengths and print them
 * in any order !
 * Now print the permutations in dictionary order.
 *
 * @author Kailas Kore
 */
public class StringPermutation {

    private static List<String> permutations;
    private static char[] chars;

    private static int possiblePermutations(int n, int l) {
        int result = n;
        for (int i = 1; i < l; i++) {
            result = result * (n - i);
        }
        return result;
    }

    private static void printPermutations(int n, int l) {
        int possiblePermutations = possiblePermutations(n, l);
        System.out.println("length: " + l + " Possible Permutations: " + possiblePermutations);
        if (permutations == null) {
            permutations = new ArrayList<>(possiblePermutations);
            for (char c : chars) {
                permutations.add("" + c);
                System.out.print(c + " ");
            }
        } else {
            List<String> fixed = new ArrayList<>(permutations);
            permutations = new ArrayList<>(possiblePermutations);
            for (String str : fixed) {
                for (char c : chars) {
                    if (str.indexOf(c) == -1) {
                        permutations.add(str + c);
                        System.out.print(str + c + " ");
                    }
                }
            }
        }
        System.out.println();
    }

    private static void permute(String input) {
        int n = input.length();
        if (n <= 1) {
            System.out.println(input);
        } else {
            chars = input.toCharArray();
            for (int l = 1; l <= n; l++) {
                printPermutations(n, l);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println("Please input your string and hit ENTER :");
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        permute(input.trim());
    }

}