Javascript中Josephus置换的高效计算

Question

在代码战争的训练中，我遇到了一个关于约瑟夫排列的挑战，我试着先在纸上解决它，然后再把它翻译成代码。

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

我的主要想法是：

• 有一个辅助数组来保持响应。
• 使用两个迭代器：

- i: to keep track of current index in the given array
- k: to keep track of the step of the permutation

​

• 初始化i在0，k在1
• 当原始数组只剩下一个元素时：
  • 将元素推送到输出数组

​

• 每当我不是数组的最后一个索引时：
  • 如果k= step：
    • 将元素从原始数组中取出，将其推入输出数组，最后替换k=1。

​

- If k != step:  
    - Increment i and k

​

​

• 当我是原始数组的最后一个索引时(并且数组有多个元素)：
  • 如果k= step：
    • 将元素从原始数组中取出，将其推入输出数组，替换k=1并设置i=0。

​

- If k != step:  
    - Set i = 0 and increment 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 ms)。

样本测试如下：

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

有一次可能会被回忆录。(这似乎通过了Codewar测试。)

​

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第四个位置开始。因此，问题是在删除(i - 1)第四元素之后，在(k - 1) mod n中删除元素，然后从k开始，即(k + g(n - 1, k, i - 1)) mod n。

Answer 2

您尝试过实现功能方法吗？来自维基百科：

function getSafePosition(n) {
  // find value of L for the equation
  valueOfL = n - highestOneBit(n);
  safePosition = 2 * valueOfL + 1;

  return safePosition;
}

function highestOneBit(i) {
  i |= (i >> 1);
  i |= (i >> 2);
  i |= (i >> 4);
  i |= (i >> 8);
  i |= (i >> 16);
  return i - (i >> 1);
}

这应该在O(n)中运行。

Answer 3

你可以把领先的部分移到最后。

const josephus = (x) => parseInt(x.toString(2).substr(1) + 1, 2);