Generating permutations of a string in a range

Question

I am looking for an extremely efficient way to generate all possible permutations of a string (or alphabet), where the permutation length it bounded below and above by two variables (i, j).

So far I have been able to generate permutations a number of ways, e.g...

void swap(char *x, char *y){
    char w;
    w = *x;
    *x = *y;
    *y = w;
}

void permute(char *str, int start, int n){
    int i;

    if(start == n-1)
        printf("%s\n", str);
    else
        for(i = start; i < n; i++){
            swap(str+i, str+start);
            permute(str, start+1, n);
            swap(str+i, str+start);
        }
}

... but no algorithm I have found so far will efficiently limit the length of the resulting strings. An example of this would be if the alphabet was defined as abcde and i = 2, j = 4... this would yield permutations such as ab, bac, dcea, but NOT a, edcba, and since the algorithm is not computing combinations, it would also not yield strings like aab.

Answer 1

What about simply passing the minimum and maximum length into the function, and printing the string when start is between the two?

Code:

void permute(char *str, int start, int n, int minLength, int maxLength)
{
    int i;

    if (start >= minLength)
    {
        char temp = str[start]; // store the character, so we don't lose it
        str[start] = 0; // 0x00 - end of string
        printf("%s\n", str);
        str[start] = temp;
    }

    if (start == maxLength)
        return;

    for (i = start; i < n; i++)
    {
        swap(str+i, str+start);
        permute(str, start+1, n, minLength, maxLength);
        swap(str+i, str+start);
    }
}

Live demo.

---

If there are duplicates in the data, and you want to prevent duplicate permutations, all you need to do is:

• Sort the letters to start so any repeated characters are next to each other

• Don't do anything if the last character was the same as this one. This can be done by simply adding the following code to the beginning of the for-loop:

  if (i != start && str[i] == str[i-1])
      continue;
  

Live demo.