When we hear random permutations, we bring in our intuition about permutations, and try to give a method which could generate a complicated permutation. Thus, I think we didn't pay enough attention to your examples like n*3 mod N, which for most situations would not be an acceptable way of generating random numbers. The only problem is what to do if N is divisible by 3. As far as I can tell, divisibility by 10 is irrelevant, so I'm not sure why you mentioned it.

You say you don't want to write a program, just a simple formula in Excel. This is reasonable, and even something which makes sense mathematically: There are a few operations available in Excel formulas such as addition, exponentiation, factorial, conditional evaluation based on whether a statement is true or false (characteristic functions), etc. Can one create a formula with fixed complexity which takes in n and N, and which is a permutation of {1,...,N] for a fixed N? Trivially returning n works, but can one produce a permutation other than (+-n+k mod N)+1?

I suggest creating a formula which is equivalent to the following:

If N is not divisible by 71, return (71*n mod N) + 1.
Otherwise N is divisible by 71. Permute the last digit base 71: return a + (3*b mod 71) +1
where n-1 = a + b and a is divisible by 71 and $0 \le b \lt 93$, i.e.,
b = n-1 mod 71.
a = n-1 - (n-1 mod 71).

IF(MOD(N,71)!=0,n-(MOD(n-1,71)) + MOD(3*(MOD(n-1,71),71),MOD(71*n,N)+1).

(Debugging left to the reader.)

This would be lousy as a random permutation, but it may be acceptable for some purposes.

A better random permutation might be based on f(n), where f reverses the lowest binary digits of n if n is at most than the greatest power of 2 less than N, and does nothing if n is greater. Try f(N+1-f(n)). This can be done using the DEC2BIN and StrReverse functions, but you need a little Excel expertise to use those.

Once you have a few ways to generate random permutations, you can compose them, and even using unsatisfactory random permutations like adding floor(sqrt(N)) can improve the appearance of the resulting permutation.

The Art of Computer Programmingwould be well within the purview of Stack Overflow. Did you trying asking it over there? – Pete L. Clark Jan 21 '10 at 6:54