Algorithm or formula that can take an incrementing counter and make it appear uniquely random

Question

I am wondering if there is a general formula of some sort that can take a single incrementing integer, and run it through a modulus sort of thing to shift it to a random place, so as you increment the counter, its output value jumps around and appears random, yet no value is ever hit twice. Assuming some limit on the set of numbers like 16-bit integers (65536 integers), or 32-bit integers, etc.. Perhaps there is a way to spiral numbers down somehow, I don't know. The sequence would be predictable, but to a layman it would appear random without thinking much of it.

For example, you can multiply a number by 2 to make it not appear directly incremented. But that's not very sophisticated. You could perhaps start the number at the middle of the set (like 30103 for 16-bit integers), then multiply by 2 and rotate the numbers using a modulus, and this would appear even less incremented. But you could still see a pattern.

I'm wondering what sorts of patterns or equations you could run an incremented number through (in a bounded set of integers) so that the output appears the least predictable as possible, and at the same time it never hits the same number twice. This way you could make IDs appear randomly generated to the layman without having to store all the IDs in a database in random order in advance. The formula would generate them from a single stored integer. What is possible in this regard, and what is the equation? How far can it theoretically go?

Maybe you could make the set odd, and skip every 20th number, and somehow prove that it will eventually revolve through the whole set without repeats. I can't figure this out though.

Update: This seems to be in the field of pseudorandom number generation, like this, but I'm not sure if they fit the added constraint of never repeating the number.

Here is what I found and implemented, but it's giving some duplicates :/.

const fetch = (x, o) => {
  if (x >= o) {
    return x
  } else {
    const v = (x * x) % o
    return (x <= o / 2) ? v : o - v
  }
}

const fetch32 = (x) => fetch(x, 4294967291)
const fetch16 = (x) => fetch(x, 65519)
const fetch8 = (x) => fetch(x, 251)

// the last number can be anything.
const build32 = (x, o) => fetch32((fetch32(x) + o) ^ 1542469173)
const build16 = (x, o) => fetch16((fetch16(x) + o) ^ 42703)
const build8 = (x, o) => fetch8((fetch8(x) + o) ^ 101)

let i = 0
let n = Math.pow(2, 32)
while (i < n) {
  let j = 0
  let r = {}
  while (j < n) {
    let x = build32(j, i)
    if (r[x]) throw `${i}:${j}:${x}`
    r[x] = true
    j++
  }
  i++
}

The other linked question in the comment doesn't show a JavaScript implementation that adheres the the uniqueness constraint.

Answer 1

If you are looking for a sequence, where one value is produced from knowing what the previous value was, then what you are looking for could be a Linear congruential generator, with a modulus of a power of 2. There are a few parameters involved:

• m: the modulus, which in your case is 2⁸, 2¹⁶, or 2³².
• a: the multiplier. To ensure that all values are produced before the first duplicate is generated, this must be a multiple of 4 plus 1 (assuming m is a power of 2).
• c: the increment. It must be odd.

You can play with these numbers to arrive at a series that you are satisfied with in terms of "randomness".

The above referenced Wikipedia article lists some parameter choices that are used in some pseudo random generators. I have just selected a=97 and c some odd number half way the range.

Here is some code to prove the uniqueness:

/*
    Assuming that m is a power of 2:
    - c must be odd
    - a % 4 must be 1
*/
function createFetch(m, a, c) { // Returns a function
     return x => (a * x + c) % m;
}
const m = 2**16;
const fetch16 = createFetch(m, 97, (m>>1)-1);

const r = new Set;
let x = 1;
for (let i = 0; i < m; i++) {
    x = fetch16(x);
    if (i < 10) console.log(x);
    if (r.has(x)) throw `${i}:${x}`
    r.add(x);
}
console.log("...");
console.log(`generated ${r.size} unique numbers`);

NB/ this is a good use case for a generator, which in JavaScript looks like this:

function * fetch(m, a, c, x=1) {
     while (true) {
         x = (a * x + c) % m;
         yield x;
     }
}
const m = 2**16;
const fetch16 = fetch(m, 97, (m>>1)-1);

const r = new Set;
for (let i = 0; i < m; i++) {
    x = fetch16.next().value;
    if (i < 10) console.log(x);
    if (r.has(x)) throw `${i}:${x}`
    r.add(x);
}
console.log("...");
console.log(`generated ${r.size} unique numbers`);

Answer 2

Any block cipher whose block size is n bits is a permutation of {0,1,2, ..., 2ⁿ-1}. Thus, if E is such a block cipher and k is a valid key for E, then E_k(0), E_k(1), ..., E_k(2ⁿ-1) are all distinct. If the block cipher is good then the values appear "random" to the naked eye. If you change the key k you get a different permutation.

This is actually mentioned in the link you provided.

Consider this answer as well.

Answer 3

var bottomLimit = 1
var topLimit = 10
var arr = []
for (var i = bottomLimit; i < topLimit; i++) {
  arr.push(i)
}
arr = shuffle(arr);
console.log(arr);

//https://stackoverflow.com/questions/2450954/how-to-randomize-shuffle-a-javascript-array#answer-2450976
function shuffle(array) {
  var currentIndex = array.length,
    temporaryValue, randomIndex;

  while (0 !== currentIndex) {

    randomIndex = Math.floor(Math.random() * currentIndex);
    currentIndex -= 1;

    temporaryValue = array[currentIndex];
    array[currentIndex] = array[randomIndex];
    array[randomIndex] = temporaryValue;
  }

  return array;
}

Answer 4

Well,you can generate random no. inside the range of two no.

 public static int getRandomVal(int min, int max) {
    Random random = new Random();

    return random.nextInt((max - min) + 1) + min;
}

public static void getRandomNumbers(int size, int min,
        int max) {
    ArrayList<Integer> numbers = new ArrayList<Integer>();

    while (numbers.size() < size) {
        int random = getRandomVal(min, max);

        if (!numbers.contains(random)) {
            numbers.add(random);
            System.out.println(" "+random);
        }
    }
}

now to generate 10 different no. between 50 and 100 you can use

getRandomNumbers(10, 50,100);

This approach is very easy I am creating an array and just checking the random value if it is already present or not. If it is not present I am pushing it to the array and outputting it.

Answer 5

Get yourself a seeded random number generator.

Seed with 1, return next random number. Seed with 2, return next random number. Seed with 3, return next random number... If you seed with an integer then the next random number will be repeatable and pseudo random.