Calculating Josephus Permutations efficiently in Javascript

Question

While training in code-wars I came across a challenge about Joseph-permutations, I tried solving it on paper first and latter translate it to code.

The problem is as follows: "Create a function that returns a Josephus permutation, taking as parameters the initial array/list of items to be permuted as if they were in a circle and counted out every k places until none remained."

My main idea was:

• Have an auxiliary array to keep the response

• Use two iterators:

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

• Initialize i at 0 and k at 1

• When the original array has only one element left:
  • Push element to output array
• Whenever i is not the last index of the array:
  • If k = step:
    • Take the element out of the original array, push it into the output array and finally replace k = 1
  • If k != step:
    • Increment i and k
• When i is the last index of the original array (and the array has more than one element):
  • If k = step:
    • Take the element out of the original array, push it into the output array, replace k = 1 and set 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;
}

This works but it's not efficient, when I run it on the run sample tests I get that 5 of the sample tests have passed but it also includes an STDERR: Execution Timed Out (12000 ms).

The sample tests are the following ones:

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),[])

My question is, how could I make this more efficient?

Is it the algorithm that I'm using that's wrong or is it the implementation?

A comment mentioned two things:

• push() is very slow, which was one of my possibilities (wrong data structure)

• suggested looking at recursion (which goes more into my doubt about the algorithm). I'm not really seeing how to make this recursive though.

Thanks in advance for your help!

Answer 1

There's a recurrence, which could be memoized. (This seems to pass the Codewars tests.)

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);

To explain the recurrence, the first element removed (when i = 1) is clearly (k - 1) mod n (zero-indexed). Now consider finding g(n, k, i). The first element that gets removed is (k - 1) mod n and then we start at the kth position. So the problem is then to find the (i - 1)th element removed after removing the element at (k - 1) mod n and starting at k, which is (k + g(n - 1, k, i - 1)) mod n.

Answer 2

have you tried implementing the functional approach? from wikipedia:

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);
}

this should run in O(n)

Answer 3

You could shift the leading bit to the end.

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