生成范围内的字符串排列 [英] Generating permutations of a string in a range

问题描述

我正在寻找一种非常有效的方式来生成字符串(或字母)的所有可能排列，其中排列长度在上下两个变量(i, j)的范围内.

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);
        }
}

...但是到目前为止，我还没有找到能有效限制结果字符串长度的算法.例如，如果字母表定义为abcde和i = 2，j = 4 ...，则会产生排列，例如ab，bac，dcea，但不是a， edcba，并且由于该算法未计算组合，因此它也不会产生像aab这样的字符串.

... 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.

推荐答案

简单地将最小和最大长度传递给函数，并在start介于两者之间时打印字符串怎么办?

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

代码:

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);
    }
}

实时演示.

如果数据中存在重复项，并且您想防止重复的排列，那么您要做的就是:

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

如果最后一个字符与此字符相同，则不执行任何操作.只需将以下代码添加到for循环的开头即可完成此操作:

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;

实时演示.

这篇关于生成范围内的字符串排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！