Warning: Untested Pseudocode
This is pseudocode. It isn't finished and probably won't even compile.
minCost :: element -> [generator] -> number -> Maybe [generator]
minCost _ [] _ = Nothing
minCost x _ c | (elemCost x) + c > cutoff = Nothing
minCost e _ _ = Just [] -- The factorization of the identity is the nullary product.
minCost x gs _ | elem x gs = Just [x]
minCost x gs _ | elem x ps = Nothing -- in P but not in gs.
minCost x gs c =
argmin
pathCost
[maybeCons g (minCost (x-g) [h| h <- gs, h <= g, h /= -g] (c+(elemCost g))) | g<-gs]
maybeCons :: a -> Maybe [a] -> Maybe [a]
maybeCons _ Nothing = Nothing
maybeCons x (Just xs) = Just (x:xs)
elemCost :: element -> number
pathCost :: [element] -> number
pathCost = sum . map elemCost
argmin :: (a -> n) -> [Maybe a] -> Maybe a
-- Return the item with the lowest cost, or Nothing if there isn't one.
There's a little bit of handwaving here, but the logic should, I hope, be clear. We have to impose an arbitrary total ordering on P and argmin has to handle results of Nothing, representing that there's no way to generate x from that subset of P. My pseudocode doesn't have quite the right syntax to do this, for readability.
Excluding h > g from the allowed generators is safe, because any solution containing h would be found by the minCost (x-h) branch, up to permutation (and G is Abelian, so any solutions that are permutations are equivalent). Excluding -g is safe because g + (-g + a) = a, but at strictly higher cost, so no such solution could be optimal.
The algorithm needs a way to prune branches such as, when P = {1,-1,i,-i}, testing (2+i) {1,-1,-i}, (2+2i) {1,-1,-i}, ad infinitum. This probably requires pruning the search when the cost exceeds a cutoff. With that fix, it terminates because each recursion reduces the size of gs or the number of steps until x reduces to a generator, until it reaches one of the base cases or the cost accumulates above the threshold. (This might be improved by passing up the lowest cost calculated on any parallel branch so far.) It cannot repeat a computation because we have excluded the inverses of all previous steps in the path.
Afterthoughts
Saying that e generates itself even if not in P is incorrect by requirements and unnecessary for correctness: the algorithm never adds an element to its own inverse, so this can only occur if we ask explicitly how to generate the identity. And that's a valid query: complex roots of unity?
On further reflection, thanks for the suggestion to represent the identity as the nullary product. Otherwise, we'd fail because we never check generators against their inverses! It has the right type, too!
There's a case to make the return type [[generator]] instead of Maybe [generator] and return all optimal productions, representing Nothing as []. The definition of maybeCons would become just map ((:)g). However, this risks exponential blow-up if there are a lot of equally-cheap paths.
Returning the cost along with the factorization, in a tuple, would both let us prune any later parallel branch with a higher cost sooner. Or we could use pathCost for this.
The particular lattice structure of your group might suggest more ways to prune, although I'm not thinking of any others in general. For instance, for the complex integers under addition, we can easily detect what the two (at most) generators must be just from the real and imaginary coefficients. In many groups, we can easily detect that something is not a product of a particular generator by which subset of G it is in. These could be additional guards that tail-recurse with a proper subset of gs.
The generator type has to be the same as element or an instance of it, because of the cost function. The ordering relation might be defined only for generators, or their structure might be simpler. It might have a different name if the group has a natural ordering that happens to be less efficient for the algorithm.
I'll leave in the note that the code isn't supposed to compile because I'm pretty sure I wrote at least one bug.
