J'ai une chaîne qui montre le pas dans la grille m x n comme ce problème: https://leetcode.com/problems/unique-paths/
('R', 'D', 'R', 'D')
('R', 'D', 'D', 'R')
('D', 'R', 'R', 'D')
('D', 'D', 'R', 'R')
('D', 'R', 'D', 'R')
('R', 'R', 'D', 'D')
4 Réponses :
Essayez d'utiliser itertools.combinationss (étape, 4) au lieu de itertools.permutations (étape, 4)
itertools.combinationss (step, 4) renverra uniquement ('D', 'D', 'R', 'R')
utilisez ceci alors, itertools.combinations_with_replacement (étape, 4)
J'ai essayé des combinaisons, des combinaisons_with_replacement, des permutations et des produits également, mais je ne peux pas obtenir exactement ce que je veux
Non. itertools.permutations énumère toutes les permutations (avec des tonnes de doublons), mais c'est exagéré.
Le problème du code leet ne demande que le nombre de chemins uniques, pas une liste de chemins uniques, donc pour calculer le nombre, il vous suffit d'utiliser la formule de combinaison de C (n, k) = n! / (k! x (n - k)!) pour trouver le nombre de positions où les D s (ou R ) peuvent être placés hors de tout positions:
RRRRRRDD RRRRRDRD RRRRRDDR RRRRDRRD RRRRDRDR RRRRDDRR RRRDRRRD RRRDRRDR RRRDRDRR RRRDDRRR RRDRRRRD RRDRRRDR RRDRRDRR RRDRDRRR RRDDRRRR RDRRRRRD RDRRRRDR RDRRRDRR RDRRDRRR RDRDRRRR RDDRRRRR DRRRRRRD DRRRRRDR DRRRRDRR DRRRDRRR DRRDRRRR DRDRRRRR DDRRRRRR
pour que f (3, 2) renvoie: 3
et que f (7, 3) renvoie: 28
En revanche, si vous souhaitez produire une liste de chemins uniques, vous pouvez utiliser itertools.combinations pour faire la même chose que ci-dessus; autrement dit, pour trouver les positions où les D (ou R ) peuvent être placés hors de toutes les positions:
print(*f(7, 3), sep='\n')
pour que:
from itertools import combinations
def f(m, n):
for positions in map(set, combinations(range(m + n - 2), m - 1)):
yield ''.join('DR'[i in positions] for i in range(m + n - 2))
renvoie:
from math import factorial
def f(m, n):
return factorial(m + n - 2) / factorial(m - 1) / factorial(n - 1)
De toute façon, c'est une solution terriblement inefficace. Calculez simplement le nombre directement:
math.comb(m + n - 2, m - 1)
Notez que math.comb n'est disponible que dans Python 3.8+.
@blhsing Oui, et LeetCode exécute 3.8.1.
Pour obtenir la réponse dont vous avez besoin, vous pouvez utiliser multiset_permutations
>>> from math import factorial >>> factorial(4)//(factorial(2)*factorial(2)) 6
Pour obtenir uniquement le nombre total, utilisez la factorielle du nombre d'éléments divisé par le produit des factorielles pour le nombre de chaque élément unique. Ici, il y a 2 D et 2 R
>>> from sympy.utilities.iterables import multiset_permutations >>> from pprint import pprint >>> pprint(list(multiset_permutations(['D','D','R','R']))) [['D', 'D', 'R', 'R'], ['D', 'R', 'D', 'R'], ['D', 'R', 'R', 'D'], ['R', 'D', 'D', 'R'], ['R', 'D', 'R', 'D'], ['R', 'R', 'D', 'D']]
im obtenant une liste vide en utilisant
itertools.permutations (step, 4), peut-être que vous vouliez direstep = list ('DDRR')Avez-vous essayé
itertools.combinations ()?@zamir désolé, j'ai édité ma question, l'étape est une chaîne pas une liste
@Daniel J'ai essayé des combinaisons, des combinaisons_with_replacement, des permutations et des produits aussi, mais je ne peux pas obtenir exactement ce que je veux
Je soupçonne que tout algorithme pour calculer les permutations sans répétition ne sera pas plus efficace (peut-être moins efficace) que les itertools et la méthode set que vous mentionnez dans votre question, donc probablement pas la peine de vous inquiéter à moins que vous n'utilisiez des chaînes beaucoup plus longues. .
@SimonN Combien de temps? Pour
DDDDDRRRRRil y a déjà 3,6 millions de permutations mais seulement 252 différentes, donc une méthode raisonnable ne produisant que ces dernières ne devrait pas avoir de mal à être plus rapide.Vous voulez donc calculer le nombre de combinaisons distinctes de disposer exactement (m-1)
Dsymboles et (n-1)R, ou de manière équivalente nR < / code> symboles avec (m-1) barres|entre eux. (Vous n'avez pas besoin de calculer les combinaisons réelles, et pour m, n jusqu'à 100, ce serait prohibitif). Le nombre de façons est donné par la célèbre formule Stars-and-BarsTagué combinatoire
@SimonN: c'est totalement incorrect, rappelez-vous que C (n, k) est de l'ordre de O (2 ^ n), vous allez donc gaspiller la mémoire et le processeur très rapidement pour les valeurs non-jouets de n. [Souvenez-vous de l'identité que [somme (C (n, k)) sur k] = 2 ^ n]
@smci ouais, c'est exactement ce que je veux, mais je veux savoir comment nous pouvons le faire facilement (en codage) parce que je pense que c'est un problème courant.
Est-ce que cela répond à votre question? permutations avec des valeurs uniques