How to generating permutations of elements of different sizes

Question

I have as input a group of elements, let's assume they are strings:

String[] elements = {"A","B","C","D"};

I would like to generate all permutations of size 1, 2 and 3 ( until n-1) elements, without duplicating any element.

So the output will look exactly like this:

A
B
C
D
AB
AC
AD
BC
BD
CD
ABC
ABD
ACD
BCD

The current code I have generate all permutations, but with duplicates :(

public static String[] getAllLists(String[] elements, int lengthOfList)
    {
        //initialize our returned list with the number of elements calculated above
        String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

        //lists of length 1 are just the original elements
        if(lengthOfList == 1) 
            return elements; 
        else 
        {
            //the recursion--get all lists of length 3, length 2, all the way up to 1
            String[] allSublists = getAllLists(elements, lengthOfList - 1);

            //append the sublists to each element
            int arrayIndex = 0;

            for(int i = 0; i < elements.length; i++)
            {
                for(int j = 0; j < allSublists.length; j++)
                {
                    //add the newly appended combination to the list
                    allLists[arrayIndex] = elements[i] + allSublists[j];
                    arrayIndex++;

                }
            }
            return allLists;
        }
    }

public static void main()
{
String[] elements = {"A","B","C","D"};
        for(int i=1; i<=elements.length; i++)
        {
            String[] result = getAllLists(elements, i);
            for(int j=0; j<result.length; j++)
            {
                System.out.println(result[j]);
            }
        }
}

Answer 1

I changed your code bit. Try this.

public static String[] getAllLists(String[] elements, int lengthOfList) {

    Set<String> result = new HashSet<String>();

    //lists of length 1 are just the original elements
    if(lengthOfList == 1)
        return elements;
    else
    {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);

        for(int i = 0; i < elements.length; i++) {
            for (int j =  i +1; j < allSublists.length; j++) {

                //Check duplicate characters
                if(allSublists[j].indexOf(elements[i].charAt(0)) == -1) {
                    String s = elements[i] + allSublists[j];
                    char[] c = s.toCharArray();
                    Arrays.sort(c);
                    result.add(new String(c));  // Add sorted String
                }
            }
        }
        return result.toArray(new String[result.size()]);
    }
}

Answer 2

Quick and dirty the key is to construct new Strings in lexicographic order... tokens contains the A, B, C, D result also contains A, B, C, D when starting

for the output shown in your post run

result = perm(tokens,result,1,3);

 public static List<String> perm(List<String> tokens, List<String> result, int currentLength, int maxLength){
    if(currentLength == maxLength){
        return result;
    }
    List<String> gen = new ArrayList<String>();
    for(String s : result){
        for(String s1 : tokens){
            if(s.equals(s1) || s.contains(s1)){
                continue;
            }else{
                String temp = s+s1;
                char[] ca = temp.toCharArray();
                Arrays.sort(ca);
                String res = "";
                for(char c : ca){
                    res+=c;
                }
                if(gen.contains(res)){
                    continue;
                }
                gen.add(res);
            }
        }
    }
    if(gen.size() > 0){
        result.addAll(perm(tokens,gen,currentLength+1,maxLength));
    }
    return result;
}