I want to get a specific combination of permutation?

Question

I want to get specific combination of permutation of string like alphabet. To understand me, I'll show you the code that I using:

public class PermutationExample {

public static List<String> getPermutation(String input) {

    List<String> collection = null;

    if (input.length() == 1) {
        collection = new ArrayList<String>();
        collection.add(input);
        return collection;
    } else {
        collection = getPermutation(input.substring(1));
        Character first = input.charAt(0);
        List<String> result = new ArrayList<String>();
        for (String str : collection) {
            for (int i = 0; i < str.length(); i++) {
                String item = str.substring(0, i) + first
                        + str.substring(i);
                result.add(item);
            }
            String item = str.concat(first.toString());
            result.add(item);
        }
        return result;
    }

}

public static void main(String[] args) {
    System.out.println(PermutationExample.getPermutation("ABCD"));

}
}

This code works well and i can get every combination, I can take it from the list, if I need 5-th element, I can receive it. But if the string is the alphabet ... , didn't works, it's too big. What I have to do, to get the specific element like 1221-th from all 26! combinations ?

Answer 1

I solved a similar problem a while ago, only in python.

If what you need is simply the n-th permutation, then you can do a lot better then generating every permutation and returning the n-th, if you try to think about generating only the permutation you need.

You can do this "simply" by figuring out what should be the element in front for the number of permutations you want, and then what should be the remaining of the elements recursively.

Assume a collection of values [0, ... ,X], for any values such that col[n] < col[n+1] For N elements, there are N! possible permutations, the case when the collection will be perfectly reversed.

We will see the change in the head of the collection after each (N-1)! permutations, so if n < (N-1)!, the head is the head. You then have a remaining number of permutations, and you can apply the same logic recursively.

Does this help? I know it's fairly high level and you'll have to think a bit about it, but maybe it'll get you on the right track.