Permutations of N Natural Numbers

Before beginning, think about the problem. What does the solution involve? A permutation of N things taken N at a time will consume N! of space (measured in units of the size of one thing). Considering this, the solution offered need only work up to a convenient number: in this case, 255 is chosen.

If we examine the constitution of the solution of N = 255, then we see that this is more than generous.

logs = 0; // log_10(1) == 0, so skip it like a sensible business girl.
for (i=2; i<256; i++)
logs += Math.log(i);
/* note that we can factor out the logarithm conversion
division */
logs /= Math.log(10);
document.write(logs);

Summing the base-10 logarithms of numbers 1..255, we see that an approximate total of permutations is 10⁵⁰⁵: more than the estimated number of electrons with which we might store them in the entire universe!

Secondly, we have the solution "program" itself. In fact, this is the only way to represent the existence of the solutions for unwritable values of N. (Time is a similar entity to this, and in these kinds of problems they are best treated as independent.)

An N-member array is created. The beginning position is occupied with the first number in the set, and the number is withdrawn from the set. The same is done in turn with each member of the set. The same is also done recursively until the end of the series. That is, the last step will be run once for each of the two (last - 1) steps, which are run for each of the three (last - 2) steps, and so on. This last step of all will add the finishing "newline" to be printed after each permutation.

Demonstration solutions

Specify another N

JavaScript Permutation Number Benchmark

The example is coded recursively, with a reduced solution redefined to the original algorithm. The problem could be done more optimally in C with the following techniques:

unsigned char data type (applying the foregone conclusion that N values greater than this are not completable)
in-place modulo addition to create N, N-1,..., 1 permutations (est. speedup would be 10 times)

If C was used, the question would be to create the fastest computer algorithm for decimal-printing and/or computing the results. However, this isn't in the contest.