Permutation of a list

Let’s consider following requirement. We have list of objects, say questions, that we want to show our users. Let’s also assume that the list is very long, 500 messages.

Each message is unique and we want to

1. show each question only once for each user.
2. show the questions in different order to each user.

Each user responds to only few questions each day so it will take several months before they exhaust the list. We need to remember over each session where user left off.

Basic way to implement this is to take the list of questions, make a copy of it, shuffle it’s content and save it as part of users profile data. This has obvious drawbacks of the data duplication and maintenance. Also if the list changes, every single copy of the list has to be updated.

Cheaper way to implement this is to use prime walk. In this method we can keep only single copy of the list and store only number of answered questions in the users profile.

1. First define the list, say we have 500 items.
2. Find prime number that is greater than 500. For example 503.
3. Select seed for each user. This seed is any number that is constant for an user, like user id or time of account creation.

Then we define function that uses these values. Note that this implementation is tail-recursive for code simplicity, efficient implementation should not use recursion.

var prime = 503;
var list = ["question1", "question2", ... "question500"];

function pick_nth(seed, n, p, l) {
    if(!n) return l[seed % p];
    return pick_nth((seed + l.length) % p, n - 1, l);
}

Now picking up n:th question from list becomes easy. For example:

pick_nth(userId, 0, prime, list);  // first question
pick_nth(userId, 1, prime, list);  // second question
...
pick_nth(userId, 499, prime, list);  // 500th question

Function returns items from list in different order for every unique user id. Only thing needed to keep track of progress is to store the number of questions user has answered.

Changing list requires some care. To delete question, just mark the entry in list to null to skip it. To add questions, add another list that is used after user has exhausted the original one.
If you change the list length, the order of selection changes and it’s not anymore guaranteed that user sees every question and sees every question only once.