Take the 2-minute tour ×

Suppose I have a sequence of numbers: {n, n+1, n+2, ... n + m}

Without storing the numbers ahead of time I want to create a function f(), which given the sequence {1,2,3,...m} will spit out the original set in a random (or at least pseudo random) order.

For example assume my sequence is {10, 11, 12, 13, 14, 15, 16, 17}

   f(1) could yield 14
   f(2) could yield 17
   f(3) could yield 13
   f(4) could yield 10
   f(5) could yield 16
   f(6) could yield 15
   f(7) could yield 11
   f(8) could yield 12

At one point in the past a co-worker showed me a mathematical algorithm that was able to do this, but I have since forgotten almost everything about it other than it existed. I remember that you had to have the sequence in advance, and generate some constants from the sequence which were used in the function. And for those wondering, I have sadly lost contact with that co-worker.

This question's answers looks close to what I want, but I am not sure if the answers allow me to constrain the output to a specific sequence ahead of time.


To clarify a little more I don't want to store the original sequence, or the shuffled sequence. I want to generate a function f() from the original sequence.

What is frustrating is that I have seen this, I just cannot remember enough about it to find it again with google.

The Fisher-Yates algorithm is great for permuting or shuffling a deck, but it is not what I am looking for.

share|improve this question
could you clarify what you mean by "without storing the numbers ahead of time?" How would the function know the valid set if the set is not stored somewhere? do you mean that your set will always be defined by a start number and count? or that the random output should not be stored ahead of time? –  Erich Mirabal Apr 9 '09 at 4:23
Are there any restrictions on what "m" is? (e.g. a power of 2? a prime?) –  Jason S Apr 10 '09 at 13:18
(or is m guaranteed to be "small" such as < 256 or "large" such as > 65536) –  Jason S Apr 10 '09 at 13:19
Take a look at this wikipedia entry: en.wikipedia.org/wiki/Linear_congruential_generator. Note the part about generating the numbers that give you a full period. Note that for some value of m (your sequence size), the math does not work out in your favor to generate a proper LCG. –  Erich Mirabal Apr 10 '09 at 13:23
@Jason S: There are no restrictions on the size of m. –  grieve Apr 10 '09 at 15:21
show 1 more comment

10 Answers

up vote 5 down vote accepted

There is a simple function that generates a permutation of [0..m-1] for a given m. Just pick a number k, relatively prime to m and let f(i)=(k*i) mod m. This always generates a permutation (no repeats on 0<=i<m). It works better if k is larger than m.

For example, m=20, let k=137 (Python code, % means modulo):

 >>> [(137*i) % 20 for i in range(20)]
 [0, 17, 14, 11, 8, 5, 2, 19, 16, 13, 10, 7, 4, 1, 18, 15, 12, 9, 6, 3]

This is a very simple PRNG, no guarantees about its statistical properties.

share|improve this answer
k and m need to be relatively prime. Consider what would happen if m=4 and k=8... Choosing a strict prime for k will insure this. –  dmckee Apr 9 '09 at 15:30
Ekhm, isn't it what I wrote? "pick a number k, relatively prime to m". –  Rafał Dowgird Apr 9 '09 at 15:35
This is not random at all. Your pattern is the same as "subtract 3 (mod 20) above. In fact, k is congruent to k mod m, so in the above, k ~= -3. –  rlbond Apr 15 '09 at 4:27
add comment

This question is analogous to shuffling a deck of (m + 1) cards, numbered [n, ..., n + m]. Notice that the numbering (and thus n) is unimportant; what matters is that we can tell the cards apart. (You can simply add the n back later if desired.)

To do what you want, you can perform a Fisher-Yates shuffle and just keep track of which indices have been selected for shuffling so far. This will allow you to avoid storing another copy of the values themselves, as requested.

share|improve this answer
add comment

Your question is a bit confusing, as it sounds like you want to get all of the original sequence back, but then you have both 4 and 8 mapping to 10, and nothing mapping to 12.

If you actually meant that to be a 1:1 mapping, then what you are looking for is a random permutation of the original set. There are ways to do this with or without collecting up the set first (but you'll need something that generates it, or keep track of where you are).

Also, note that n is not important. You can always use 0,1,2,...m and then add n to everything if needed.

Assuming I've interpreted this correctly and you are actually looking for a shuffle algorithm (i.e. random permutation, called shuffles by analogy to shuffling a deck of cards), have a look at Fisher-Yates

[Edit] Ok, based on your update, the problem you face is this: You don't want to encode the permutation explicitly, but you must encode it somehow in order to construct f. The easiest way is just to actually store the permuted indices in an array, but if you don't want to do that for some reason (e.g. too big), you can encode it in various ways. There is no free lunch though, as there are information theoretic limits on how simple this can be. Anyway, you can get some ideas from looking up work on "encoding permutations" for example something like this paper

share|improve this answer
I did intend a one to one mapping. I edited the question to reflect that. Sorry for the confusion. –  grieve Apr 9 '09 at 5:08
add comment

Here is some pseudocode in my own made-up language:

function f(array a)
    array newArray
    while a.size() == 0
        int position = randomNumber(1 to a.size())
        int removedNumber = a[position]
    end while
    return newArray
share|improve this answer
He said he doesn't want to have to store the numbers -- passing in an array containing the numbers is cheating, isn't it? –  John Feminella Apr 9 '09 at 4:00
add comment

add the initial values to a list.
then, use a random number to pick a new index value in the range of the list's current size.
use that index to select and then remove the number from the list.

as somebody already pointed out, this is similar to having a deck of cards, and then randomly removing one card at a time.

share|improve this answer
add comment

If you want a 1:1 mapping, go with Fisher-Yates as mentioned in the other answers.

If you don't care about 1:1 mapping, and you just need all of the resulting values to be from the given sequence (with the possibility of repeats), then you can use a random function with a specified range.

For example, in C++, you could use rand() in the following way -

result = rand() % (m+1) + n

So for your example,

result = rand() % 8 + 10

Would produce an integer between 10 and 17.

share|improve this answer
add comment

You can fit a polynomial to the selected sequence; I'd guess that's what your coworker showed you. It won't save space compared to just remembering the permutation, though.

share|improve this answer
The final function was relatively simple, and did not require a long polynomial (at least as I remember it). We had about a million numbers in the sequence, and I think there were only a few terms in the function. –  grieve Apr 9 '09 at 6:49
add comment

You can generate a permutation of the first n integers by using a block cipher and xor folding, as per my previous answer.

share|improve this answer
add comment

It's not possible to return the values without storing the results of the original function somewhere. Reasoning:

Your random number generator tells you to return these values from the original sequence: 5th, 11th, 3rd.

So you skip the first four values, return the 5th, skip another 5, return the 11th ... now how do you return the 3rd without saving it somewhere?

The closest thing you could get away with is creating a list and append all the values which you skip but that sound very awkward and probably not worth the effort. Also, it would be very slow in the case where the shuffling algorithm returns a very big and then a very small value (in which case you would effectively copy most values into the list, first, which you want to avoid).

I rest my case.

share|improve this answer
add comment

Your input is described by f(x) => x + 9, or more generally f(x) => n - 1 + x as x starts at 1.

You link to another question which describes a function r(x) which maps x to a shuffled value, 0 <= r(x) <= m.

so f(r(x) + 1) or (r(x) + n)should give you the value you want.

For small m, you also should be able to find seeds of a standard random number generator by trail and error which then generate m+1 distinct values when taken mod m+1 if you don't want to code your own generator.

share|improve this answer
add comment

Your Answer


