Seeking for a formula or an expression to generate non-repeatative random number .. [closed]

Question

With my personal interest and hobby I started this ..
Given a sequence of numbers 1,2,3 .... N
where N is the highest among the sequence and length of the sequence as well ..

I tried my best to bring up a relationship where y=f(n) .. so that .. y (equal or not-equal to n) is an unique value for each value of n bounded within N,

for example:
for the sequence:
1, 2, 3, 4, 5
Corresponding sequence would be ..
3, 2, 5, 1, 4 (or Assume some other random sequence of same numbers) ..
where 3=f(1), 2=f(2), etc ..

The function f(n) must effectively work for all values of N .. ie we must be able to generate the random sequence of any value of N.

Initially I tried with y = (n * 9) % N, y = (n * 7) % N and y = (n * 3) % N But they work only if the number is divisible by 10 and the max number if not divisible by 3, 7 and 9 ..

Is it possible to generalize the formula .. ? Please help me in deriving the same ..

Answer 1

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.

Answer 2

You want a random permutation. See the Knuth shuffle.

Answer 3

I haven't used EXCEL in forever, but here is how I would implement the Knuth shuffle in what I would think of as a generic spreadsheet. I want two 1-dimensional arrays, which I will call $x[i]$ and $y[i]$, and one 2-dimensional array $z[i,j]$. Think of three worksheets.

$x[i]$ is a random variable with value chosen from $\{ 1,2, \ldots, n-i+1 \}$.

$z[1,j]=j$.

For $i>1$, we have $z[i,j] = \mathrm{IF}(j \geq x[i],\ z[i-1, j],\ z[i-1,j+1]]$. (Here $\mathrm{IF}(P,a,b)$ returns $a$ if $P$ is true and $b$ otherwise.)

And $y[i]$, our output, is $z[i][x[i]]$.

---

An example: if y[i] is

$$\begin{matrix} 4 & 2 & 1 & 2 & 1 \end{matrix}$$

then $z$ is

$$\begin{matrix} 1 & 1 & 1 & 3 & 3 \\ 2 & 2 & 3 & 5 & \\ 3 & 3 & 5 & & \\ 4 & 5 & & & \\ 5 & & & & \\ \end{matrix}$$

and $y$ is

$$\begin{matrix} 4 & 2 & 1 & 5 & 3 \end{matrix}.$$

---

It occurs to me that some of the spreadsheet software I worked with didn't allow an expression like $y[i][x[i]]$, but only allowed me to address a cell by its location plus a constant offset. Here is a hack to get around that: define $z[i] = \sum_{j} y[i,j] - \sum_j y[i+1,j]$. Any spreadsheet should let you total up columns.