Write a (stateless) function nextPermutation that takes a permutation (as a list) on the elements of the set {1, …, n} and returns the “next” permutation, so that chaining n! calls to nextPermutation([1, …, n]) results in the generation of every permutation on the set {1, …, n}.
I'm not sure I understand the question properly. Is the list you're given as input literally a permutation of the first N integers, or is it an arbitrary list of N things? If you're not allowed to "look at" the N items in the list and have to use an implementation that always performs the same transformation of the input, this is impossible. If N equals 3, there are six possible output cycles you can produce...
{a,b,c} -> {a,b,c} {a,b,c} -> {a,c,b} -> {a,b,c} {a,b,c} -> {b,a,c} -> {a,b,c} {a,b,c} -> {b,c,a} -> {c,a,b} -> {a,b,c} {a,b,c} -> {c,a,b} -> {b,c,a} -> {a,b,c} {a,b,c} -> {c,b,a} -> {a,b,c}
none of which include all 3! permutations of {a,b,c}. So you have to "cheat"... which should be possible, because everything is stored as just bits (integers) anyway...
Quixey is a 2-year-old startup with a lot of ties to the rationalist community. Our product is an all-platform "functional search" engine for apps. Our main engineering task is to build the most accurate possible map of all software on all platforms (the "functional web"), and write search algorithms that let users find apps to do what they need.
We're hiring top-notch engineers for full time positions in our Palo Alto, CA office. If your overall engineering skill level is "Google+", we have a lot to offer: