javascript - 在 Javascript 中有效地计算 Josephus 排列

Question

在进行代码大战训练时，我遇到了关于约瑟夫排列的挑战，我尝试先在纸上解决它，然后再将其转化为代码。

问题如下:“创建一个返回 Josephus 排列的函数，将要排列的项目的初始数组/列表作为参数，就像它们在一个圆圈中一样，并计算出每 k 个位置，直到没有剩余。”

我的主要想法是:

• 有一个辅助数组来保持响应

• 使用两个迭代器:

  • i: 跟踪给定数组中的当前索引
  • k:跟踪排列的步骤

• 将 i 初始化为 0，将 k 初始化为 1

• 当原数组只剩下一个元素时:
  • 将元素压入输出数组
• 每当 i 不是数组的最后一个索引时:
  • 如果 k = 步骤:
    • 从原数组中取出元素，压入输出数组最后替换k = 1
  • 如果 k != 步骤:
    • 递增 i 和 k
• 当 i 是原数组的最后一个索引时(并且数组有多个元素):
  • 如果 k = 步骤:
    • 从原数组中取出元素，压入输出数组，替换k = 1，设置i = 0
  • 如果 k != 步骤:
    • 设置 i = 0 并递增 k

function josephus(items,step){
  var output = [];
  var i = 0;
  var k = 1;
  if( items == [] ) {
    return [];
  }
  while (items.length != 1) {
    if        (k == step && i == items.length - 1) {
      output.push(items[i]); 
      items.splice(i, 1);
      i = 0;
      k = 1;
    } else if (k == step && i != items.length - 1) {
      output.push(items[i]);
      items.splice(i, 1);
      k = 1
    } else if (k < step && i == items.length - 1) {
      k++;
      i=0;
    } else if (k < step && i != items.length - 1) {
      k++;
      i++;
    }
  }
  output.push(items[0]);
  return output;
}

这有效但效率不高，当我在运行示例测试中运行它时，我得到 5 个示例测试已通过，但它还包括一个 STDERR:执行超时(12000 毫秒)。

示例测试如下:

Test.assertSimilar(josephus([1,2,3,4,5,6,7,8,9,10],1),[1,2,3,4,5,6,7,8,9,10])
Test.assertSimilar(josephus([1,2,3,4,5,6,7,8,9,10],2),[2, 4, 6, 8, 10, 3, 7, 1, 9, 5])
Test.assertSimilar(josephus(["C","o","d","e","W","a","r","s"],4),['e', 's', 'W', 'o', 'C', 'd', 'r', 'a'])
Test.assertSimilar(josephus([1,2,3,4,5,6,7],3),[3, 6, 2, 7, 5, 1, 4])
Test.assertSimilar(josephus([],3),[])

我的问题是，我怎样才能使它更有效率？

是我使用的算法有误还是实现？

一条评论提到了两件事:

• push() 非常慢，这是我的一种可能性(错误的数据结构)

• 建议查看递归(这让我更加怀疑算法)。不过，我并没有真正看到如何使这个递归。

预先感谢您的帮助!

Answer 1

有重现，可以内存。 (这似乎通过了 Codewars 测试。)

function g(n, k, i, memo){
  if (memo.hasOwnProperty([n, k, i]))
    return memo[[n, k, i]];
    
  if (i == 1)
    return memo[[n, k, i]] = (k - 1) % n;
    
  return memo[[n, k, i]] =
    (k + g(n - 1, k, i - 1, memo)) % n; 
}

function f(A, k){
  let n = A.length;
  let result = new Array(n);
  let memo = {};
  
  for (let i=1; i<=n; i++)
    result[i - 1] = A[ g(n, k, i, memo) ];
  
  return result;
}

let str = '';

str +=  JSON.stringify(f([1,2,3,4,5,6,7,8,9,10],1)) + '\n';
//[1,2,3,4,5,6,7,8,9,10])

str += JSON.stringify(f([1,2,3,4,5,6,7,8,9,10],2)) + '\n';
//[2, 4, 6, 8, 10, 3, 7, 1, 9, 5])

str += JSON.stringify(f(["C","o","d","e","W","a","r","s"],4)) + '\n';
//,['e', 's', 'W', 'o', 'C', 'd', 'r', 'a'])

str += JSON.stringify(f([1,2,3,4,5,6,7],3)) + '\n';
//,[3, 6, 2, 7, 5, 1, 4])

str += JSON.stringify(f([],3))
//,[])

console.log(str);

为了解释递归，删除的第一个元素(当 i = 1 时)显然是 (k - 1) mod n(零索引)。现在考虑寻找g(n, k, i)。第一个被移除的元素是 (k - 1) mod n 然后我们从第 k 位置开始。所以问题是在删除 (k - 1) mod n 处的元素并从 k< 开始后，找到删除的第 (i - 1) 个元素，即 (k + g(n - 1, k, i - 1)) mod n。