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