En m'entraînant aux guerres de code, je suis tombé sur un défi concernant les permutations de Joseph, j'ai d'abord essayé de le résoudre sur papier et ensuite de le traduire en code.
Le problème est le suivant: "Créez une fonction qui renvoie une permutation Josèphe, en prenant comme paramètres le tableau / la liste initiale des éléments à permuter comme s'ils étaient dans un cercle et en comptant toutes les k places jusqu'à ce qu'il n'en reste plus."
Ma principale l'idée était:
Utilisez deux itérateurs:
Initialiser i à 0 et k à 1
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),[])
Cela fonctionne mais ce n'est pas efficace, quand je l'exécute sur les exemples de tests, j'obtiens que 5 des exemples de tests ont réussi, mais il comprend également un STDERR: Execution Timed Out (12000 ms).
Les exemples de tests sont les suivants:
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;
}
Ma question est, comment pourrais-je rendre cela plus efficace?
Est-ce l'algorithme que j'utilise qui est faux ou est-ce l'implémentation?
Un commentaire mentionnait deux choses:
push () est très lent, ce qui était l'une de mes possibilités (mauvaise structure de données)
a suggéré de regarder la récursion (ce qui va plus dans mon doute sur l'algorithme). Je ne vois pas vraiment comment rendre cela récursif.
Merci d'avance pour votre aide!
3 Réponses :
avez-vous essayé de mettre en œuvre l'approche fonctionnelle? depuis 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);
}
cela devrait exécuter en O (n)
Je calcule peut-être mal mon Big O mais mon code ne devrait-il pas tourner autour de O (étape * n) = O (n)? Va vérifier cette solution!
OP a comme paramètre step , ce n'est pas toujours 2 .
Il y a une récurrence, qui pourrait être mémorisée. (Cela semble réussir les tests de 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);
Pour expliquer la récurrence, le premier élément supprimé (lorsque i = 1 ) est clairement (k - 1) mod n (indexé à zéro) . Pensez maintenant à trouver g (n, k, i) . Le premier élément qui est supprimé est (k - 1) mod n , puis nous commençons à la k ième position. Le problème est donc de trouver le (i - 1) ème élément supprimé après avoir supprimé l'élément à (k - 1) mod n et à partir de k , qui est (k + g (n - 1, k, i - 1)) mod n .
Pouvez-vous m'aider à résoudre cette variante du problème de Josèphe: -> stackoverflow.com/questions/56941975/... Merci :-)
Vous pouvez déplacer le premier bit vers la fin.
const josephus = (x) => parseInt(x.toString(2).substr(1) + 1, 2);
Je ne savais pas codereview, je vais le vérifier. Je cherche des alternatives mais rien ne m'est venu à l'esprit en termes de récursivité.
splicea tendance à être coûteux, mais je ne peux pas imaginer que les tests que vous avez fournis puissent durer 12 secondes à moins que certaines des boucles de votre code ne restent bloquées ou ne soient configurées pour se terminer après un nombre extraordinaire de répétitions.@ גלעד ברקן: Si je me souviens bien, CodeWars vous donne quelques exemples de cas de test afin que vous puissiez tester l'exactitude de votre algorithme, mais en cache d'autres qu'il utilise pour assurer l'efficacité d'exécution.