Take every k-th element from the (1 .. n) natural

问题:

For example, we have series 1, 2, 3, 4, 5. We take every 3 element => 3, 1, 5, 2, 4 (chosen element shouldn't remain, we can take while series is not empty). Naive implementation by circle doubly linked list is not good idea cause of performance. Can you give me an advice which data structures and algorithms are more applicable?

回答1:

Build a complete binary tree containing the numbers 1 to n, e.g. for n=15 that would be:

In each branch, store the number of nodes to the left of it; this will allow us to quickly find the i-th node. (You'll see that this tree has a very predictable structure and values, and generating it is much more efficient than building a same-sized binary tree with randomly-ordered values. It's also an ideal candidate for a tree-in-an-array.)

Then, to find the i-th number, start at the root node, and at every node, if i is one greater than the number of nodes to the left, you've found the i-th number, else go left (if i is not greater than the number of nodes to the left) or right (if i is more than 1 greater than the number of nodes to the left).

Whenever you go left, decrement the count of nodes to the left of this node (because we'll be removing one).

Whenever you go right, decrease the number you're looking for by the number of nodes to the left of the node, plus 1 (or plus 0 if the value in the node has been erased).

When you've found the i-th node, read its value (to add to the removal order list) and then set its value to 0. Thereafter, if the i-th node we're looking for has had its value erased, we'll go right and then take the leftmost node.

We start with a value i = k, and then every time we've erased the number in the i-th node, we'll decrement the total number of nodes and set i = (i + k - 1) % total (or if that is zero: i = total).

This gives a log₂N lookup time and a total complexity of N×LogN.

---

Example walk-through: with n=15 (as in the image above) and k=6, the first steps are 6, 12, 3, 10, 2. At that point the situation is:

We've just removed the second number, and now i = 2 + 6 - 1 = 7. We start at the root node, which has 4 nodes to the left of it and still has its value, so we go right and subtract 5 from the 7 we're looking for and get 2. We arrive at node 12 (which has been erased) and find there are 2 nodes to the left of it, so we decrement the number of nodes to the left of it and then go left. We come to node 10 (which has been erased) and find that it has 1 node to the left of it, and 1 = 2 - 1 so this is the node we're looking for; however, since its value has been erased, we go right and subtract 1 from the 2 we're looking for and get 1. We arrive at node 11, which has 0 nodes to the left of it (because it's a leaf), and 0 = 1 - 1, so this is the node we're looking for.

We then decrement the total number of nodes from 10 to 9, and update i from 7 to (7 + 6 - 1) % 9 = 3 and go on to find the third node (which is now the one with value 5).

---

Here's a simple implementation in JavaScript. It solves series of 100,000 numbers in less than a second, and it could probably be made faster and more space-efficient by using a tree-in-an-array structure.

(Unlike in the explanation above, the indexes of the numbers are zero-based, to simplify the code; so index 0 is the first number in the tree, and we look for the node with a number of left-connected children that equals the target index.)

function Tree(size) {                      // CONSTRUCTOR
    var height = Math.floor(Math.log(size) / Math.log(2));
    this.root = addNode(height, 1 << height, size);
    this.size = size;
    function addNode(height, value, max) { // RECURSIVE TREE-BUILDER
        var node = {value: value > max ? 0 : value, lower: (1 << height) - 1};
        if (height--) {
            node.left = addNode(height, value - (1 << height), max);
            if (value < max) {             // DON'T ADD UNNECESSARY RIGHT NODES
                node.right = addNode(height, value + (1 << height), max);
            }
        }
        return node;
    }
}
Tree.prototype.cut = function(step) {      // SEE ANSWER FOR DETAILS
    var sequence = [], index = (step - 1) % this.size;
    while (this.size) {
        var node = this.root, target = index;
        while (node.lower != target || node.value == 0) {
            if (target < node.lower) {
                --node.lower;
                node = node.left;
            } else {
                target -= node.lower + (node.value ? 1 : 0);
                node = node.right;
            }
        }
        sequence.push(node.value);
        node.value = 0;
        index = (index + step - 1) % --this.size;
    }
    return sequence;
}
var tree = new Tree(15);
var sequence = tree.cut(6);
document.write("15/6&rarr;" + sequence + "<BR>");

tree = new Tree(100000);
sequence = tree.cut(123456);
document.write("100000/123456&rarr;" + sequence);

---

NOTE:

If you look at the tree for n=10, you'll see that the node to the right of the root has an incomplete tree with 2 nodes to its left, but the algorithm as implemented in the code example above gives it an incorrect left-node count of 3 instead of 2:

However, nodes with an incomplete tree to their left never hold a value themselves, and never have nodes to their right. So you always go left there anyway, and the fact that their left-node count is too high is of no consequence.

回答2:

If you just need the last number, it's known as Josephus problem and there're well-known formulas for computing the answer in O(N) time.

I don't know if one can adapt it to run a full simulation, so I'll describe a straightforward O(N log N) solution here:

Let's keep all numbers in a treap with implicit keys. We need to find the k-th element and delete it at each step (in fact, there can be a shift, so it's more like (cur_shift + k) % cur_size, but it doesn't really matter). A treap can do it. We just need to split it into 3 parts [0, k - 1], [k, k] and [k + 1, cur_size - 1], print the number in the node that corresponds to the second part and merge the first and last part back together. It requires O(log N) time per step, so it should be good enough for the given constraints.

回答3:

Here is an implementation with an array representation of the binary tree, only storing the size of the left sub-tree as node value. The input array is not actually stored, but silently assumed to be the leaves at the bottom level, below the binary tree:

function josephusPermutation(size, step) {
    var len = 1 << 32 - Math.clz32(size-1), // Smallest power of 2 >= size
        tree = Array(len).fill(0), // Create tree in array representation 
        current = 0, 
        skip = step - 1,
        result = Array(size).fill(0),
        goRight, leftSize, order, i, j;

    // Initialise tree with sizes of left subtrees as node values
    (function init(i) {
        if (i >= len) return +(i - len < size); // Only count when within size
        var left = tree[i] = init(i*2); // recursive, only store left-size
        return left + (left ? init(i*2+1) : 0); // return sum of left and right 
    })(1);

    for (j = 0; j < result.length; j++, size--) {
        current = (current + skip) % size; // keep within range
        order = current;
        for (i = 1; i < len; i = i*2+goRight) {
            leftSize = tree[i];
            goRight = order >= leftSize;
            if (goRight) {
                order -= leftSize; // Moving rightward, counting what is at left side.
            } else {
                tree[i]--; // we will remove value at left side
            }
        }
        result[j] = 1 + i - len;
    }
    return result;
}

var sequence = josephusPermutation(100000, 123456);
console.log(sequence.join(','));

回答4:

Below is an implementation of Lei Wang and Xiaodong Wang's (2013) ¹ O(n log k) algorithm (very similar to, if not based on, the algorithm by Errol Lloyd, published in 1983). The idea is to divide the original sequence into n/m binary trees of height log k. The algorithm is actually designed for the "feline" Josephus problem, where the participants can have more than one life (listed in the array variable below, global.l).

I also like the O(1) space algorithms by Knuth, Ahrens, and Kaplansky, (outlined in a master's thesis by Gregory Wilson, California State University, Hayward, 1979²), which take a longer time to process, although can be quite fast depending on the parameters.

Knuth’s algorithm for J(n,d,t) (t is the ith hit), a descending sequence:

Let x1 = d * t and for k = 2,3,..., 
  let x_k = ⌊(d * x_(k−1) − d * n − 1) / (d − 1)⌋

Then J(n,d,t) = x_p where x_p is the first term in the sequence <= n.

Ahrens’ algorithm for J(n,d,t), an ascending sequence:

Let a1 = 1 and for k = 2,3,... 
  let a_k = ⌈(n − t + a_(k−1)) * d / (d − 1)⌉ 
If a_r is the first term in the sequence such that a_r + 1 ≥ d * t + 1 
  then J(n,d,t) = d * t + 1 − a_r.

Kaplansky’s algorithm for J(n,d,t):

Let Z+ be the set of positive integers and for k =1,2,...,t 
  define a mapping P_k : Z+ → Z+ by P_k(m) = (m+d−1)−(n−k+1)(m−k+d−1)/(n−k+1)
Then, J(n,d,t) = P1 ◦ P2 ◦···◦Pt(t).

JavaScript code:

var global = {
  n: 100000,
  k: 123456,
  l: new Array(5).fill(1),
  m: null,
  b: null,
  a: [],
  next: [],
  prev: [],
  i: 0,
  limit: 5,
  r: null,
  t: null
}

function init(params){
  global.m = Math.pow(2, Math.ceil(Math.log2(params.k)));
  params.b = Math.ceil(params.n / global.m);
      
  for (let i=0; i<params.b; i++){
    let s = i * global.m,
        t = (i + 1) * global.m,
        u = [];
        
    for (let j=0; j<global.m; j++)
      u[j] = 0;
      
    for (let j=s; j<=Math.min(t-1,params.n-1); j++)
      u[j-s] = -(j + 1);
      
    global.a[i] = [];
    build(u, global.a[i]);
    
    t = (i + 1) % params.b;
    
    params.next[i] = t;
    params.prev[t] = i;
  }
}

function build(u,v){
  function count(_v, i){
    if (global.m < i + 2){
      if (_v[i] < 0)
        return 1;
      else
        return 0;
        
    } else {
      _v[i] = count(_v, 2*i + 1);
      _v[i] = _v[i] + count(_v, 2*i + 2);
      return _v[i];
    }
  }
  
  for (let i=0; i<global.m; i++)
    v[global.m + i - 1] = u[i];
    
  count(v, 0);
}

function algorithmL(n, b){
  global.r = 0;
  global.t = b - 1;
      
  while (global.i < global.limit){
    tree(global, global);
    let j = leaf(global, global);
    hit(global.i,j,global,global);
    global.i = global.i + 1;
  }
}

function tree(params_r,params_t){
  if (params_t.t === global.next[params_t.t] && params_r.r < global.k){
    params_r.r = global.k + global.a[params_t.t][0] - 1 - (global.k - params_r.r - 1) % global.a[params_t.t][0];
  } else {
    while (params_r.r < global.k){
      params_t.t = global.next[params_t.t];
      params_r.r = params_r.r + global.a[params_t.t][0];
    }
  }
}

function size(t,j){
  if (global.a[t][j] < 0)
    return 1
  
  return global.a[t][j];
}

function leaf(params_r,params_t){
  let j = 0,
      nxt = params_r.r - global.k;
      
  while (j + 1 < global.m){
    let rs = size(params_t.t, 2*j + 2);
    if (params_r.r - rs < global.k){
      j = 2*j + 2;
    } else {
      j = 2*j + 1;
      params_r.r = params_r.r - rs;
    }
  }
  params_r.r = nxt;
  return j;
}

function hit(i,j,params_r,params_t){
  let h = -global.a[params_t.t][j];
  console.log(h);
  if (global.l[h-1] > 1)
    global.l[h-1] = global.l[h-1] - 1;
  else
    kill(i,j,params_r,params_t);
}

function kill(i,j,params_r,params_t){
  global.a[params_t.t][j] = 0;
  while (j > 0){
    j = Math.floor((j - 1) / 2);
    global.a[params_t.t][j] = global.a[params_t.t][j] - 1;
  }
  if (params_t.t !== global.next[params_t.t]){
    if (global.a[params_t.t][0] + global.a[global.next[params_t.t]][0] === global.m){
      params_r.r = params_r.r + global.a[global.next[params_t.t]][0];
      combine(params_t);
    } else if (global.a[params_t.t][0] + global.a[global.prev[params_t.t]][0] === global.m){
      t = global.prev[params_t.t];
      combine(params_t);
    }
  }
}

function combine(params_t){
  let x = global.next[params_t.t],
      i = 0,
      u = [];
  
  for (let j=0; j<global.m; j++)
    if (global.a[params_t.t][global.m + j - 1] < 0){
      u[i] = global.a[params_t.t][global.m + j - 1];
      i = i + 1;
    }
  for (let j=0; j<global.m; j++)
    if (global.a[x][global.m + j - 1] < 0){
      u[i] = global.a[x][global.m + j - 1];
      i = i + 1;
    }
  build(u,global.a[params_t.t]);
  global.next[params_t.t] = global.next[global.next[params_t.t]];
  global.prev[global.next[params_t.t]] = params_t.t;
}

init(global);
algorithmL(global.n, global.b);

(1) L. Wang and X. Wang. A Comparative Study on the Algorithms for a Generalized Josephus Problem. Applied Mathematics & Information Sciences, 7, No. 4, 1451-1457 (2013).

(2) References from Wilson (1979):

Knuth, D. E., The Art of Computer Programming, Addison-Wesley, Reading Mass., Vol I Fundamental Algorithms, 1968, Ex. 22, p158; Vol. III, Sorting and Searching, Ex. 2, pp. 18-19; Vol. I, 2-nd ed., p.181.

Ahrens, W., Mathematische Unterhaltungen und Spiele, Teubner: Leipzig, 1901, Chapter 15, 286-301.

Kaplansky, I. and Herstein I.N., Matters Mathematical, Chelsea, New York, 1978, pp. 121-128.