Recursively finding n word permutations given a linked-list of strings in C?

3214 views c
3

I'm having trouble creating a recursive algorithm to find the number of n word permutations given a linked list of strings.

So, the function should take the linked list of strings and output a linked list of all possible concatenated permutations of those strings, separated by spaces.

Essentially, if the linked list was say ("cat", "dog", "mouse"), and n was 3, it should return: "cat dog mouse", "cat mouse dog", "dog cat mouse", "dog mouse cat", "mouse cat dog", and "mouse dog cat".

Similarly, if n was 2, it should return: "cat dog", "cat mouse", "dog cat", "dog mouse", "mouse cat", and "mouse dog".

I can't seem to figure out a solution.

answered question

Any attempts, at least? Also, are the words guaranteed to be unique?

Hello and welcome to SO. While we are always anxious to help someone with a programming problem, we like to see what the person has already tried and what isn't working so that we are in a better position to provide an answer as well as to prevent us offering suggestions that have already been tried and aren't working. With that in mind, could you post the code you have already tried and show us where it seems to be going wrong? This link will help to explain this concept in more detail - idownvotedbecau.se/noattempt

From you question I say that you should learn combinations first then jump to permutations - learn about playing with bits (binary representation) using pen and paper and then come to programming part.

What kind of trouble?

My suggestion is to write a prototype in Python or PHP or some scripting language where memory management is nonexistent and string concatenation is trivial. When you have the prototype working you can start converting it to C.

These words being in linked list is irrelevant to the question. You are basically solving a permutation of n out of m elements. Did you try read everything out, put it in a flat array, and just use the array index to do permutation? This will be one way to solve this problem.

1 Answer

11

Recursion involves finding an inductive case and a base case. The inductive case takes you one step closer to the solution, while the base case solves a small version of the problem.

In this case, your base case is "find all permutations of a list with one element." There is only one value in this set, the string itself.

A great candidate for your inductive case would be "for each string in the set, return the concatenation of that string with each of the permutations of the set without that string".

posted this

Have an answer?

JD

Please login first before posting an answer.