Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating all permutations of a certain length

Suppose we have an alphabet "abcdefghiklimnop". How can I recursively generate permutations with repetition of this alphabet in groups of FIVE in an efficient way?

I have been struggling with this a few days now. Any feedback would be helpful.

Essentially this is the same as: Generating all permutations of a given string

However, I just want the permutations in lengths of FIVE of the entire string. And I have not been able to figure this out.

SO for all substrings of length 5 of "abcdefghiklimnop", find the permutations of the substring. For example, if the substring was abcdef, I would want all of the permutations of that, or if the substring was defli, I would want all of the permutations of that substring. The code below gives me all permutations of a string but I would like to use to find all permutations of all substrings of size 5 of a string.

    public static void permutation(String str) { 
    permutation("", str); 
}
private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}
like image 471
TheHumblePedestrian Avatar asked Feb 10 '16 18:02

TheHumblePedestrian


3 Answers

In order to pick five characters from a string recursively, follow a simple algorithm:

  • Your method should get a portion filled in so far, and the first position in the five-character permutation that needs a character
  • If the first position that needs a character is above five, you are done; print the combination that you have so far, and return
  • Otherwise, put each character into the current position in the permutation, and make a recursive call

This is a lot shorter in Java:

private static void permutation(char[] perm, int pos, String str) {
    if (pos == perm.length) {
        System.out.println(new String(perm));
    } else {
        for (int i = 0 ; i < str.length() ; i++) {
            perm[pos] = str.charAt(i);
            permutation(perm, pos+1, str);
        }
    }
}

The caller controls the desired length of permutation by changing the number of elements in perm:

char[] perm = new char[5];
permutation(perm, 0, "abcdefghiklimnop");

Demo.

like image 72
Sergey Kalinichenko Avatar answered Oct 20 '22 00:10

Sergey Kalinichenko


All permutations of five characters will be contained in the set of the first five characters of every permutation. For example, if you want all two character permutations of a four character string 'abcd' you can obtain them from all permutations: 'abcd', 'abdc', 'acbd','acdb' ... 'dcba'

So instead of printing them in your method you can store them to a list after checking to see if that permutation is already stored. The list can either be passed in to the function or a static field, depending on your specification.

like image 35
Luke Caswell Samuel Avatar answered Oct 19 '22 23:10

Luke Caswell Samuel


class StringPermutationOfKLength
{
    // The main recursive method
    // to print all possible
    // strings of length k
    static void printAllKLengthRec(char[] set,String prefix,
                                   int n, int k)
    {

        // Base case: k is 0,
        // print prefix
        if (k == 0)
        {
            System.out.println(prefix);
            return;
        }

        // One by one add all characters
        // from set and recursively
        // call for k equals to k-1
        for (int i = 0; i < n; i++)
        {

            // Next character of input added
            String newPrefix = prefix + set[i];

            // k is decreased, because
            // we have added a new character
            printAllKLengthRec(set, newPrefix,
                n, k - 1);
        }
    }

    // Driver Code
    public static void main(String[] args)
    {
        System.out.println("First Test");
        char[] set1 = {'a', 'b','c', 'd'};
        int k = 2;
        printAllKLengthRec(set1, "", set1.length, k);

        System.out.println("\nSecond Test");
        char[] set2 = {'a', 'b', 'c', 'd'};
        k = 1;
        printAllKLengthRec(set2, "", set2.length, k);
    }
like image 38
Ravi Raj Avatar answered Oct 19 '22 22:10

Ravi Raj