Looking for an algorithm that splashes 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 saving the numbers ahead of time, I want to create a function f (), which sets the sequence {1,2,3, ... m}, will spit out the original set in a random (or at least pseudo random) order.

For example, suppose 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 some point in the past, an employee showed me a mathematical algorithm that could do this, but since then I forgot almost everything about it, except that it existed. I remember that you had to have a sequence in advance and generate some constants from the sequence that were used in the function. And for those who wondered, I, unfortunately, lost contact with this employee.

This question answers almost the way I want, but I'm not sure if the answers allow me to limit the output to a certain sequence ahead of time.

---

Edit:

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

What is disappointing is that I saw this, I just can't remember enough to find it again with Google.

The Fisher-Yates algorithm is great for swapping or shuffling the deck, but that's not what I'm looking for.

Answer 1

There is a simple function that generates a permutation [0..m-1] for a given m . Just pick a number k , relatively simple with m and f(i)=(k*i) mod m . This always creates a permutation (no repetitions at 0<=i<m ). It works better if k greater than m .

For example, m = 20, 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 regarding its statistical properties.

Answer 2

Your question is a bit confusing, as it seems like you want to return the entire original sequence, but then you have both 4 and 8 mappings to 10 and nothing is mapped to 12.

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

Also note that n does not matter. You can always use 0,1,2, ... m, and then add n to everything if necessary.

Assuming I interpreted this correctly, and you are really looking for a shuffle algorithm (like random shuffling called shuffling, similar to shuffling a deck of cards), check out Fisher-Yates

[Edit] Well, based on your update, the problem you are facing is this: you do not want to explicitly encode the permutation, but you must somehow encode it in order to build f. The easiest way is to simply save the rearranged indexes in an array, but if you do not want to do this for any reason (for example, too large), you can encode it in various ways. However, there is no free lunch, as there are theoretical limits to how simple it is. In any case, you can get some ideas from finding work on “coding permutations,” for example, something like in this article

Answer 3

This question is similar to shuffling the deck (m + 1) of cards numbered [n, ..., n + m]. Note that numbering (and therefore n ) is unimportant; what matters is that we can split the cards. (If you want, you can simply add n back later.)

To do what you want, you can run the Fisher-Yates shuffle and just keep track of which indexes have been selected for the shuffle so far. This will allow you to avoid saving another copy of the values ​​themselves on request.

Answer 4

Here is some kind of pseudo code in my own 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 

Answer 5

add initial values ​​to the list. Then use a random number to select a new index value in the range of the current list size. Use this index to select and then remove a number from the list.

as someone already pointed out, this is like having a deck of cards, and then accidentally deleting one card at a time.

Answer 6

If you want to match 1: 1, go with Fisher-Yates as indicated in the other answers.

If you do not need to display 1: 1, and you want all the values ​​received to be from a given sequence (with the possibility of repetitions), you can use a random function with the specified range.

For example, in C ++ you can use rand () as follows:

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

So for your example

 result = rand() % 8 + 10 

Creates an integer from 10 to 17.

Answer 7

You can set the polynomial in the selected sequence; I would have guessed what your colleague showed you. This will not save space compared to just remembering the permutation.

Answer 8

You can generate a permutation of the first n integers using a block cipher and xOR folding, according to my previous answer .

Answer 9

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

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

therefore f(r(x) + 1) or (r(x) + n) should provide you with the required value.

For small m you should also find the seeds of the standard random number generator along the path and error, which then generate m+1 different values ​​when taking mod m+1 if you do not want to code your own generator.

Answer 10

It is not possible to return values ​​without saving the results of the original function. Justification:

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 the 5th, return the 11th ... now, how do you return the 3rd without saving it somewhere?

The closest thing you can get away is to create a list and add all the values ​​you miss, but that sounds very uncomfortable and probably not worth the effort. In addition, it would be very slow in the case where the shuffling algorithm returns a very large and then a very small value (in this case, you efficiently copy most of the values ​​to the list, first of all, what you want to avoid).

I will leave my case.