0
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – Paul
    Apr 3 '17 at 16:44
  • $\begingroup$ I'm guessing you need to stay away from recursion? (Because it's not practically scalable for large $n$?) $\endgroup$
    – John
    Apr 3 '17 at 16:44
  • $\begingroup$ 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? $\endgroup$ Apr 3 '17 at 16:46
  • 1
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$
    – Josh Chen
    Apr 3 '17 at 16:51
1
$\begingroup$

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

You can write this as a tail-recursive algorithm if you define a helper function, but maybe the details of that are a better fit on e.g. StackOverflow.

$\endgroup$
0
$\begingroup$

If you're trying to write a program in Python then there is itertools.combinations that will create all combinations of an arbitrary size of a given set.

$\endgroup$
1
  • $\begingroup$ My interest is in how that algorithm works, not in generating the permutations themselves. I can do it in MATLAB, too, but I don't know how MATLAB does it. $\endgroup$ Apr 3 '17 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.