Énumérer des points de grille sur un plan 2D avec ordre décroissant de (x * y)

Voici une solution O (k Logk), où K est le nombre de termes que vous souhaitez générer.
EDIT: Q ne conserve qu'une copie de chaque élément; Un insert échoue si l'élément est déjà présent.

priority_queue Q
Q.insert( (N*M, (N,M)) ) // priority, (x,y) 
repeat K times:
    (v, (x,y)) = Q.extract_max()
    print(v, (x,y))
    Q.insert( (x-1)*y, (x-1,y) )
    Q.insert( x*(y-1), (x,y-1) )

Une approche factice qui boucle de NXM à 1 recherche des paires qui, lorsqu'elles sont multipliées produisent le nombre actuel: xxx

pour n = m, la complexité est O (n ^{3 ) mais l'utilisation de la mémoire est O (1).}

Mise à jour : Notez que la complexité n'est pas aussi mauvaise que parce que le nombre d'éléments à générer est déjà n ° N < sup> 2 . Pour la comparaison, l'approche Generate-The-The-Sort est O (N ^{2 logn) avec O (N 2 ) Utilisation de la mémoire.}

Voici un algorithme pour vous. Je vais essayer de vous donner une description en anglais.

Dans le rectangle, nous travaillons avec, nous pouvons toujours supposer qu'un point p (x, y) code> a une plus grande "zone" que Le point ci-dessous p (x, y-1) code>. Ainsi, lorsque vous recherchez des points de surface maximale, il suffit de comparer le point le plus haut absolu dans chaque colonne (c'est-à-dire pour chaque x code>). Par exemple, lorsque vous envisagez de la pristine 3 x 5 code> grille p> xxx pré>

Nous n'avons vraiment besoin que de comparer A code>, B code> et c code>. Tous les autres points sont garantis pour avoir moins de superficie qu'au moins une de celles-ci. Donc, construisez un tas maximum qui ne contient que le point le plus haut dans chaque colonne. Lorsque vous faites obstacle à un point sur le tas, poussez-le au point qui se trouve directement en dessous (si ce point existe). Répétez jusqu'à ce que le tas soit vide. Cela vous donne l'algorithme suivant (testé, mais c'est en rubis): p> xxx pré>

ceci vous donne une heure d'exécution de O ((2K + N) log n) code>. Coût des opérations de tas journal n code>; nous faisons n code> lors de la construction du tas initial, puis 2k code> lorsque nous retirons les points k code> de la surface maximale (2 en supposant chaque pop est suivie de la poussée du point ci-dessous). P>

Il a l'avantage supplémentaire de ne pas avoir à construire tous vos points, contrairement à la proposition initiale de la construction de l'ensemble de l'ensemble, puis de tri. Vous ne construisez que autant de points que nécessaire pour garder votre tas précis. P>

et enfin: les améliorations peuvent être faites! EM> Je ne les ai pas faites, mais vous pourriez avoir une meilleure performance avec les modifications suivantes: p>

1. ne descend que sur y = x code> dans chaque colonne au lieu de y = 1 code>. Pour générer les points que vous ne vérifiez plus, utilisez le fait que la zone de p (x, y) code> est égale à la zone de p (y, x) code >. REMARQUE: FORT> Si vous utilisez cette méthode, vous aurez besoin de deux versions de l'algorithme. Les colonnes fonctionnent lorsque m> = n code>, mais si m vous devez le faire par des lignes à la place. Li>
2. considère uniquement les colonnes qui pourraient éventuellement contenir le maximum. Dans l'exemple que j'ai donné, il n'y a aucune raison d'inclure A code> dans le tas depuis le début, car il est garanti d'être inférieur à B code>. Donc, il vous suffit d'ajouter des colonnes au tas lorsque les points supérieurs de leurs colonnes de voisin sont sautés. Li> ol>

   et qui s'est transformé en un petit essai ... de toute façon - espérons que cela aide! p>

   EDIT: FORT> L'algorithme complet, intégrant les deux améliorations que j'ai mentionnées ci-dessus ( Mais toujours dans Ruby, parce que je suis paresseux). Notez qu'il n'est pas nécessaire de ne pas avoir besoin de structures supplémentaires pour éviter d'insérer des doublons - à moins que ce soit un "sommet", chaque point ne insérera qu'un autre point de sa ligne / colonne est pris. P>

   def enumerate(n, m, k)
       heap = MaxHeap.new
       heap.push(Point.new(n, m))
       result = []
   
       loop do
           max = heap.pop
           result << max
           return result if result.length == k
   
           result << Point.new(max.y, max.x) if max.x <= m && max.y <= n && max.x != max.y
           return result if result.length == k
   
           if(m < n) # One point per row
               heap.push(Point.new(max.x, max.y - 1)) if max.x == n && max.y > 1
               heap.push(Point.new(max.x - 1, max.y)) if max.x > max.y
           else # One point per column
               heap.push(Point.new(max.x - 1, max.y)) if max.y == m && max.x > 1
               heap.push(Point.new(max.x, max.y - 1)) if max.y > max.x
           end
       end
   end
   

Je l'ai compris!

Considérez la grille en tant que jeu de m colonnes où chaque colonne est une pile contenant les éléments de 1 en bas à n en haut en haut. Chaque colonne est étiquetée avec sa coordonnée x.

Les éléments à l'intérieur de chaque pile de colonne sont commandés par sa valeur y et aussi par x * y comme x a la même valeur pour toutes.

Donc, il vous suffit d'aller choisir la pile qui a la plus grande valeur x * y à son sommet, pop-le et répétez.

En pratique, vous n'aurez pas besoin de piles, juste l'index du Valeur supérieure et vous pouvez utiliser une file d'attente prioritaire pour obtenir la colonne avec la plus grande valeur x * y. Ensuite, décrémenter la valeur de l'indice et s'il est plus grand que 0 (indiquant que la pile n'a pas été épuisée) réinsérez la pile sur la file d'attente avec sa nouvelle priorité x * y.

la complexité de cette L'algorithme pour n = m est O (n ^{2 logn) et son utilisation de la mémoire O (n).}

update : mis en œuvre dans Perl ... xxx