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...