Finding possible permutation of N words [reviewed]

Problem

Permutate a list of string 

this question is supposed to permutate the characters instead of the whole string, 

Here is input example {"red", "fox", "super" }

the expected output is 

rfs, rfu, rfp, rfe, rfr, ros, rou, rop, roe, ror, rxs, rxu, rxp, rxe, rxr, efs, efu, efp, efe, efr, eos, eou, eop, eoe, eor, exs, exu, exp, exe, exr, dfs, dfu, dfp, dfe, dfr, dos, dou, dop, doe, dor, dxs, dxu, dxp, dxe, dxr

Answer

Algorithm: DFS with backtracking $O(M^N \times N!)$

This is a similar problem to a single-word permutation problem. The difference is that you have N words you need to permutation.

We can perform the permutation of each word in the input remembering characters from each word before

It can be a recursive DFS search. We stop when the next word position reaches the end of the input words.

Here is the pseudo code for the DFS search 

def dfs(input, next_word, found):

  for i in range(len(input[next_word])):
       next = input[next_word][i]
       found.append(next)
      self.dfs(next_word +1)
      found.pop() // backtracking

Exit conditions:

1. When the collected characters from each word in the input become N

- We examined all words. We add the found to the final result list

2. When the next word position is beyond the input list

- if the algorithm is correct this condition happens when the first condition is met.
- We need to add found to the final result list

Here is the complete code in C++



Practice statistics:

13:08: to write up the code and debug. (3 typos)


UPDATE(2019-09-03): solved this problem in Python with the same DFS w/ backtracking

Here is the complete code in python


Practice statistics:

20:07: to come up with the algorithm and write up the code
04:30: to write up the test code and fix one bug in the test code

UPDATE(2022-06-15): Solved the problem again. Took longer to figure out the right algorithm. Turned out that I don't need to remember the starting position of each word since it is the recursive call and we already know which one is the next one. Will fix it later.

14:38: to come up with the algorithm

08:00: to write the code

04:45: to review the code

00:52: to run and check the correctness