Énumération des combinaisons par produit

Question

J'ai trois listes a, b, c. Chaque liste contient un nombre d'entiers dans l'ordre trié.

Par souci de l'exemple nous:

a = [2, 2, 7] 
b = [4, 6, 9] 
c = [3, 6, 8] 

Mon but est d'énumérer tous les produits possibles des éléments des trois listes dans l'ordre croissant. Le produit minimal est bien sûr a[0]*b[0]*c[0]. Dans l'exemple, le deuxième produit le plus bas est a[0]*b[1]*c[0]. Etc. J'essaie de trouver une solution générale pour un nombre arbitraire de listes. J'ai du mal à généraliser le passage du k-ème produit le plus bas au produit le plus bas (k + 1). Je ne veux pas énumérer tous les produits possibles, puis les trier, parce que j'ai affaire à un très grand nombre de listes et que je ne m'intéresse qu'aux 1000 premières combinaisons, par exemple.

Toute aide sera appréciée, y compris les pointeurs vers les manuels.

Answer 1

Disons que nous voulons une complexité temporelle de O(N * K) où N est le nombre de listes et K est le K produit -ème. Nous maintenons un pointeur au début de chaque liste (pour simplifier, j'appelle cela le P[i] - i 'pointeur sur la liste i, et L[i] - la liste i).

Dans un premier temps P[i] = 0 pour chaque liste (parce que nous commençons l'indexation des listes de 0)

Step 1: Le premier produit est L[0][P[1]] * L[1][P[2]] * .. L[N][P[N]].

Step 2: Pour la prochaine étape, nous sommes intéressés par la minimisation du produit suivant. Nous sélectionnons j (0<=j<=N) pour lequel L[j][P[j] + 1] est minimum. Nous incrémentons P[j] par 1, puis nous passons au Step 1 pour calculer le prochain produit. Je pense qu'il est clair que le prochain produit devrait être le minimum de toutes les possibilités.

Si vous souhaitez compter le nombre de produits uniques, il vous suffit de gérer un compteur que vous n'augmenterez que si le produit actuel est différent du précédent.

Vous pouvez toujours améliorer cet algorithme en O(log(N) * K) en utilisant une file d'attente prioritaire afin d'obtenir le minimum à Step 2.