Je cherche à créer une liste de permutations entre un élément et une liste en Python. Par exemple:
import itertools import re # include blanks to allow for four-word permutations to have just one, two, or three words adjectives = ['', '', '', 'nyc', 'strawberry', 'apple', 'banana', 'orange', 'pineapple'] names = ['-'.join(x) for x in itertools.permutations(adjectives, 4)] # limit to permutations that contain 'nyc' names = [x for x in names if 'nyc' in x] # since joining blanks using "-", remove the multiple dashes when this happens # and also remove leading or trailing dashes names = [re.sub(r"-+", "-", x) for x in names] names = [re.sub(r"-+$", "", x) for x in names] names = [re.sub(r"^-+", "", x) for x in names] # remove duplicates, since blank can be added multiple times, sort for visual clarity names = sorted(list(set(names))) print(names)
J'essaie d'obtenir jusqu'à quatre mots avec «nyc» toujours inclus. L'ordre est important et «nyc» doit toujours être inclus. Par exemple:
nyc strawberry-nyc nyc-strawberry strawberry-apple-nyc strawberry-apple-banana-nyc
Ce que j'ai fait jusqu'à présent, c'est de mettre tous les mots dans une seule liste, d'inclure quelques espaces, puis de créer toutes les permutations à l'aide d'itertools, puis de supprimer tous les lignes qui ne conatain "nyc":
[nyc] [strawberry, apple, banana, orange, pineapple, ..]
J'ai parcouru itertools et certaines des questions ici, je pense que je dois négliger une solution simple. Quelle serait la manière la plus efficace de procéder?
4 Réponses :
Vous pouvez trouver toutes les combinaisons des éléments dans la liste principale, puis appliquer un produit cartésien:
['nyc', 'nyc-strawberry', 'strawberry-nyc', 'strawberry-nyc-apple', 'nyc-strawberry-apple', 'strawberry-apple-nyc', 'strawberry-nyc-apple-banana', 'strawberry-apple-nyc-banana', 'strawberry-apple-banana-nyc', 'nyc-strawberry-apple-banana', 'strawberry-nyc-apple-orange', 'strawberry-apple-nyc-orange', 'strawberry-apple-orange-nyc', 'nyc-strawberry-apple-orange', 'strawberry-nyc-apple-pineapple', 'strawberry-apple-nyc-pineapple', 'strawberry-apple-pineapple-nyc', 'nyc-strawberry-apple-pineapple', 'strawberry-nyc-banana', 'nyc-strawberry-banana', 'strawberry-banana-nyc', 'strawberry-nyc-banana-apple', 'strawberry-banana-nyc-apple', 'strawberry-banana-apple-nyc', 'nyc-strawberry-banana-apple', 'strawberry-nyc-banana-orange', 'strawberry-banana-nyc-orange', 'nyc-strawberry-banana-orange', 'strawberry-banana-orange-nyc', 'strawberry-nyc-banana-pineapple', 'strawberry-banana-nyc-pineapple', 'nyc-strawberry-banana-pineapple', 'strawberry-banana-pineapple-nyc', 'strawberry-nyc-orange', 'strawberry-orange-nyc', 'nyc-strawberry-orange', 'strawberry-nyc-orange-apple', 'strawberry-orange-nyc-apple', 'nyc-strawberry-orange-apple', 'strawberry-orange-apple-nyc', 'strawberry-nyc-orange-banana', 'strawberry-orange-nyc-banana', 'nyc-strawberry-orange-banana', 'strawberry-orange-banana-nyc', 'strawberry-nyc-orange-pineapple', 'strawberry-orange-nyc-pineapple', 'nyc-strawberry-orange-pineapple', 'strawberry-orange-pineapple-nyc', 'strawberry-nyc-pineapple', 'strawberry-pineapple-nyc', 'nyc-strawberry-pineapple', 'strawberry-nyc-pineapple-apple', 'strawberry-pineapple-nyc-apple', 'nyc-strawberry-pineapple-apple', 'strawberry-pineapple-apple-nyc', 'strawberry-nyc-pineapple-banana', 'strawberry-pineapple-nyc-banana', 'nyc-strawberry-pineapple-banana', 'strawberry-pineapple-banana-nyc', 'strawberry-nyc-pineapple-orange', 'strawberry-pineapple-nyc-orange', 'strawberry-pineapple-orange-nyc', 'nyc-strawberry-pineapple-orange', 'apple-nyc', 'nyc-apple', 'apple-nyc-strawberry', 'apple-strawberry-nyc', 'nyc-apple-strawberry', 'apple-nyc-strawberry-banana', 'apple-strawberry-nyc-banana', 'apple-strawberry-banana-nyc', 'nyc-apple-strawberry-banana', 'apple-nyc-strawberry-orange', 'apple-strawberry-nyc-orange', 'nyc-apple-strawberry-orange', 'apple-strawberry-orange-nyc', 'apple-nyc-strawberry-pineapple', 'apple-strawberry-nyc-pineapple', 'apple-strawberry-pineapple-nyc', 'nyc-apple-strawberry-pineapple', 'apple-nyc-banana', 'apple-banana-nyc', 'nyc-apple-banana', 'apple-nyc-banana-strawberry', 'apple-banana-nyc-strawberry', 'nyc-apple-banana-strawberry', 'apple-banana-strawberry-nyc', 'apple-nyc-banana-orange', 'apple-banana-nyc-orange', 'apple-banana-orange-nyc', 'nyc-apple-banana-orange', 'apple-nyc-banana-pineapple', 'apple-banana-nyc-pineapple', 'nyc-apple-banana-pineapple', 'apple-banana-pineapple-nyc', 'apple-nyc-orange', 'nyc-apple-orange', 'apple-orange-nyc', 'apple-nyc-orange-strawberry', 'apple-orange-nyc-strawberry', 'nyc-apple-orange-strawberry', 'apple-orange-strawberry-nyc', 'apple-nyc-orange-banana', 'apple-orange-nyc-banana', 'apple-orange-banana-nyc', 'nyc-apple-orange-banana', 'apple-nyc-orange-pineapple', 'apple-orange-nyc-pineapple', 'apple-orange-pineapple-nyc', 'nyc-apple-orange-pineapple', 'apple-nyc-pineapple', 'nyc-apple-pineapple', 'apple-pineapple-nyc', 'apple-nyc-pineapple-strawberry', 'apple-pineapple-nyc-strawberry', 'apple-pineapple-strawberry-nyc', 'nyc-apple-pineapple-strawberry', 'apple-nyc-pineapple-banana', 'apple-pineapple-nyc-banana', 'apple-pineapple-banana-nyc', 'nyc-apple-pineapple-banana', 'apple-nyc-pineapple-orange', 'apple-pineapple-nyc-orange', 'apple-pineapple-orange-nyc', 'nyc-apple-pineapple-orange', 'nyc-banana', 'banana-nyc', 'banana-nyc-strawberry', 'nyc-banana-strawberry', 'banana-strawberry-nyc', 'banana-nyc-strawberry-apple', 'banana-strawberry-nyc-apple', 'banana-strawberry-apple-nyc', 'nyc-banana-strawberry-apple', 'banana-nyc-strawberry-orange', 'banana-strawberry-nyc-orange', 'banana-strawberry-orange-nyc', 'nyc-banana-strawberry-orange', 'banana-nyc-strawberry-pineapple', 'banana-strawberry-nyc-pineapple', 'nyc-banana-strawberry-pineapple', 'banana-strawberry-pineapple-nyc', 'banana-nyc-apple', 'banana-apple-nyc', 'nyc-banana-apple', 'banana-nyc-apple-strawberry', 'banana-apple-nyc-strawberry', 'banana-apple-strawberry-nyc', 'nyc-banana-apple-strawberry', 'banana-nyc-apple-orange', 'banana-apple-nyc-orange', 'nyc-banana-apple-orange', 'banana-apple-orange-nyc', 'banana-nyc-apple-pineapple', 'banana-apple-nyc-pineapple', 'nyc-banana-apple-pineapple', 'banana-apple-pineapple-nyc', 'banana-nyc-orange', 'banana-orange-nyc', 'nyc-banana-orange', 'banana-nyc-orange-strawberry', 'banana-orange-nyc-strawberry', 'banana-orange-strawberry-nyc', 'nyc-banana-orange-strawberry', 'banana-nyc-orange-apple', 'banana-orange-nyc-apple', 'nyc-banana-orange-apple', 'banana-orange-apple-nyc', 'banana-nyc-orange-pineapple', 'banana-orange-nyc-pineapple', 'banana-orange-pineapple-nyc', 'nyc-banana-orange-pineapple', 'banana-nyc-pineapple', 'nyc-banana-pineapple', 'banana-pineapple-nyc', 'banana-nyc-pineapple-strawberry', 'banana-pineapple-nyc-strawberry', 'banana-pineapple-strawberry-nyc', 'nyc-banana-pineapple-strawberry', 'banana-nyc-pineapple-apple', 'banana-pineapple-nyc-apple', 'banana-pineapple-apple-nyc', 'nyc-banana-pineapple-apple', 'banana-nyc-pineapple-orange', 'banana-pineapple-nyc-orange', 'nyc-banana-pineapple-orange', 'banana-pineapple-orange-nyc', 'orange-nyc', 'nyc-orange', 'orange-nyc-strawberry', 'nyc-orange-strawberry', 'orange-strawberry-nyc', 'orange-nyc-strawberry-apple', 'orange-strawberry-nyc-apple', 'nyc-orange-strawberry-apple', 'orange-strawberry-apple-nyc', 'orange-nyc-strawberry-banana', 'orange-strawberry-nyc-banana', 'nyc-orange-strawberry-banana', 'orange-strawberry-banana-nyc', 'orange-nyc-strawberry-pineapple', 'orange-strawberry-nyc-pineapple', 'nyc-orange-strawberry-pineapple', 'orange-strawberry-pineapple-nyc', 'orange-nyc-apple', 'nyc-orange-apple', 'orange-apple-nyc', 'orange-nyc-apple-strawberry', 'orange-apple-nyc-strawberry', 'orange-apple-strawberry-nyc', 'nyc-orange-apple-strawberry', 'orange-nyc-apple-banana', 'orange-apple-nyc-banana', 'nyc-orange-apple-banana', 'orange-apple-banana-nyc', 'orange-nyc-apple-pineapple', 'orange-apple-nyc-pineapple', 'nyc-orange-apple-pineapple', 'orange-apple-pineapple-nyc', 'orange-nyc-banana', 'nyc-orange-banana', 'orange-banana-nyc', 'orange-nyc-banana-strawberry', 'orange-banana-nyc-strawberry', 'orange-banana-strawberry-nyc', 'nyc-orange-banana-strawberry', 'orange-nyc-banana-apple', 'orange-banana-nyc-apple', 'nyc-orange-banana-apple', 'orange-banana-apple-nyc', 'orange-nyc-banana-pineapple', 'orange-banana-nyc-pineapple', 'orange-banana-pineapple-nyc', 'nyc-orange-banana-pineapple', 'orange-nyc-pineapple', 'nyc-orange-pineapple', 'orange-pineapple-nyc', 'orange-nyc-pineapple-strawberry', 'orange-pineapple-nyc-strawberry', 'nyc-orange-pineapple-strawberry', 'orange-pineapple-strawberry-nyc', 'orange-nyc-pineapple-apple', 'orange-pineapple-nyc-apple', 'nyc-orange-pineapple-apple', 'orange-pineapple-apple-nyc', 'orange-nyc-pineapple-banana', 'orange-pineapple-nyc-banana', 'orange-pineapple-banana-nyc', 'nyc-orange-pineapple-banana', 'nyc-pineapple', 'pineapple-nyc', 'pineapple-nyc-strawberry', 'nyc-pineapple-strawberry', 'pineapple-strawberry-nyc', 'pineapple-nyc-strawberry-apple', 'pineapple-strawberry-nyc-apple', 'nyc-pineapple-strawberry-apple', 'pineapple-strawberry-apple-nyc', 'pineapple-nyc-strawberry-banana', 'pineapple-strawberry-nyc-banana', 'nyc-pineapple-strawberry-banana', 'pineapple-strawberry-banana-nyc', 'pineapple-nyc-strawberry-orange', 'pineapple-strawberry-nyc-orange', 'nyc-pineapple-strawberry-orange', 'pineapple-strawberry-orange-nyc', 'pineapple-nyc-apple', 'pineapple-apple-nyc', 'nyc-pineapple-apple', 'pineapple-nyc-apple-strawberry', 'pineapple-apple-nyc-strawberry', 'pineapple-apple-strawberry-nyc', 'nyc-pineapple-apple-strawberry', 'pineapple-nyc-apple-banana', 'pineapple-apple-nyc-banana', 'nyc-pineapple-apple-banana', 'pineapple-apple-banana-nyc', 'pineapple-nyc-apple-orange', 'pineapple-apple-nyc-orange', 'pineapple-apple-orange-nyc', 'nyc-pineapple-apple-orange', 'pineapple-nyc-banana', 'nyc-pineapple-banana', 'pineapple-banana-nyc', 'pineapple-nyc-banana-strawberry', 'pineapple-banana-nyc-strawberry', 'nyc-pineapple-banana-strawberry', 'pineapple-banana-strawberry-nyc', 'pineapple-nyc-banana-apple', 'pineapple-banana-nyc-apple', 'pineapple-banana-apple-nyc', 'nyc-pineapple-banana-apple', 'pineapple-nyc-banana-orange', 'pineapple-banana-nyc-orange', 'nyc-pineapple-banana-orange', 'pineapple-banana-orange-nyc', 'pineapple-nyc-orange', 'pineapple-orange-nyc', 'nyc-pineapple-orange', 'pineapple-nyc-orange-strawberry', 'pineapple-orange-nyc-strawberry', 'nyc-pineapple-orange-strawberry', 'pineapple-orange-strawberry-nyc', 'pineapple-nyc-orange-apple', 'pineapple-orange-nyc-apple', 'nyc-pineapple-orange-apple', 'pineapple-orange-apple-nyc', 'pineapple-nyc-orange-banana', 'pineapple-orange-nyc-banana', 'nyc-pineapple-orange-banana', 'pineapple-orange-banana-nyc'] >>>len(output) 311
Sortie:
def cart_p(d, c =[]):
if not d:
yield c
else:
for i in d[0]:
yield from cart_p(d[1:], c+[i])
def combo(d, c = []):
if len(c) == 3:
yield c
else:
yield c
for i in d:
if i not in c:
yield from combo(d, c+[i])
def group_result(r):
for a, b in r:
for i in range(1, len(a)):
yield '-'.join(a[:i]+[b]+a[i:])
yield from {'-'.join(a+[b]), '-'.join([b]+a)}
data = ['strawberry', 'apple', 'banana', 'orange', 'pineapple']
print(list(group_result(list(cart_p([list(combo(data)), ['nyc']])))))
p>
La sortie ci-dessus ressemble à elle n'ajoute que «nyc» à la fin de chaque ligne, pas à un point dans chaque ligne? Toutes mes excuses si ce n'était pas clair dans mon message.
@octothorpe_not_hashtag Pas de problème. Donc, quelque chose comme «fraise-nyc-pomme» , «fraise-nyc-pomme-banane» est également nécessaire?
Correct, ceux-ci sont également nécessaires
@octothorpe_not_hashtag Y aura-t-il toujours une seule valeur à ajouter, à savoir nyc , ou pourrait-il y avoir une liste des ajouts nécessaires tels que ['nyc', 'ma', 'ca'] < / code>?
Juste un, éventuellement il pourrait s'agir d'une entrée définie par l'utilisateur
@octothorpe_not_hashtag Ok, alors ma modification devrait toujours être pertinente pour le problème :)
Continuons cette discussion dans le chat .
Que diriez-vous de permuter deux fois? Pas très efficace pour les listes plus longues. Pour les listes plus longues, vous pouvez simplement insérer nyc dans toutes les positions au lieu de permuter. Je vous laisse l'optimisation de la boucle interne.
import itertools
import re
adjectives = ['strawberry', 'apple', 'banana', 'orange', 'pineapple']
root = 'nyc'
for i in range(len(adjectives)):
adj_perm = itertools.permutations(adjectives, i+1)
for perm in adj_perm:
perm = list(perm)
perm.append(root)
print(len(perm))
combined_perm = itertools.permutations(perm, len(perm))
for final_perm in combined_perm:
print("-".join(final_perm))
La sortie de ce code est beaucoup plus longue, il semble qu'il effectue toutes les permutations non seulement jusqu'à 4 mots?
Oh oui, tu as raison. Limitez la première plage à 3 au lieu de len (adjectifs) . Avec nyc , cela devrait être 4
Besoin d'ajouter une ligne pour supprimer les doublons et ajouter «nyc» par lui-même (également supprimé l'instruction d'impression à mi-fonction) .. fonctionne!
Cela me semble être une solution simple. Faites les permutations, puis ajoutez le «nyc» dans chaque position. J'ai évité de créer trop de résultats intermédiaires sous forme de listes complètes, cela devrait donc utiliser moins de mémoire que les solutions qui impliquent de créer des listes et de les élaguer. Je ne suis pas sûr des performances.
import itertools
adjectives = ['strawberry', 'apple', 'banana', 'orange', 'pineapple']
root = 'nyc'
targetlength = 4
def rootpermute(root, adjectives, N):
for group in itertools.permutations(adjectives, N-1):
for position in range(len(group) + 1):
newgroup = list(group)
newgroup.insert(position, root)
yield newgroup
perms = itertools.chain.from_iterable(rootpermute(root, adjectives, N)
for N in range(1, targetlength+1))
names = ['-'.join(group) for group in perms]
On dirait qu'il obtient le bon résultat! Je vais devoir analyser un peu plus, en tant que débutant. Je vais faire des tests.
IIUC vous pouvez utiliser la fonction suivante avec des permuations et une liste de compréhension pour obtenir toutes les combinaisons de N de longueur en insérant la racine à chaque index .
print(len(res)) #226
Vous pouvez maintenant appeler cette fonction pour obtenir les combinaisons de longueurs souhaitées:
res = list(chain.from_iterable(getPerms(i, root, adjectives) for i in range(4))) print(res) #['nyc', # 'nyc-strawberry', # 'nyc-apple', # 'nyc-banana', # 'nyc-orange', # 'nyc-pineapple', # 'nyc-strawberry-apple', # 'strawberry-nyc-apple', # 'nyc-strawberry-banana', # 'strawberry-nyc-banana', #... skipping ... #'pineapple-nyc-orange-apple', # 'pineapple-orange-nyc-apple', # 'nyc-pineapple-orange-banana', # 'pineapple-nyc-orange-banana', # 'pineapple-orange-nyc-banana']
Donc, pour obtenir la sortie finale souhaitée, vous pouvez enchaîner appelle ensemble getPerms jusqu'à la longueur 4:
print(getPerms(0, root, adjectives)) #['nyc'] print(getPerms(1, root, adjectives)) #['nyc-strawberry', 'nyc-apple', 'nyc-banana', 'nyc-orange', 'nyc-pineapple']
Cela produit une liste de sortie de 226 éléments: p >
from itertools import permutations, chain
def getPerms(N, root, adjectives):
"""N is the number of elements from adjectives to include in the output"""
if N == 0:
return [root]
return [
"-".join(p[:i] + (root, ) + p[i:])
for p in permutations(adjectives, N)
for i in range(N)
]