persist random items with no duplicates in constant time

Question

I've a an array in which I take out random items

[a, b, c, d ,...]

function getRandomItem(){
   // return random item from array
}

I also have a SQL table like so :

category_id
random_item

Then I want to add that item to the table. For every category_id, I want multiple rows of random item such as:

• There is no duplicate items in each category (item a cannot figure twice with the category_id 1, but item a can be in category_id 1 and category_id 2)
• The number of items will be smaller than length of the array. (That's not a requirement that'll just be always the case).

---

Here is some imaginary code that do just that:

function persist(){
    var a = giveRandomItem();
    // $1 = a
    return execute("INSERT INTO mytable (random_item) values ($1) ON CONFLICT DO NOTHING RETURNING *", a)
}

 // usage
 var persisted;
 while(persisted === undefined){
    persisted = persist();
 }

The problem with this is that it's not constant time. There is a probability that I hit the DB 5 times in a row because the item has already been persisted.

For each category I expect max 5k items and my array length is 400 000. So the probability is quite low though.

I'd like to find a way that is constant time nevertheless, or at least have a sql command that would try multiple values, so as to lower the probability further.

---

Use case

A simple use case I can think of is this (it is useless but simple):

Users are presented with an interface where they can select a category. Then they can press a button that adds a random item to it. There are multiple users, each acting individually. So user 1 can add a random item to category 1 while user 2 simultaneously adds a random item to category 2

EDIT

I ended up doing something like this:

At the application level:

shuffle(array);

function getRandomItem(seed, inc){
   let index = (seed + inc) % array.length;
   return array[index]
}

// usage:

let seed = item.category_id
let inc = category.item_count

This way I've no duplicates since I said the count of items was lower than the length of the array. Also the items are seemingly random because the id of the category is used as a seed for the start of the increment. However that's only for the starting point and it's therefore not really random but that works for my use case.

Answer 1

To guarantee that you don't experience conflicts (unique constraint violations) you should change your approach. Instead of generating one random item at a time you should generate all 5K items at once (and then insert them in bulk). Inserting in bulk would also speed things up considerably.

How to generate 5K random items out of array of 400K items?

One way is to shuffle the array and take first 5K elements. Then the next 5K elements, and so on. This would also guarantee that separate batches don't have repeating elements (until all 400K are exhausted and you start from the beginning of the array again).

If you want elements to have a chance to be repeated between batches, then re-shuffle array between the batches.

---

After discussion in the comments, it looks like you need an algorithm that generates Cyclic permutations. For each category store in the DB the starting seed/internal state of this algorithm to know how to continue picking elements of 400K array in such a way that they look random, but don't repeat until all 400K elements for the category are picked.