从 (1 .. n) 自然数系列中取出每个第 k 个元素
Take every k-th element from the (1 .. n) natural numbers series
例如，我们有系列 1、2、3、4、5。我们取每 3 个元素 =>
3, 1, 5, 2, 4（选择的元素不应该保留，我们可以在系列不为空时取）。循环双向链表的简单实现不是性能的好主意。你能给我一个建议，哪些数据结构和算法更适用？
这是一个用二叉树的数组表示的实现，只存储左子树的大小作为节点值。输入数组实际上并没有存储，而是默认为二叉树下方最底层的叶子：
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(','));
如果您只需要最后一个数字，它被称为 Josephus problem 并且有众所周知的公式可以在 O(N) 时间内计算出答案。
我不知道是否可以将它改编成 运行 一个完整的模拟，所以我将在这里描述一个简单的 O(N log N) 解决方案：
让我们用隐式键将所有数字保存在一个陷阱中。我们需要找到第 k 个元素，并在每一步删除它（实际上，可以有一个移位，所以它更像是 (cur_shift + k) % cur_size，但这并不重要）。一个陷阱可以做到。我们只需要将其拆分为 [0, k - 1]、[k, k] 和 [k + 1, cur_size - 1] 三个部分，打印与第二部分对应的节点中的数字，并将第一部分和最后一部分合并在一起。每一步需要 O(log N) 时间，因此对于给定的约束应该足够好了。
构建一棵包含数字 1 到 n 的 complete 二叉树，例如对于 n=15 那将是：
在每个分支中，存储其左侧的节点数；这将使我们能够快速找到 i-th 节点。 (你会看到这棵树有一个非常可预测的结构和值，生成它比构建一个 same-sized 具有 randomly-ordered 值的二叉树更有效。这也是一个理想的选择tree-in-an-array.)
的候选人
然后，要找到 i-th 数，从根节点开始，在每个节点，如果 i 比左边的节点数大 1，则找到 i-th number，否则向左（如果 i 不大于左侧的节点数）或向右（如果 i 大于 1 大于左侧的节点数）。
每当您向左移动时，减少该节点左侧的节点数（因为我们将删除一个节点）。
每当您向右走时，将要查找的数字减去该节点左侧的节点数，再加上 1（如果节点中的值已被删除，则加 0）。
当你找到 i-th 节点时，读取它的值（添加到移除顺序列表）然后将它的值设置为 0。此后，如果 i-th 节点我们'如果要查找的值已被删除，我们将向右走，然后取最左边的节点。
我们从一个值 i = k 开始，然后每次我们擦除 i-th 节点中的数字时，我们都会减少节点总数并设置 i = (i + k - 1) % total (或者如果它为零：i = total）。
这给出了 log2N 的查找时间和 N×LogN 的总复杂度。
示例walk-through：n=15（如上图所示）和k=6，第一个步骤是 6、12、3、10、2。此时情况是：
我们刚刚删除了第二个数字，现在 i = 2 + 6 - 1 = 7。我们从根节点开始，它的左边有 4 个节点并且仍然有它的值，所以我们向右移动并从我们正在寻找的 7 中减去 5 得到 2。我们到达节点 12（已经erased) 发现它的左边有2个节点，所以我们减少它左边的节点数然后向左走。我们来到节点10（已经被擦除），发现它的左边还有1个节点，1 = 2 - 1 所以这就是我们要找的节点；然而，由于它的值已被擦除，我们向右移动并从我们正在寻找的 2 中减去 1 并得到 1。我们到达节点 11，它的左侧有 0 个节点（因为它是叶子），并且0 = 1 - 1，所以这就是我们要查找的节点。
然后我们将节点总数从 10 减少到 9，并将 i 从 7 更新为 (7 + 6 - 1) % 9 = 3 并继续寻找第三个节点（现在是值为 5 的节点）。
JavaScript 中有一个简单的实现。它在不到一秒的时间内解决了 100,000 个数字的系列，并且可以通过使用 tree-in-an-array 结构使其变得更快和更多 space-efficient。
（与上面的解释不同，数字的索引是zero-based，以简化代码；所以索引0是树中的第一个数字，我们寻找left-connected children 等于目标索引的节点。）
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→" + sequence + "<BR>");
tree = new Tree(100000);
sequence = tree.cut(123456);
document.write("100000/123456→" + sequence);
注意：
如果您查看 n=10 的树，您会看到根右侧的节点有一个不完整的树，其左侧有 2 个节点，但是上面代码示例中实现的算法给它一个不正确的 left-node 计数 3 而不是 2：
但是，左边有不完整树的节点本身永远不会保存值，右边也永远不会有节点。所以无论如何你总是向左走，他们的 left-node 计数太高这一事实无关紧要。
下面是 Lei Wang 和 Xiaodong Wang (2013) 1 O(n log k) 算法的实现（即使不是基于 Errol Lloyd 的算法，也非常相似） , 1983 年出版).思路是将原始序列分成n/m个高度log k的二叉树。该算法实际上是针对"feline" Josephus问题设计的，其中参与者可以有不止一次的生命（列在下面的数组变量中，global.l）。
我也喜欢 Knuth、Ahrens 和 Kaplansky 的 O(1) space 算法（在 Gregory Wilson 的硕士论文中概述，加利福尼亚州立大学，海沃德，1979 2)，这需要更长的时间来处理，但根据参数的不同可能会非常快。
Knuth 的 J(n,d,t) 算法（t 是 ith 命中），降序序列：
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 的 J(n,d,t) 算法，升序：
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 算法 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代码：
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 和 X. Wang。广义 Josephus 问题算法的比较研究。 应用数学与信息科学, 7, No. 4, 1451-1457 (2013).
(2) 威尔逊 (1979) 的参考资料：
Knuth, D.E.，计算机编程艺术，Addison-Wesley，Reading Mass.，第一卷基础算法，1968 年，Ex. 22，第 158 页；卷。 III，排序和搜索，Ex。 2，第 18-19 页；卷。 I，第 2 版，第 181 页。
Ahrens, W., Mathematische Unterhaltungen und Spiele, Teubner: Leipzig, 1901, Chapter 15, 286-301.
Kaplansky, I. 和 Herstein I.N., Matters Mathematical, Chelsea, New York, 1978, pp. 121-128.
例如，我们有系列 1、2、3、4、5。我们取每 3 个元素 => 3, 1, 5, 2, 4（选择的元素不应该保留，我们可以在系列不为空时取）。循环双向链表的简单实现不是性能的好主意。你能给我一个建议，哪些数据结构和算法更适用？
这是一个用二叉树的数组表示的实现，只存储左子树的大小作为节点值。输入数组实际上并没有存储，而是默认为二叉树下方最底层的叶子：
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(','));
如果您只需要最后一个数字，它被称为 Josephus problem 并且有众所周知的公式可以在 O(N) 时间内计算出答案。
我不知道是否可以将它改编成 运行 一个完整的模拟，所以我将在这里描述一个简单的 O(N log N) 解决方案：
让我们用隐式键将所有数字保存在一个陷阱中。我们需要找到第 k 个元素，并在每一步删除它（实际上，可以有一个移位，所以它更像是 (cur_shift + k) % cur_size，但这并不重要）。一个陷阱可以做到。我们只需要将其拆分为 [0, k - 1]、[k, k] 和 [k + 1, cur_size - 1] 三个部分，打印与第二部分对应的节点中的数字，并将第一部分和最后一部分合并在一起。每一步需要 O(log N) 时间，因此对于给定的约束应该足够好了。
构建一棵包含数字 1 到 n 的 complete 二叉树，例如对于 n=15 那将是：
在每个分支中，存储其左侧的节点数；这将使我们能够快速找到 i-th 节点。 (你会看到这棵树有一个非常可预测的结构和值，生成它比构建一个 same-sized 具有 randomly-ordered 值的二叉树更有效。这也是一个理想的选择tree-in-an-array.)
的候选人然后，要找到 i-th 数，从根节点开始，在每个节点，如果 i 比左边的节点数大 1，则找到 i-th number，否则向左（如果 i 不大于左侧的节点数）或向右（如果 i 大于 1 大于左侧的节点数）。
每当您向左移动时，减少该节点左侧的节点数（因为我们将删除一个节点）。
每当您向右走时，将要查找的数字减去该节点左侧的节点数，再加上 1（如果节点中的值已被删除，则加 0）。
当你找到 i-th 节点时，读取它的值（添加到移除顺序列表）然后将它的值设置为 0。此后，如果 i-th 节点我们'如果要查找的值已被删除，我们将向右走，然后取最左边的节点。
我们从一个值 i = k 开始，然后每次我们擦除 i-th 节点中的数字时，我们都会减少节点总数并设置 i = (i + k - 1) % total (或者如果它为零：i = total）。
这给出了 log2N 的查找时间和 N×LogN 的总复杂度。
示例walk-through：n=15（如上图所示）和k=6，第一个步骤是 6、12、3、10、2。此时情况是：
我们刚刚删除了第二个数字，现在 i = 2 + 6 - 1 = 7。我们从根节点开始，它的左边有 4 个节点并且仍然有它的值，所以我们向右移动并从我们正在寻找的 7 中减去 5 得到 2。我们到达节点 12（已经erased) 发现它的左边有2个节点，所以我们减少它左边的节点数然后向左走。我们来到节点10（已经被擦除），发现它的左边还有1个节点，1 = 2 - 1 所以这就是我们要找的节点；然而，由于它的值已被擦除，我们向右移动并从我们正在寻找的 2 中减去 1 并得到 1。我们到达节点 11，它的左侧有 0 个节点（因为它是叶子），并且0 = 1 - 1，所以这就是我们要查找的节点。
然后我们将节点总数从 10 减少到 9，并将 i 从 7 更新为 (7 + 6 - 1) % 9 = 3 并继续寻找第三个节点（现在是值为 5 的节点）。
JavaScript 中有一个简单的实现。它在不到一秒的时间内解决了 100,000 个数字的系列，并且可以通过使用 tree-in-an-array 结构使其变得更快和更多 space-efficient。
（与上面的解释不同，数字的索引是zero-based，以简化代码；所以索引0是树中的第一个数字，我们寻找left-connected children 等于目标索引的节点。）
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→" + sequence + "<BR>");
tree = new Tree(100000);
sequence = tree.cut(123456);
document.write("100000/123456→" + sequence);
注意：
如果您查看 n=10 的树，您会看到根右侧的节点有一个不完整的树，其左侧有 2 个节点，但是上面代码示例中实现的算法给它一个不正确的 left-node 计数 3 而不是 2：
但是，左边有不完整树的节点本身永远不会保存值，右边也永远不会有节点。所以无论如何你总是向左走，他们的 left-node 计数太高这一事实无关紧要。
下面是 Lei Wang 和 Xiaodong Wang (2013) 1 O(n log k) 算法的实现（即使不是基于 Errol Lloyd 的算法，也非常相似） , 1983 年出版).思路是将原始序列分成n/m个高度log k的二叉树。该算法实际上是针对"feline" Josephus问题设计的，其中参与者可以有不止一次的生命（列在下面的数组变量中，global.l）。
我也喜欢 Knuth、Ahrens 和 Kaplansky 的 O(1) space 算法（在 Gregory Wilson 的硕士论文中概述，加利福尼亚州立大学，海沃德，1979 2)，这需要更长的时间来处理，但根据参数的不同可能会非常快。
Knuth 的 J(n,d,t) 算法（t 是 ith 命中），降序序列：
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 的 J(n,d,t) 算法，升序：
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 算法 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代码：
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 和 X. Wang。广义 Josephus 问题算法的比较研究。 应用数学与信息科学, 7, No. 4, 1451-1457 (2013).
(2) 威尔逊 (1979) 的参考资料：
Knuth, D.E.，计算机编程艺术，Addison-Wesley，Reading Mass.，第一卷基础算法，1968 年，Ex. 22，第 158 页；卷。 III，排序和搜索，Ex。 2，第 18-19 页；卷。 I，第 2 版，第 181 页。
Ahrens, W., Mathematische Unterhaltungen und Spiele, Teubner: Leipzig, 1901, Chapter 15, 286-301.
Kaplansky, I. 和 Herstein I.N., Matters Mathematical, Chelsea, New York, 1978, pp. 121-128.