title: Calculating Josephus Permutations efficiently in Javascript
body: <p>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.</p>
  
  <p>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."</p>
  
  <p>My main idea was:</p>
  
  <ul>
  <li>Have an auxiliary array to keep the response</li>
  <li><p>Use two iterators:</p>
  
  <ul>
  <li>i: to keep track of current index in the given array</li>
  <li>k: to keep track of the step of the permutation</li>
  </ul></li>
  <li><p>Initialize i at 0 and k at 1</p></li>
  <li>When the original array has only one element left:
  
  <ul>
  <li>Push element to output array</li>
  </ul></li>
  <li>Whenever i is not the last index of the array:
  
  <ul>
  <li>If k = step:
  
  <ul>
  <li>Take the element out of the original array, push it into the output array and finally replace k = 1</li>
  </ul></li>
  <li>If k != step:
  
  <ul>
  <li>Increment i and k</li>
  </ul></li>
  </ul></li>
  <li>When i is the last index of the original array (and the array has more than one element):
  
  <ul>
  <li>If k = step:
  
  <ul>
  <li>Take the element out of the original array, push it into the output array, replace k = 1 and set i = 0</li>
  </ul></li>
  <li>If k != step:
  
  <ul>
  <li>Set i = 0 and increment k</li>
  </ul></li>
  </ul></li>
  </ul>
  
  <pre><code>function josephus(items,step){
    var output = [];
    var i = 0;
    var k = 1;
    if( items == [] ) {
      return [];
    }
    while (items.length != 1) {
      if        (k == step &amp;&amp; i == items.length - 1) {
        output.push(items[i]); 
        items.splice(i, 1);
        i = 0;
        k = 1;
      } else if (k == step &amp;&amp; i != items.length - 1) {
        output.push(items[i]);
        items.splice(i, 1);
        k = 1
      } else if (k &lt; step &amp;&amp; i == items.length - 1) {
        k++;
        i=0;
      } else if (k &lt; step &amp;&amp; i != items.length - 1) {
        k++;
        i++;
      }
    }
    output.push(items[0]);
    return output;
  }
  </code></pre>
  
  <p>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).</p>
  
  <p>The sample tests are the following ones:</p>
  
  <pre><code>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),[])
  </code></pre>
  
  <p>My question is, how could I make this more efficient? </p>
  
  <p>Is it the algorithm that I'm using that's wrong or is it the implementation?</p>
  
  <p>A comment mentioned two things: </p>
  
  <ul>
  <li><p>push() is very slow, which was one of my possibilities (wrong data structure) </p></li>
  <li><p>suggested looking at recursion (which goes more into my doubt about the algorithm). I'm not really seeing how to make this recursive though.</p></li>
  </ul>
  
  <p>Thanks in advance for your help!</p>