used - lru algorithm




Quel est l'algorithme optimal de taille de l'ongle juif? (4)

En fait, j'aime mieux votre algorithme original.

Puisque 14 permutations sur 120 fonctionnent, 106 sur 120 ne le font pas. Chaque vérification a donc 106/120 chances d'échouer.

Cela signifie que le nombre attendu d'échecs est:

1*(106/120) + 2*(106/120)^2 + 3*(106/120)^3 + ...

Pas trop difficile de résumer cette série infinie:

S       = 1*x + 2*x^2 + 3*x^3 + ...

Multipliez par x:

x*S     =       1*x^2 + 2*x^3 + ...

Soustraire:

S - x*S = x + x^2 + x^3 + ...

Multipliez à nouveau par x et soustrayez à nouveau:

x*S - x^2*S = x^2 + x^3 + ...
S - 2*x*S + x^2S = x
S*(1-x)^2 = x
S = x/(1-x)^2

Puisque x = 106/120, S = 64,9.

Donc, en moyenne, votre boucle n'a besoin que de 65 itérations pour trouver une solution.

Quelle est la probabilité que cela prenne, disons, mille itérations?

Eh bien, la probabilité d'échec d'une seule itération est de 104/120, donc la probabilité d'échec de 1000 itérations est de (104/120) ^ 1000, ce qui est quelque chose comme 10 ^ (- 63). C'est-à-dire que vous ne verrez jamais cela se produire dans votre vie, et probablement pas dans la vie de l'univers.

Pas de tables précalculées, adaptation facile à différents nombres de doigts / orteils / mains / pieds, adaptation facile à différents jeux de règles ... Qu'est-ce qui ne va pas? La décroissance exponentielle est une chose merveilleuse.

[mettre à jour]

Oups, j'ai mal compris la formule originale ... Comme mes probabilités ne sont pas égales à 1. :-)

L'expression correcte pour le nombre attendu d'échecs est:

0*(14/120) + 1*(106/120)*(14/120) + 2*(106/120)^2*(14/120) + ...

