Looking for an algorithm to spit out a sequence of numbers in a (pseudo) random order

Question

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.

---

Edit:

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.

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

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]
        a.remove(position)
        newArray.insertAtEnd(removedNumber)
    end while
    return newArray