0

在阅读了几篇文章后，我仍然对排列和递归函数感到困惑。我正在尝试在不等长的二维数组中创建所有可能的 3 个字母排列，其中第一个字母来自集合 {'l'、'm'、'n'}，第二个字母来自集合 {'q ', 'r'} 和第三个字母来自集合 {'a', 'e', 'i', 'o'}。我的代码通过了正确的排列模式，但没有打印出正确的输出。例如，如果前 8 个排列应该是：

lqa
lqe
lqi
lqo
lra
lre
lri
lro

我的代码打印出来：

lqa
e
i
o
ra
e
i
o

关于问题是什么的任何想法？以下是我的代码的相关部分：

rec(character_pools,0,3);
void rec(char** pool, int k, int j)
{
    if(k==j)
    {
        printf("\n");
        return;
    }
    int i,len=strlen(pool[k]);
    for (i=0;i<len;i++)
    {
        printf("%c",pool[k][i]);
        rec(pool,k+1,j);
    }
}
4

3 回答 3

1

这最终为我工作！谢谢@Tsukuyo 的提示。如果我想在排列中找到字符串的第 n 个索引，是否需要提出单独的问题？

void rec(char** pool, int k, int j, char* cur, int counter)
{
    if(k==j)
    {
        cur[k]=0;
        printf("Recursive call #%d %s\n",counter,cur);
        return;
    }
    int i,len=strlen(pool[k]);


    for (i=0;i<len;i++)
    {
        cur[k]=pool[k][i];
        rec(pool,k+1,j,cur,counter++);
    }
}
于 2013-09-21T16:12:09.797 回答
1

调用堆栈：

   rec(pool, 0, 3);
-> 'l'   rec(pool, 1, 3);
      -> 'q'   rec(pool, 2, 3);
            -> 'a'   rec(pool, 3, 3);
                  -> '\n'
            -> 'e'   rec(pool, 3, 3);
                  -> '\n'
            -> 'i'   rec(pool, 3, 3);
                  -> '\n'
            -> ...
      -> ...
-> ...

更新：
不像递归。但是..它有效:)。希望这可以帮助。
假设最大长度为 10。 

#include <stdio.h>
#include <string.h>
#define ALL_DONE 1
#define NOT_YET  0

int rec(char (*pool)[10], int num, int start);

int main(void)
{
    int i, num;
    char pool[20][10];

    scanf("%d", &num);
    for (i = 0; i < num; i++){
        scanf("%s", pool[i]);
    }
    while ( !rec(pool, num, 0) );  // keepint calling until all permutations are printed
    return 0;
}

int rec(char (*pool)[10], int num, int start)
{
    static int ndx[20] = {0};  // record the index of each string

    if (start == num){
        printf("\n");
        return ALL_DONE;
    }
    printf("%c", pool[start][ndx[start]]);
    if ( rec(pool, num, start+1) == ALL_DONE ){
        ndx[start+1] = 0;
        ndx[start]++;
        if (ndx[start] == strlen(pool[start])){
            return ALL_DONE;
        return NOT_YET;
    }
    return NOT_YET;
}

解释： 

   rec(pool, 0, 0)[1st calling]     
-> 'l'   rec(pool, 1, 0)                    | ndx[0..2] = 0, 0, 0
      -> 'q'   rec(pool, 2, 0)              | ndx[0..2] = 0, 0, 0
            -> 'a'   rec(pool, 3, 0)        | ndx[0..2] = 0, 0, 0
                  -> '\n' retrun ALL_DONE   | ndx[0..2] = 0, 0, 0
            -> return NOT_YET               | ndx[0..2] = 0, 0, 1
      -> return NOT_YET                     | ndx[0..2] = 0, 0, 1
-> return NOT_YET                           | ndx[0..2] = 0, 0, 1
|
   rec(pool, 0, 0)[2nd]
-> 'l'   rec(pool, 1, 0)                    | ndx[0..2] = 0, 0, 1
      -> 'q'   rec(pool, 2, 0)              | ndx[0..2] = 0, 0, 1
            -> 'e'   rec(pool, 3, 0)        | ndx[0..2] = 0, 0, 1
                  -> '\n' return ALL_DONE   | ndx[0..2] = 0, 0, 1
            -> return NOT_YET               | ndx[0..2] = 0, 0, 2
      -> return NOT_YET                     | ndx[0..2] = 0, 0, 2
-> return NOT_YET                           | ndx[0..2] = 0, 0, 2
|
|  ...
|
   rec(pool, 0, 0)[4th]
-> 'l'   rec(pool, 1, 0)                    | ndx[0..2] = 0, 0, 3
      -> 'q'   rec(pool, 2, 0)              | ndx[0..2] = 0, 0, 3
            -> 'o'   rec(pool, 3, 0)        | ndx[0..2] = 0, 0, 3
                  -> '\n' return ALL_DONE   | ndx[0..2] = 0, 0, 3
            -> return ALL_DONE              | ndx[0..2] = 0, 0, 4
      -> return NOT_YET                     | ndx[0..2] = 0, 1, 0
-> return NOT_YET                           | ndx[0..2] = 0, 1, 0
|
| ...
| ...
|
   rec(pool, 0, 0)[5th]
-> 'l'   rec(pool, 1, 0)                    | ndx[0..2] = 0, 1, 0
      -> 'r'   rec(pool, 2, 0)              | ndx[0..2] = 0, 1, 0
            -> 'a'   rec(pool, 3, 0)        | ndx[0..2] = 0, 1, 0
                  -> '\n' return ALL_DONE   | ndx[0..2] = 0, 1, 0
            -> return NOT_YET               | ndx[0..2] = 0, 1, 1
      -> return NOT_YET                     | ndx[0..2] = 0, 1, 1
-> return NOT_YET                           | ndx[0..2] = 0, 1, 1
|
| ...
|
   rec(pool, 0, 0)[8th]
-> 'l'   rec(pool, 1, 0)                    | ndx[0..2] = 0, 1, 3
      -> 'r'   rec(pool, 2, 0)              | ndx[0..2] = 0, 1, 3
            -> 'o'   rec(pool, 3, 0)        | ndx[0..2] = 0, 1, 3
                  -> '\n' return ALL_DONE   | ndx[0..2] = 0, 1, 3
            -> return ALL_DONE              | ndx[0..2] = 0, 1, 4
      -> return ALL_DONE                    | ndx[0..2] = 0, 2, 0
-> return ALL_DONE                          | ndx[0..2] = 1, 0, 0
|
| FINISH
于 2013-09-21T04:33:25.317 回答
1

您创建一个 char 数组，其中将包含您要使用的字符串 char str[] = "ABC";

然后你得到字符串的长度，int n = strlen(str);最后你排列。

您创建一个新函数，其中将包含输入字符串、字符串的起始索引和字符串的结束索引。检查起始索引 ( int s) 是否等于结束索引 ( int e) 如果是，则表示您已经完成，如果不是，则进入从 start (s) 到 end (e) 的循环，交换值，递归，再次交换回溯。

C++ 中的一个示例：

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

void swap(char *i, char *j)
{
    char temp;
    temp = *i;
    *i = *j;
    *j = temp;
}

void permutate(char *str, int start, int end)
{
    int i;
    if (start == end)
        printf("%s\n", str);
    else
    {
        for (i = start; i <= end; i++)
        {
            swap((str + start), (str + i));
            permutate(str, start + 1, end);
            swap((str + start), (str + i)); //backtrack
        }
    }
}

int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permutate(str, 0, n - 1);
    return 0;
}
于 2016-01-02T15:02:30.853 回答