Quand j'ai vu le programme qui énumère l'ordre et les combinaisons que j'ai fait il y a longtemps, je ne pouvais pas comprendre immédiatement comment je l'avais fait, alors j'ai essayé de le recréer en tant que critique. J'écrirai un article pour ne pas l'oublier.
Cependant, le programme de cet article n'en vaut pas la peine, car il est facile à trouver avec itertools. De plus, la documentation officielle de Python contient également un programme concis et beau qui demande des séquences et des combinaisons. C'est juste un mémo d'étude personnel.
Fabriqué avec Python 3.6.1.
Chacun doit être écrit comme suit.
--Données données (liste ou tuple): données --Longueur des données: n --Nombre à choisir: r --Nombre total de séquences dupliquées: H (n, r) --Nombre total de colonnes: P (n, r) --Nombre total de combinaisons en double: Π (n, r) --Nombre total de combinaisons: C (n, r)
itertools
Ce que vous êtes sur le point de trouver peut être trouvé en utilisant itertools.
list(itertools.product(data, repeat=r))
--Commande:
list(itertools.permutations(data, r))
--Combinaison en double:
list(itertools.combinations_with_replacement(data, r))
--Combinaison:
list(itertools.combinations(data, r))Tout d'abord, par souci de simplicité, considérons uniquement le cas de l'extraction de trois à partir des données données (r = 3).
La commande avec des doublons est
C'est. Pour trouver une paire
Le processus appelé est exécuté. Afin de demander toutes les paires
Réduisez la boucle comme ceci. Si vous essayez de créer un programme immédiatement, ce sera comme suit.
result = []
for i in data:
for j in data:
for k in data:
result.append([i, j, k])
Avec la notation d'inclusion de liste
result = [[i, j, k] for i in data for j in data for k in data]
Cependant, la notation d'inclusion de liste n'est pas utilisée pour le traitement essentiel. De plus, bien qu'il soit un peu redondant d'y penser plus tard, je vais demander l'index et ensuite obtenir le contenu des données comme suit.
result = []
for i in range(len(data)):
for j in range(len(data)):
for k in range(len(data)):
result.append([data[i], data[j], data[k]])
L'ordre est
C'est. En d'autres termes, il peut être obtenu en ajoutant un processus qui rend impossible la récupération de ce qui a été retiré une fois au processus de la commande avec des doublons. Par conséquent, le processus pour trouver un ensemble est le suivant.
Le reste de la structure peut être réalisé de la même manière qu'une séquence séquentielle avec des doublons. Vous pouvez également le demander en supprimant les doublons de la commande dupliquée. Cependant, je ne considérerai pas cette méthode car il y a beaucoup de répétitions inutiles.
Le programme ressemble à ceci: Ici, nous définissons et utilisons la fonction listExcludedIndices, qui renvoie une liste excluant celle qui a été récupérée une fois.
def listExcludedIndices(data, indices=[]):
return [x for i, x in enumerate(data) if i not in indices]
result = []
for i in range(len(data)):
for j in range(len(data) - 1):
for k in range(len(data) - 2):
jData = listExcludedIndices(data, [i])
kData = listExcludedIndices(jData, [j])
result.append([data[i], jData[j], kData[k]])
Combinaisons avec chevauchement
C'est. Considérons 2. en détail. Si les données fournies sont «[1,2,3,4]», alors «[1,1,2]» et «[1,2,1]» et «[2,1,1]» sont C'est le même. En d'autres termes, contrairement à l'ordre avec des doublons, si vous trouvez toutes les paires qui incluent des 1, vous n'avez pas besoin de trouver les paires qui incluent des 1 après cela. Pour ce faire, vous pouvez décaler la position de départ de la boucle imbriquée. Je pense que cela peut être exprimé comme suit.
Le programme est le suivant.
result = []
for i in range(len(data)):
for j in range(i, len(data)):
for k in range(j, len(data)):
result.append([data[i], data[j], data[k]])
La combinaison est
C'est. Par conséquent, le processus de recherche d'un ensemble est le suivant, tout comme lors de la recherche de la séquence.
Vous pouvez déplacer la position de la boucle de la même manière que la combinaison avec chevauchement. Faisons un programme basé sur l'idée ci-dessus.
result = []
for i in range(len(data)):
for j in range(i, len(data) - 1):
for k in range(j, len(data) - 2):
jData = listExcludedIndices(data, [i])
kData = listExcludedIndices(jData, [j])
result.append([data[i], jData[j], kData[k]])
Cependant, il y a des doublons
Le but était de permettre la duplication, donc si vous n'autorisez pas la duplication,
Peut être. En d'autres termes, le programme peut être réécrit comme suit.
result = []
for i in range(len(data)):
for j in range(i + 1, len(data)):
for k in range(j + 1, len(data)):
result.append([data[i], data[j], data[k]])
Il peut également être obtenu en supprimant les doublons des combinaisons avec des doublons, comme les colonnes avant et les colonnes avant avec des doublons.
Dans les programmes jusqu'à ce qui précède, r a été fixé. Puisqu'il est inutile tel qu'il est, il sera transformé en fonction. Tout d'abord, convertissez ce que vous avez écrit de manière fixe en récursif. Chacun a une structure dans laquelle une boucle qui se répète n fois est imbriquée r fois. Il semble que l'imbrication r devrait être réalisée par appel récursif, et n boucles devraient être réalisées par 1 appel récursif. Ensuite, si vous définissez la condition de fin de récurrence sur 0 lorsque r devient 0, vous pouvez le convertir en récursif.
Dans le cas d'une séquence avec doublons, le plus simple est le suivant. La valeur obtenue dans un appel est considérée comme une progression, et cette valeur moins r est transmise au prochain appel récursif. Lorsque r devient 0, enregistrez le contenu de la progression dans le résultat et quittez. La fonction qui trouve réellement l'élément doit donner une valeur initiale. Comme il est difficile à utiliser tel quel, je définis une fonction wrapper et je l'appelle.
def permutationWithRepetitionListRecursive(data, r):
if r <= 0:
return []
result = []
_permutationWithRepetitionListRecursive(data, r, [], result)
return result
def _permutationWithRepetitionListRecursive(data, r, progress, result):
if r == 0:
result.append(progress)
return
for i in range(len(data)):
_permutationWithRepetitionListRecursive(data, r - 1, progress + [data[i]], result)
Puisque la séquence ne permet pas la réextraction, elle peut être obtenue en ajoutant le traitement. Dans la colonne de commande avec doublons, les données ont été passées à l'appel suivant telles quelles, mais ici nous passerons le reste à l'exclusion de celui récupéré une fois.
def permutationListRecursive(data, r):
if r <= 0 or r > len(data):
return []
result = []
_permutationListRecursive(data, r, [], result)
return result
def _permutationListRecursive(data, r, progress, result):
if r == 0:
result.append(progress)
return
for i in range(len(data)):
_permutationListRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]], result)
Pour les combinaisons en double, ajoutez un argument qui représente la position de départ, donnez à cet argument la position de récupération actuelle et effectuez le prochain appel récursif. À part cela, il n'y a aucune différence avec la commande avec des doublons.
def combinationWithRepetitionListRecursive(data, r):
if r <= 0:
return []
result = []
_combinationWithRepetitionListRecursive(data, r, 0, [], result)
return result
def _combinationWithRepetitionListRecursive(data, r, start, progress, result):
if r == 0:
result.append(progress)
return
for i in range(start, len(data)):
_combinationWithRepetitionListRecursive(data, r - 1, i, progress + [data[i]], result)
La combinaison garantit que le prochain appel récursif est effectué un pas en avant de la position d'extraction actuelle.
def combinationListRecursive(data, r):
if r == 0 or r > len(data):
return []
result = []
_combinationListRecursive(data, r, 0, [], result)
return result
def _combinationListRecursive(data, r, start, progress, result):
if r == 0:
result.append(progress)
return
for i in range(start, len(data)):
#Une autre solution_combinationListRecursive(listExcludedIndices(data, [i]), r - 1, i, progress + [data[i]], result)
_combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)
La réception est dangereuse car elle peut provoquer un débordement de pile, pensez donc à une fonction qui utilise des boucles. Fondamentalement, il faut r boucles pour trouver un élément, et vous n'avez qu'à le répéter autant de fois que nécessaire. Le nombre total de chacun est officiellement calculé immédiatement, alors utilisez-le. De plus, dans ce qui suit, nous envisageons une méthode de résolution basée sur la position (indice) pour tout retirer.
Si n = 4 et r = 3, l'ordre des doublons à obtenir est le suivant.
00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 0 -> data[0] data[1] data[0]
05: 0 1 1 -> data[0] data[1] data[1]
06: 0 1 2 -> data[0] data[1] data[2]
07: 0 1 3 -> data[0] data[1] data[3]
08: 0 2 0 -> data[0] data[1] data[0]
09: 0 2 1 -> data[0] data[1] data[1]
10: 0 2 2 -> data[0] data[1] data[2]
11: 0 2 3 -> data[0] data[1] data[3]
...
L'ordre avec les doublons est le même que pour trouver le nombre n-aire de r chiffres.
Lorsque le nombre de chiffres est représenté par d, chaque chiffre compte tous les «n ^ d» de la même manière qu'un nombre n-aire.
Si vous représentez un élément par i maintenant, vous pouvez trouver l'indice de ce chiffre en divisant i par n ^ d.
Cela dépassera la taille des données, vous devez donc les diviser par n comme le reste.
Le programme ressemble à ceci:
import math
def permutationWithRepetition(n, r):
return int(pow(n, r))
def permutationWithRepetitionList(data, r):
length = len(data)
total = permutationWithRepetition(length, r)
result = []
for i in range(total):
element = []
for digit in reversed(range(r)):
element.append(data[int(i / pow(length, digit)) % length])
result.append(element)
return result
Si n = 4 et r = 3, l'ordre à obtenir est le suivant.
00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 1 -> data[0] data[2] data[1]
03: 0 2 3 -> data[0] data[2] data[3]
04: 0 3 1 -> data[0] data[3] data[1]
05: 0 3 2 -> data[0] data[3] data[2]
06: 1 0 2 -> data[1] data[0] data[2]
07: 1 0 3 -> data[1] data[0] data[3]
08: 1 2 0 -> data[1] data[2] data[0]
09: 1 2 3 -> data[1] data[2] data[3]
10: 1 3 0 -> data[1] data[3] data[0]
11: 1 3 2 -> data[1] data[3] data[2]
12: 2 0 1 -> data[2] data[0] data[1]
13: 2 0 3 -> data[2] data[0] data[3]
14: 2 1 0 -> data[2] data[1] data[0]
15: 2 1 3 -> data[2] data[1] data[3]
16: 2 3 0 -> data[2] data[3] data[0]
17: 2 3 1 -> data[2] data[3] data[1]
18: 3 0 1 -> data[3] data[0] data[1]
19: 3 0 2 -> data[3] data[0] data[2]
20: 3 1 0 -> data[3] data[1] data[0]
21: 3 1 2 -> data[3] data[1] data[2]
22: 3 2 0 -> data[3] data[2] data[0]
23: 3 2 1 -> data[3] data[2] data[2]
Ceci est également susceptible d'être obtenu à partir du numéro d'élément i et du chiffre d.
Tout d'abord, considérons le troisième chiffre. Le même nombre apparaît de 1 à 4. En d'autres termes, si vous divisez P (n, r) par n, vous pouvez trouver la position à compter.
Considérez le deuxième chiffre. Ici, des nombres autres que ceux apparaissant dans le troisième chiffre apparaîtront. Le nombre total est n-1. Cela apparaîtra uniformément lorsque le troisième chiffre est le même nombre. En d'autres termes, il compte avec P (n, r) / (n \ * n-1).
Si vous pensez au premier chiffre de la même manière, vous pouvez voir qu'il compte avec P (n, r) / (n \ * n-1 \ * n-2).
Faisons un programme à partir de l'idée ci-dessus.
import math
import functools
import operator
def permutation(n, r):
if(n < r):
return 0
return int(math.factorial(n) / math.factorial(n - r))
def permutationList(data, r):
length = len(data)
total = permutation(length, r)
result = []
for i in range(total):
element = []
copyData = data[:]
for digit in range(r):
l = len(copyData)
countUp = total / functools.reduce(operator.mul, range(l, length + 1))
index = int(i / countUp) % l
element.append(copyData.pop(index))
result.append(element)
return result
Si n = 4 et r = 3, la combinaison avec duplication à obtenir est la suivante.
00: 0 0 0 -> data[0] data[0] data[0]
01: 0 0 1 -> data[0] data[0] data[1]
02: 0 0 2 -> data[0] data[0] data[2]
03: 0 0 3 -> data[0] data[0] data[3]
04: 0 1 1 -> data[0] data[1] data[1]
05: 0 1 2 -> data[0] data[1] data[2]
06: 0 1 3 -> data[0] data[1] data[3]
07: 0 2 2 -> data[0] data[2] data[2]
08: 0 2 3 -> data[0] data[2] data[3]
09: 0 3 3 -> data[0] data[3] data[3]
10: 1 1 1 -> data[1] data[1] data[1]
11: 1 1 2 -> data[1] data[1] data[2]
12: 1 1 3 -> data[1] data[1] data[3]
13: 1 2 2 -> data[1] data[2] data[2]
14: 1 2 3 -> data[1] data[2] data[3]
15: 1 3 3 -> data[1] data[3] data[3]
16: 2 2 2 -> data[2] data[2] data[2]
17: 2 2 3 -> data[2] data[2] data[3]
18: 2 3 3 -> data[2] data[3] data[3]
19: 3 3 3 -> data[3] data[3] data[3]
Cela semble difficile à trouver à partir du numéro d'élément, alors essayez de trouver l'élément suivant de l'élément précédent. En se concentrant sur le 1er chiffre, la valeur précédente est +1 sauf lorsque le 2ème ou 3ème chiffre a été modifié. Par conséquent, il semble qu'il puisse être contrôlé en détectant le décompte des 2ème et 3ème chiffres. Si vous extrayez l'endroit où le deuxième chiffre compte,
0 0 3 -> 0 1 1
0 1 3 -> 0 2 2
0 2 3 -> 0 3 3
Ce qu'ils ont en commun est
est. De la même manière, si vous extrayez l'endroit où le troisième chiffre compte,
0 3 3 -> 1 1 1
1 3 3 -> 2 2 2
2 3 3 -> 3 3 3
Ce qu'ils ont en commun est
est.
Si vous mettez cela dans une fonction
--N-1 vient au chiffre i de l'élément précédent --i + 1 ajouter +1 au premier chiffre --Faites i + 1 chiffres et plus tard les mêmes que i + 1 chiffres
Ça va être bien. C'est un programme compliqué, mais il ressemble à ceci: Ici, la fonction getListElements qui obtient la valeur de l'ensemble d'index est définie et utilisée.
def getListElements(lis, indices):
"""Renvoie l'ensemble des éléments indiqués par les indies de la liste"""
return [lis[i] for i in indices]
import math
def combinationWithRepetition(n, r):
return int(math.factorial(r + n - 1) / (math.factorial(r) * math.factorial(n - 1)))
def updateCombinationIndex(lastIndex, start, repetition=False):
result = lastIndex[:start]
x = lastIndex[start] + 1
for i in range(start, len(lastIndex)):
result.append(x)
if(repetition == False):
x += 1
return result
def getComginationWithRepetitionIndex(length, r, lastIndex):
result = []
for i in range(r):
if(len(lastIndex) == 0):
result.append(0)
elif(lastIndex[i] >= length - 1):
result = updateCombinationIndex(lastIndex, i - 1, True)
break
elif(i == r - 1):
result = updateCombinationIndex(lastIndex, i, True)
return result
def combinationWithRepetitionList(data, r):
length = len(data)
total = combinationWithRepetition(length, r)
result = []
lastIndex = []
for i in range(total):
lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
result.append(getListElements(data, lastIndex))
return result
Si n = 4 et r = 3, la combinaison à obtenir est la suivante.
00: 0 1 2 -> data[0] data[1] data[2]
01: 0 1 3 -> data[0] data[1] data[3]
02: 0 2 3 -> data[0] data[2] data[3]
03: 1 2 3 -> data[1] data[2] data[3]
J'essaierai de le trouver de la même manière que la combinaison avec duplication. C'est difficile à comprendre car il y a peu d'exemples concrets, mais l'endroit où le deuxième chiffre compte est
L'endroit où le troisième chiffre compte est
C'est comme ça.
--N-i vient au chiffre i de l'élément précédent --i + 1 ajouter +1 au premier chiffre --i + 1-Définit le nième chiffre sur l'élément de i + 1 + n
Si vous modifiez les conditions de comptage et les modifications, vous pouvez le faire de la même manière qu'une combinaison avec duplication. Le programme ressemble à ceci:
import math
def combination(n, r):
if(n < r):
return 0
return int(math.factorial(n) / (math.factorial(r) * math.factorial(n - r)))
def getComginationIndex(length, r, lastIndex):
result = []
for i in range(r):
if(len(lastIndex) == 0):
result.append(i)
elif(lastIndex[i] >= length - r + i):
result = updateCombinationIndex(lastIndex, i - 1, False)
break
elif(i == r - 1):
result = updateCombinationIndex(lastIndex, i, False)
return result
def combinationList(data, r):
length = len(data)
total = combination(length, r)
result = []
lastIndex = []
for i in range(total):
lastIndex = getComginationIndex(length, r, lastIndex)
result.append(getListElements(data, lastIndex))
return result
Depuis que je l'ai fait avec Python, je vais l'essayer en tant que générateur. Je sais que la version récursive du générateur fonctionne si je l'écris comme ça, mais je ne sais pas pourquoi je devrais le faire. De plus, on ne sait pas que si l'opération est arrêtée dans une pile profonde avec le générateur de version récursive, la mémoire sera surchargée.
Si vous le créez avec seulement yield, ce sera comme suit.
Je suis yield pour retourner une valeur quand r est 0, et comme la fonction récursive elle-même retourne un generalta, je la tourne avec une instruction for pour la tourner.
J'ai essayé d'utiliser les données passées à la fonction récursive comme générateur, mais je ne pouvais pas m'en rendre compte à cause de la difficulté jusqu'à présent.
def permutationWithRepetitionGeneratorRecursive(data, r):
if r <= 0:
return []
return _permutationWithRepetitionGeneratorRecursive(data, r, [])
def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
if r == 0:
yield progress
return
for i in range(len(data)):
for j in _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]]):
yield j
En utilisant yield from, nous obtenons:
Deux «rendements» sont sortis et ce n'était pas de mauvaise humeur, donc c'est agréable et rafraîchissant.
def _permutationWithRepetitionGeneratorRecursive(data, r, progress):
if r == 0:
yield progress
return
for i in range(len(data)):
yield from _permutationWithRepetitionGeneratorRecursive(data, r - 1, progress + [data[i]])
def permutationGeneratorRecursive(data, r):
if r <= 0 or r > len(data):
return []
return _permutationGeneratorRecursive(data, r, [])
def _permutationGeneratorRecursive(data, r, progress):
if r == 0:
yield progress
return
for i in range(len(data)):
yield from _permutationGeneratorRecursive(listExcludedIndices(data, [i]), r - 1, progress + [data[i]])
def combinationWithRepetitionGeneratorRecursive(data, r):
if r <= 0:
return []
return _combinationWithRepetitionGeneratorRecursive(data, r, 0, [])
def _combinationWithRepetitionGeneratorRecursive(data, r, start, progress):
if r == 0:
yield progress
return
for i in range(start, len(data)):
yield from _combinationWithRepetitionGeneratorRecursive(data, r - 1, i, progress + [data[i]])
def combinationGeneratorRecursive(data, r):
if r == 0 or r > len(data):
return []
return _combinationGeneratorRecursive(data, r, 0, [])
def _combinationGeneratorRecursive(data, r, start, progress):
if r == 0:
yield progress
return
for i in range(start, len(data)):
yield from _combinationGeneratorRecursive(data, r - 1, i + 1, progress + [data[i]])
def permutationWithRepetitionGenerator(data, r):
length = len(data)
total = permutationWithRepetition(length, r)
for i in range(total):
element = []
for digit in reversed(range(r)):
element.append(data[int(i / pow(length, digit)) % length])
yield element
def permutationGenerator(data, r):
length = len(data)
total = permutation(length, r)
for i in range(total):
element = []
copyData = data[:]
for digit in range(r):
l = len(copyData)
countUp = total / functools.reduce(operator.mul, range(l, length + 1))
index = int(i / countUp) % l
element.append(copyData.pop(index))
yield element
def combinationWithRepetitionGenerator(data, r):
length = len(data)
total = combinationWithRepetition(length, r)
lastIndex = []
for i in range(total):
lastIndex = getComginationWithRepetitionIndex(length, r, lastIndex)
yield getListElements(data, lastIndex)
def combinationGenerator(data, r):
length = len(data)
total = combination(length, r)
lastIndex = []
for i in range(total):
lastIndex = getComginationIndex(length, r, lastIndex)
yield getListElements(data, lastIndex)
C'est difficile avec les mots. Plutôt que de penser à la théorie / solution puis d'en faire un programme, j'avais l'impression de penser à une solution / théorie du programme, donc le texte n'était pas très bon. De plus, il y a des endroits où les explications sont sautées. Un tel endroit est un endroit où je ne comprenais pas assez ou je me demandais quoi faire avec l'expression.
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = list(range(r))
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
def combinations(iterable, r):
pool = tuple(iterable)
n = len(pool)
for indices in permutations(range(n), r):
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)
def combinations_with_replacement(iterable, r):
# combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC
pool = tuple(iterable)
n = len(pool)
if not n and r:
return
indices = [0] * r
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != n - 1:
break
else:
return
indices[i:] = [indices[i] + 1] * (r - i)
yield tuple(pool[i] for i in indices)
def combinations_with_replacement(iterable, r):
pool = tuple(iterable)
n = len(pool)
for indices in product(range(n), repeat=r):
if sorted(indices) == list(indices):
yield tuple(pool[i] for i in indices)
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = list(range(n))
cycles = list(range(n, n-r, -1))
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
def product(*args, repeat=1):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = [tuple(pool) for pool in args] * repeat
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
Recommended Posts