c - 生成范围内字符串的排列

Question

我正在寻找一种极其有效的方法来生成字符串(或字母表)的所有可能排列，其中排列长度由两个变量 (i, j) 限定。

到目前为止，我已经能够通过多种方式生成排列，例如...

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 这样的字符串。

Answer 1

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

代码:

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 .

---

如果数据中存在重复，而你想防止重复排列，你需要做的就是:

• 对开始的字母进行排序，使任何重复的字符彼此相邻

• 如果最后一个字符与这个字符相同，则不执行任何操作。这可以通过简单地将以下代码添加到 for 循环的开头来完成:

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

Live demo .