Calculating Josephus Permutations efficiently in Javascript

user_11688399 0
Viewed 1154

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!

josephus permutation arrays algorithm javascript
3 Answers

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.

user_20347870

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)

user_72814470

You could shift the leading bit to the end.

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