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.

Selecting biased random objects from a set

Normal random pick from set of objects will return every object equally likely.
For example, following function returns any character with equal probability from the argument string.

function randomselect(s) {
    return s[~~(Math.random() * s.length)];
}

This is usually the desired functionality, but games often require to pick one thing more likely than another. Typical use case are random drops from enemies, the common loot should drop most often and the good stuff should be much more rare.

Biased random pick is selecting object from a set randomly, so that some of them selected more often than others.

Calling randomselect("abc") will return each “a”, “b” and “c” with 33% probability.
Selection can be biased by just adding more of characters in the string. Calling randomselect("aaabbc") will return “a” with 50%,”b” with 33% and “c” with 16% propability.

Just adding entries in a list is bit clumsy, and more generic method is to use integral of probability density.

// define elements and probability for each
var elems = [
  ['a', 0.5],
  ['b', 0.333],
  ['c', 0.166]
]

// Biased random entry selection
function select(elems) {
    var r = Math.random();
    var ref = 0;

    for(var i=0; i < elems.length; i++) {
        var elem= elems[i];
        ref += elem[1];
        if (r < ref) return elem[0];
    }
    // This happens only if probabilities do not add up to 1
    return null;
}

Calling select(elems) returns a with 50%, b with 33.3% and c with 16.6% probability.
If defined probabilities do not sum to 1 you can get null, i.e not selection. In this case 0.5 + 0.333 + 0.166 is 0.999 so there is 0.1% probability (one out 1000) to get nothing.

For example to pick 100 times randomly from the set.

var elems = [
  ['a', 0.5],
  ['b', 0.333],
  ['c', 0.166]
];

var s = '';
for(var i=0; i < 100; i++) {
	s += select(elems);
}
console.log(s);

Run this with node to get string of randomly picked characters. Here you can see that selection bias works, half of the letters are ‘a’, one third ‘b’ and rest ‘c’.

$ node biased.js
babbaaaabaabbaabaccbaacabbbabbacbaabacabccacacacbacaaaaacbcaaaababaccbcbbbcaabcaabaccabbbcbcbacaabaa