I think this is a problem we’ve done before. Let’s see if I’m right.
The problem: Permutation Generation. This is problem MS6 in the Appendix.
The description: Given a set F of functions on some set A (each f in F maps from A to A), and a “goal” function h, also from A to A. Can we get h from some composition of the functions in F?
Example: Suppose F was:
- f1(x) = x+1
- f1(x) = 2x
- f3(x) = x+2
with all functions mapping from Z->Z. If h was the function x+3, we could get it by h(x) = f1(f2(x)). We could not get the function x+7 out of any composition of the above functions.
Reduction: G&J send us to the paper by Garey, Johnson, Miller and Papadimitriou we used for Arc Coloring. In that problem we had a detour into the “Word Problem For Products of Symmetric Groups” (WPPSG), which I think is this problem, or at least a version we can reduce from for our problem.
WPPSG asks: Given a set X of permutations on the numbers 1..K and a “goal” permutation π, can π be written as a composition of the permutations in X?
We can view a permutation of 1..K as a function, then our h is just the permutation π: h(1) = the first element of π, h(2) = the second element of π, and so on. Thus, we have a function composition that reaches h if and only if we have a combination of permutations that reach π.
Difficulty: 4, if you’ve seen the WPPSG problem. It’s easy for people to get confused about the difference between functions and sequences here.