1
$\begingroup$

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

$\endgroup$
11
  • $\begingroup$ I can't figure out what your question is asking; it appears to be a programming question, not a math one; it is "repetitive", not "repeatative"; and I think this is not of interest to professional mathematicians. Perhaps StackOverflow or one of the forums listed in mathoverflow.net/faq#whatnot can help. $\endgroup$ Jan 21, 2010 at 6:04
  • $\begingroup$ Nah ! this is not a programming related question.. its pure maths .. and that is what I have written there .. By the way .. Its quite easy with the programming I know .. $\endgroup$ Jan 21, 2010 at 6:25
  • $\begingroup$ One would think that a question which can be answered by a citation to The Art of Computer Programming would be well within the purview of Stack Overflow. Did you trying asking it over there? $\endgroup$ Jan 21, 2010 at 6:54
  • $\begingroup$ I don't need a program .. It must be a kind of PICK .. like in the above example, If I want to pick the first number it should map to the number 3 .. which is because of the function or formula f(n) .. I need to create such a kind of formula which is generalized for all the values of N .. thanx for the response .. :-) $\endgroup$ Jan 21, 2010 at 7:06
  • 1
    $\begingroup$ This was far from nonsense. What was misleading was that the questioner's name includes "programmer" so people kept giving programming references. $\endgroup$ Jan 22, 2010 at 1:20

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the support sir, I will refer this as the answer and follow-on .. $\endgroup$ Jan 22, 2010 at 5:06
  • 2
    $\begingroup$ While I agree with your interpretation of the question, I am very nervous about your answer. In particular, I don't like the idea that composing several poor sources of randomness is a good way to make a random number generator. As Donald Knuth says, "random numbers should not be generated with a method chosen at random". See the introduction to Chapter 3 in The Art of Computer Programming, Volume II, for an example of how this can fail. $\endgroup$ Jan 28, 2010 at 18:12
  • 1
    $\begingroup$ Of course, the previous comment assumes that we need a high quality source of randomness, such as would be used in cryptography or for a gambling website. If we just something that looks random to a casual observer, your solution is probably fine. $\endgroup$ Jan 28, 2010 at 18:13
4
$\begingroup$

You want a random permutation. See the Knuth shuffle.

$\endgroup$
3
  • $\begingroup$ Thanx for the useful link .. Please add-up something if you are familiar with, which helps in mapping rather than programming .. Mapping I mean to say is something where it is allowed to write one formula (no conditions and loops) common for all numbers .. $\endgroup$ Jan 21, 2010 at 9:39
  • 1
    $\begingroup$ The only closed form for general n is the description given. The function is not smooth or continuous, and I see no reason to believe that a closed-form expression exists for any n. $\endgroup$ Jan 21, 2010 at 13:39
  • $\begingroup$ Yup I agree with you @Harry Gindi $\endgroup$ Jan 21, 2010 at 14:19
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I am not sure if this is what you are looking for. Am I required to fit my formula in O(1) cells, independent of n? If so, things become much harder and I don't know how to do it. $\endgroup$ Jan 21, 2010 at 13:00
  • $\begingroup$ That's really great of you sir .. thanx for help and support .. :-) $\endgroup$ Jan 21, 2010 at 14:33
  • $\begingroup$ Well said @david .. and I am glad that you appreciated my questioning .. The answer has not been actually accepted (I just accepted Douglas's answer because he said ITS POSSIBLE) .. and I am still doing research on the need .. $\endgroup$ Feb 4, 2010 at 5:47
  • $\begingroup$ In case of programming we are facilitated with RAM and processor resolving algorithm with powerful loops and stuff .. But as you know thats not the case with mapping .. where we are left with only a (essentially complicated,) formula which picks the numbers in jumbled fashion (not-repeatedly) .. $\endgroup$ Feb 4, 2010 at 5:52
  • $\begingroup$ Best analogy would be the most perfect Playlist shuffling algorithm (which instantly picks up a track in the list, but doesn't repeat) .. The only way left is to convert that shuffling algorithm into a complicated formula .. ;-) I know its certainly hardly possible stuff .. well. by the way, I don't forget to thank your support and interest .. $\endgroup$ Feb 4, 2010 at 6:01

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