Combinaisons avec répétitions inférieur à un nombre

Bonjour à tous.

J'ai une liste liste1 des 10 premiers nombres premiers et un nombre très grand A (par exemple 15!). J'aimerai obtenir l'ensemble des combinaisons avec répétitions de liste1 tel que le produit des nombres de chacune des combinaisons avec répétitions soit inférieur à A. Avez-vous une idée?

J'ai essayé en utilisant "from itertools import combinations_with_replacement" et des listes par compréhension mais je dépasse la mémoire, en effet, je ne l'utilise pas de façon optimal, je génère bien trop de combinaisons avec répétitions.

J'espère avoir été clair.

Merci pour votre aide.

Bonjour

Citation:

---

Envoyé par Balafraise

J'espère avoir été clair.

---

Pas suffisamment.

Si on cherche la "combinaison", on calcule "une combinaison de n objets pris k à k": combien vaut k ici?

A moins que ce soit la liste des "parties d'un ensemble" (https://fr.wikipedia.org/wiki/Ensemb...%27un_ensemble)?

En général; on comprend mieux avec un exemple simplifié (par exemple avec les 4 premiers nombres premiers). Et ce serait bien de donner ici la tentative de code.

Tout d'abord, merci de m'avoir répondu.

Je vous donne un exemple. Prenons liste1 = [2,3,5,7] et A = 26. J'aimerai obtenir les listes suivantes:
[2] , [2,2] , [2,2,2] , [2,2,2,2] , Mais pas [2,2,2,2,2] car 2x2x2x2x2=32 et 32> A
On obtient ensuite: [3] , [3,2] , [3,2,2] , [3,2,2,2] Mais pas [3,2,2,2,2] car 3x2x2x2x2=48 et 48> A
Ensuite: [3,3] , [3,3,2]
On se rend compte que [3,3,3] ne fonctionne pas car 3x3x3=27 et 27>A
Donc on poursuit avec [5] , [5,2] , [5,2,2] Puis [5,3] , [5,5] et les derniers [7] , [7,2] , [7,3]

Malheureusement, je ne parviens pas à faire en sorte que mon programme suive la construction des listes comme dans mon exemple précédent. J'ai simplement généré toutes les listes possibles ayant au maximum E(log2(A)) éléments où E désigne la partie entière. E(log2(A)) correspond aux nombres de 2 nécessaires pour atteindre ma borne. De cette façon, je génère les listes qui m'intéressent, mais en réalité j'en génère vraiement beaucoup plus ce qui rend mon programme inutilisable pour A grand. Voici mon code:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

from itertools import combinations_with_replacement from math import *   def final(borne): liste=[] fact_borne=factorial(borne) premier = [2,3,5,7,11,13,17,19,29] for i in range(int(log2(fact_borne))): liste+= combinations_with_replacement(premier, i) liste2=[produit(t) for t in liste if produit(t)<=fact_borne] return liste2

---

La fonction "produit" calcule le produit des éléments d'une liste.

Je vous remercie.

Citation:

---

Envoyé par Balafraise

J'ai une liste liste1 des 10 premiers nombres premiers et un nombre très grand A (par exemple 15!). J'aimerai obtenir l'ensemble des combinaisons avec répétitions de liste1 tel que le produit des nombres de chacune des combinaisons avec répétitions soit inférieur à A.

---

Si la liste ne comprend qu'un seul nombre premier z alors il existe un entier n tel que zⁿ <= A < zⁿ⁺¹.

Si la liste comprend 2 nombres premiers y et z (y < z), il existe (0, n) tel que u⁰*zⁿ <= A < u⁰*zⁿ⁺¹. Comme y < z, il existe m tel que (m, n-1) vérifie u^m*z^n-1 <= A < u^m*z^n-1,.... et je recommence avec z^n-2.

- W

salut,

avec une fonction récursive un truc comme ça semble fonctionner :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

def combinations(numbers, target): def recurse(current, start, output, result): if (current <= target) and result: output.append(result[:])   for i in range(start, len(numbers)+1): temp = current * numbers[i-1] if temp <= target: result.append(numbers[i-1]) recurse(temp, i, output, result) result.pop() else: return output = [] result = [] recurse(1, 1, output, result) return output

---

et le résultat :

Code:

---

1 2	>>> combinations([2,3,5,7], 26) [[2], [2, 2], [2, 2, 2], [2, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3], [2, 2, 5], [2, 3], [2, 3, 3], [2, 5], [2, 7], [3], [3, 3], [3, 5], [3, 7], [5], [5, 5], [7]]

---

à voir si ça fonctionne avec 15! néanmoins... et ça vaudrait peut-être le coup de le transformer en générateur aussi :P

Merci à tous pour vos réponses!

En effet, une fonction récursive était une excellente idée. Et cela fonctionne très bien même avec des valeurs comme 15! .

Merci encore.

Bonne journée.