Permutation Generation

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.

Leave a Reply

Your email address will not be published. Required fields are marked *