(Par exemple, pour obtenir exactement deux échecs, vous avez besoin de deux échecs suivis d'un succès : deux échecs ont une probabilité (106/120) ^ 2, un succès a une probabilité (14/120), multipliez-les par deux pour obtenir le poids "2" terme.)

Donc, mon S est éteint par un facteur de (1-x) (ie, 14/120). Le nombre réel attendu de défaillances est juste x / (1-x) = 106/14 = 7,57. Donc, en moyenne, il suffit de 8 à 9 itérations pour trouver une solution (7,5 échecs plus un succès).

Mes calculs pour l'affaire "1000 échecs" sont toujours corrects, je pense.

Je travaille sur le logiciel pour une machine qui va automatiquement couper les ongles, de sorte que les utilisateurs peuvent simplement mettre leurs pieds dedans et les exécuter au lieu d'avoir à le faire manuellement en les mordant ou en utilisant des coupe-ongles.

Un pourcentage important de notre base d'utilisateurs potentiels sera probablement juif, et, évidemment, il y a une tradition de ne pas rogner les ongles ( ou les ongles ) dans l'ordre séquentiel

Il semble y avoir une opinion dissidente sur l'application précise de cette tradition, mais nous pensons que les règles suivantes sont suffisantes pour accommoder les personnes dont les pratiques religieuses interdisent de couper les ongles dans l'ordre:

  • Aucun deux ongles adjacents doivent être coupés consécutivement
  • La séquence de coupe sur le pied gauche ne doit pas correspondre à la séquence sur le pied droit
  • La séquence de coupe sur deux séries consécutives ne devrait pas être la même. Les séquences ne devraient pas être facilement prévisibles, de sorte que le codage en dur d'une séquence en alternance ne fonctionne pas.

Voici comment nous avons décidé de numéroter les orteils:

5 4 3 2 1  1 2 3 4 5
Left foot  Right foot

J'ai écrit du code pour résoudre le problème, mais l'algorithme utilisé est sous-optimal: en fait, la pire des performances est O (∞) . La façon dont cela fonctionne est comparable à bogosort . Voici une simplification du pseudo code du code réel utilisé:

function GenerateRandomSequence
   sequence = Array[5]
   foreach (item in sequence)
       item = RandomNumberBetween(1,5)
   return sequence

function GetToenailCuttingOrder
   while (true)
      sequence = GenerateRandomSequence()
      if (!AllItemsAreUnique(sequence))
         continue
      if (NoTwoAdjacentItemsHaveConsecutiveNumbers(sequence))
         return sequence

do
    leftFootSequence = GetToenailCuttingOrder()
    rightFootSequence = GetToenailCuttingOrder()
until (leftFootSequence != rightFootSequence &&
       leftFootSequence != leftFootSequenceFromLastRun &&
       rightFootSequence != rightFootSequenceFromLastRun)

Fondamentalement, il génère des séquences aléatoires et vérifie si elles répondent aux critères. S'il ne répond pas aux critères, il recommence. Cela ne prend pas un temps ridiculement long, mais c'est très imprévisible.

Je me rends compte que la façon dont je le fais actuellement est assez terrible, mais j'ai de la difficulté à trouver une meilleure solution. Quelqu'un d'entre vous peut-il suggérer un algorithme plus élégant et performant?


Il n'y a vraiment aucune raison d'introduire un caractère aléatoire dans ce problème. Il y a seulement 14 séquences qui satisfont ce problème, et sûrement un ordre de ces séquences satisferait le mieux le sens esthétique que vous essayez d'accommoder. Ainsi, vous devriez simplement réduire ce problème à un algorithme pour choisir une séquence parmi ces 14, probablement dans un ordre prédéfini.

Implémentation Javascript de l'algorithme pour trouver le 14:

function swap (a, i, j) {
  var temp = a[i]
  a[i]=a[j]
  a[j]=temp
}

function permute (b, n, a) {
  if (n==4) {
    b.push(a.slice(0)) //copy array
  }
  else {
    for (var i = n; i < 5; i++) {
      swap(a,n,i)
      permute(b, n+1, a)
      swap(a,n,i)
    }
  }
}

var a = [1,2,3,4,5]
var b = []
var c = []

permute(b,0,a)

for (var i = 1; i < b.length-1; i++) {
  var good = true
  for (var j = 0; j < b[i].length; j++) {
    if (Math.abs(b[i][j-1]-b[i][j]) < 2 || Math.abs(b[i][j]-b[i][j+1]) < 2) {
      good = false
    }
  }
  if (good) c.push(b[i].join(''))
}

console.log(c)

EDIT: La nouvelle exigence selon laquelle les séquences doivent être générées aléatoirement ne peut pas être facilement satisfaite. Le mieux que vous puissiez probablement faire est de les générer de manière pseudo-aléatoire, ce qui est tout aussi déterministe que de les coder à l'avance, et ne devrait donc pas satisfaire les superstitions de qui que ce soit.


L'évidence: Trouver un ordre qui fonctionne, et le coder en dur. Mais je ne pense pas que tu veuilles le faire.

Vous pouvez générer des permutations beaucoup mieux que la façon dont vous le faites. Vous n'avez pas besoin de faire un échantillonnage de rejet. Utilisez un shuffle de Fisher Yates sur une permutation initialement triée (1, 2, .. 5), et vous aurez une permutation aléatoire. http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Mais en général, la méthode de génération et de test me semble tout à fait satisfaisante tant que la probabilité de générer une entrée réussie est suffisamment élevée. Je suis sûr qu'il y a beaucoup de séquences valides selon vos critères, une fois que vous passez à une permutation aléatoire, je doute que vous deviez faire beaucoup d'itérations de rejet.


Rien de vraiment nouveau ici, la même solution @Kevin déjà posté, mais je pense intéressant de voir comment cela se traduit par un langage fonctionnel. Dans ce cas, Mathematica :

Extract[#,Position[Times @@ ([email protected]#-1)&/@ Differences/@ #, [email protected], 1][[2 ;;]]]  
         &@ [email protected]@5

Quelques explications:

[email protected]@5 Calculates all permutations of {1, 2, 3, 4, 5}

Differences          Calculate the differences between adjacent elements
                     (we wish to discard all lists containing +1 or -1)

Times @@ ([email protected]#-1)   Abs turns the -1s into +1s, and then to zeros by subtracting
                     one, then TIMES multiplies all elements, giving zero when 
                     the original result of "Differences" contained a +1 or a -1

Position ... [email protected] Returns the position of the non zero results

Extract              Returns the original elements according to the calculated 
                     positions

Le résultat final est:

{{1, 3, 5, 2, 4}, {1, 4, 2, 5, 3}, {2, 4, 1, 3, 5}, {2, 4, 1, 5, 3}, 
 {2, 5, 3, 1, 4}, {3, 1, 4, 2, 5}, {3, 1, 5, 2, 4}, {3, 5, 1, 4, 2}, 
 {3, 5, 2, 4, 1}, {4, 1, 3, 5, 2}, {4, 2, 5, 1, 3}, {4, 2, 5, 3, 1}, 
 {5, 2, 4, 1, 3}, {5, 3, 1, 4, 2}}

modifier

Ou, plus difficile à expliquer, mais plus court:

Reap[ Table[ If[Times @@ ([email protected]@i - 1) != 0, [email protected]],
           {i, [email protected]@5}]][[2, 1]]






language-agnostic