C - 获取一个字符串的所有排列组合，并为每个重复的字符分配一个数字。

Question

这对我来说是个噩梦。我已经成功地完成了第一部分，即从一个字符串中获取所有的排列组合，这要归功于 这段代码. 成功了！

#include <stdio.h> 
#include <string.h> 

/* Function to swap values at two pointers */
void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

/* Function to print permutations of string 
   This function takes three parameters: 
   1. String 
   2. Starting index of the string 
   3. Ending index of the string. */
void permute(char *a, int l, int r) 
{ 
   int i; 
   if (l == r) 
     printf("%s\n", a); 
   else
   { 
       for (i = l; i <= r; i++) 
       { 
          swap((a+l), (a+i)); 
          permute(a, l+1, r); 
          swap((a+l), (a+i)); //backtrack 
       } 
   } 
} 

/* Driver program to test above functions */
int main() 
{ 
    char str[] = "CASA"; 
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
} 

现在，我怎么能做第二部分？我已经输出了24种不同的排列组合。

需要做的是，给每个重复的字符分配一个数字。到目前为止，我还没有找到在C语言中这样做的方法。我对 "CASA "这个词的输出应该是这样的。. (对了，数字是不是下标不重要，我只是想辨别哪个是同一个字符的第一第二第三)。

Answer 1

您可以创建一个辅助数据结构来表示您的索引字母，例如

struct tag {
    char str[4];
};

现在，您可以为每个字母创建一个标签并对其进行细分，而不是直接对字符串进行细分。

void swap(struct tag *a, int i, int j) 
{
    struct tag temp = a[i]; a[i] = a[j]; a[j] = temp;
} 

void do_permute(struct tag *tag, int lo, int hi) 
{
    if (lo == hi) { 
        for (int i = 0; i < hi; i++) {
            if (i) printf(" ");
            printf("%s", tag[i].str);
        }

        printf("\n"); 
    } else { 
        for (int i = lo; i < hi; i++) { 
            swap(tag, lo, i); 
            do_permute(tag, lo + 1, hi); 
            swap(tag, lo, i); 
       } 
    } 
}

这或多或少是你原来的函数，但我擅自把上界变成了排他性的，就像在C语言中一样。 (我总是有点不安，当我看到... <=的在 for 循环条件）。)

当然，你必须创建标签。你可以在上述后端函数的前端函数中进行。这个函数还应该确定字符串的长度。你可以分两步创建你的标签。

• 对所有的字符进行统计 给每个字母分配一个索引。
• 在第二步中，从每个只出现一次的字母中删除数字。

现在你就可以开始了。

void permute(const char *str)
{
    int l = strlen(str);
    struct tag *tag = malloc(l * sizeof(*tag));
    int count[256] = {0};

    // first pass: assign individual indices for each letter

    for (int i = 0; i < l; i++) {
        unsigned char k = str[i];

        count[k]++;
        snprintf(tag[i].str, sizeof(tag[i].str), "%c%d", str[i], count[k]);
    }

    // second pass: remove index for single instances

    for (int i = 0; i < l; i++) {
        unsigned char k = str[i];

        if (count[k] == 1) tag[i].str[1] = '\0';
    }

    do_permute(tag, 0, l);

    free(tag);
}

现在 permute("CASA") 将会写出一个有索引的组合列表。(但请注意，你可以传递一个字符串字面意思--字符串在排列组合时不会有任何改变。)

请看所有的东西都被放在一个 例子.