Fastest (fast enough to compute) algorithm for finding permutations
Suppose you are working with an alphabet of size $d$.  Then each word can be represented as its characteristic vector.  A characteristic vector $v \in \mathbb{N}^d$ is a vector, where the $i$th entry counts the number of times the $i$th letter appears in the word.  For instance, the word $abbad$ would have characteristic vector $(2,2,0,1)$ if the alphabet is $a,b,c,d$.

As Yuval explains, you want to find all strings which satisfy the following two properties: (1) they are a rearrangement of the list of letters, (2) they are a concatenation of up to $n$ words from the list of words (the same word can be used several times).

Looking at characteristic vectors, you can think of the problem as follows: you are given vectors $v_1,\dots,v_k$ (corresponding to the list of words) and a vector $w$ (corresponding to the characteristic vector for the list of letters), and you want to find non-negative integers $a_1,\dots,a_k$ such that

$$a_1 v_1 + \dots + a_k v_k = w.$$

You also want $a_1 + \dots + a_k \le n$ (to satisfy requirement (2) above).  You want to enumerate all solutions $a_1,\dots,a_k$ that satisfy these requirements.

This turns out to be an instance of enumerating lattice points in a convex polytope, for which there are well-studied algorithms.  See the following paper for an overview:


Effective lattice point counting in rational convex polytopes.  Jesús A. De Loerab, Raymond Hemmecke, Jeremiah Tauzera, Ruriko Yoshida.  Journal of Symbolic Computation, vol 38 no 4, Oct 2004, pp.1273-1302.  https://www.sciencedirect.com/science/article/pii/S0747717104000422


You could try applying one of those algorithms to your problem to see how well they work.



Alternatively, it's also possible to solve the problem by repeatedly invoking an ILP solver.  You can use an ILP solver to test whether any solution exists, and the largest value of $a_1$ such that a solution exists.   Then,  if at least one solution exists, you enumerate $a_1=0,1,2,\dots$, and for each value of $a_1$, plug in the value of $a_1$ and recursively invoke the same algorithm to enumerate all solutions for $a_2,\dots,a_k$ (such that $a_2 v_2 + \dots + a_k v_k = w - a_1 v_1$ and $a_2 + \dots a_k \le n - a_1$).  This might be inefficient, though.