Эффективный расчет перестановок Иосифа в Javascript - PullRequest
Новая
       33

Эффективный расчет перестановок Иосифа в Javascript

4 голосов
/ 23 июня 2019

Во время обучения кодовым войнам я столкнулся с проблемой перестановок Джозефа, сначала я попытался решить ее на бумаге, а затем перевести в код.

Проблема заключается в следующем: «Создайте функцию, которая возвращает перестановку Джозефуса, принимая в качестве параметров исходный массив / список элементов, подлежащих перестановке, как если бы они были в круге, и отсчитывал каждые k мест, пока не осталось ни одного».

Моя главная идея была:

  • иметь вспомогательный массив для хранения ответа

  • Используйте два итератора:

    • i: отслеживать текущий индекс в данном массиве
    • k: для отслеживания шага перестановки

  • Инициализировать i в 0 и k в 1

  • Когда в исходном массиве остается только один элемент:
    • Вставить элемент в выходной массив
  • Всякий раз, когда я не последний индекс массива:
    • Если k = шаг:
      • Извлеките элемент из исходного массива, вставьте его в выходной массив и, наконец, замените k = 1
    • Если k! = Step:
      • Инкремент i и k
  • Когда i - последний индекс исходного массива (и массив имеет более одного элемента):
    • Если k = шаг:
      • Извлеките элемент из исходного массива, вставьте его в выходной массив, замените k = 1 и установите i = 0
    • Если k! = Step:
      • Установите 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 () очень медленный, что было одной из моих возможностей (неправильная структура данных)

  • предложил посмотреть на рекурсию (что больше относится к моим сомнениям в алгоритме). Хотя я не вижу, как сделать это рекурсивным.

Заранее спасибо за помощь!

Ответы [ 2 ]

0 голосов
/ 23 июня 2019

Есть повторение, которое можно запомнить.(Кажется, это проходит тесты 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 -ой позиции.Таким образом, проблема состоит в том, чтобы найти (i - 1) -й элемент, удаленный после удаления элемента в (k - 1) mod n и начиная с k, то есть (k + g(n - 1, k, i - 1)) mod n.

0 голосов
/ 23 июня 2019

Вы пытались реализовать функциональный подход?из википедии : 

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)

...