How to systematically (ie: algorithmically) generate permutations of a set?

Given the first $n$ natural numbers, how do you systematically generate all of the $n!$ permutations of that set? I can do it for a known $n$ using a computer program, but it requires $n$ nested loops. I'm sure there must be a more efficient way.

• You probably want to use recursion, a function that calls itself. Instead of $n$ loops you have a function with one loop that calls itself $n$ levels deep. So effectively you do the same, but now $n$ can be variable.
– Paul
Apr 3 '17 at 16:44
• I'm guessing you need to stay away from recursion? (Because it's not practically scalable for large $n$?)
– John
Apr 3 '17 at 16:44
• I suppose recursion could work. Presumably any recursive algorithm can be modified to be a stack-based algorithm, so it's all good. I guess the questions are: a) is recursion (or some method based on it) the only way and b) if not, how? Apr 3 '17 at 16:46
• en.wikipedia.org/wiki/… Apr 3 '17 at 16:51

If $S_n$ is the set of all permutations of $\{1,\dotsc,n\}$ then a recursive formulation is
$$S_{n+1} = \bigcup_{i=0}^n\ \{ f_i(s) \mid s \in S_n \}$$
where $f_i(s)$ denotes the permutation obtained by inserting $n+1$ after the $i$-th entry of the $n$-permutation $s$. (For $i=0$ this is inserting in the first place.)