c - 给定 C 中的字符串链表，递归地找到 n 个单词排列？

Question

我在创建递归算法来查找给定字符串链接列表的 n 个单词排列数时遇到问题。

因此，该函数应该获取字符串的链接列表，并输出这些字符串的所有可能的串联排列的链接列表，并用空格分隔。

本质上，如果链表是(“cat”，“dog”，“mouse”)，并且 n 是 3，它应该返回:

"cat dog mouse", "cat mouse dog", "dog cat mouse", "dog mouse cat", "mouse cat dog", and "mouse dog cat".

同样，如果 n 为 2，则应返回:

"cat dog", "cat mouse", "dog cat", "dog mouse", "mouse cat", and "mouse dog".

编辑:

我试图写出一些伪(ish)代码:

permutations(list, n, newList, char *phrase){
    //base case
    if(n == 0){
        add phrase to newlist
    //inductive case
    } else {
        while(list != null){
        create a copy of the list without the word from current node = copyList
        char test[100]; 
        strcpy(test, list->word);
        strcat(phrase, test);
        permutations(copyList, n-1, newList, phrase);
        list = list->next;
        }
    }
}

抱歉，如果我的伪代码到处都是。

Answer 1

递归涉及寻找归纳案例和基本案例。归纳案例使您更接近解决方案，而基本案例解决了问题的一小部分。

在这种情况下，您的基本情况是“查找具有一个元素的列表的所有排列”。该集合中只有一个值，即字符串本身。

归纳案例的一个很好的候选者是“对于集合中的每个字符串，返回该字符串与没有该字符串的集合的每个排列的串联”。