[PYTHON] Trouvez tous les modèles pour extraire un nombre spécifique de l'ensemble

Aperçu

Trouvez l'algorithme pour écrire tous les motifs du petit ensemble extrait de l'ensemble de 5 J'ai fait référence à ici.

(Une addition) Il existe une bibliothèque pratique, alors utilisons-la. Merci de me l'avoir dit.

from itertools import combinations
list(combinations([1,2,4,3],3))
>>[(1, 2, 4), (1, 2, 3), (1, 4, 3), (2, 4, 3)]

Le langage utilisé est le python.

algorithme

Tous les motifs à retirer 2 à 3 (s'il ne disparaît pas même s'il est retiré)

Créez une fonction appelée "choix" pour en extraire une de l'ensemble complet. Si vous en retirez un avec «choix», augmentez la profondeur de un et appelez à nouveau «choix». Lorsque la profondeur atteint le nombre à retirer, elle reviendra. Vous pouvez maintenant générer tous les modèles.

Si vous voulez le retirer et le faire disparaître, exécutez simplement "choix" et passez l'ensemble entier en excluant celui sélectionné au "choix" suivant.

Un problème est le suivant Il y a un problème que les mêmes motifs de [rouge, vert] et [vert, rouge] sont mélangés. Il n'y a pas d'aide pour cela ici, alors vérifiez si le même élément existe, et si c'est le cas, supprimez-en un. S'il vous plaît laissez-moi savoir s'il existe une meilleure façon.

programme

import copy

class Allpattern():
    def __init__(self,n,r):
        self.n = n  #n Parmi ceux-ci, r tous les modèles à supprimer
        self.r = r
        self.pattern = []
        used = [0] * self.n
        hoge =[]
        for i in range(r):
            hoge.append(used)
            
    def make(self):
        """
        list1 = [1 ,・ ・ ・ ・, n]Faire l'ensemble
        """
        list1=[]
        for i in range(self.n):
            list1.append(i+1)
        
        """
        choice_list: Une liste pour mettre les choix
        depth       :Nombre de choix
        """
        choice_list = []
        depth = 0
        self.choice(list1,depth,choice_list)
        
    def choice(self,list1,depth,choice_list):
        for i in list1:
            list2 = copy.deepcopy(list1)
            list2.remove(i)                           #Choisissez une fois et ne choisissez plus jamais
            choice_list2 = copy.deepcopy(choice_list)
            choice_list2.append(i)
            if depth+1 >= self.r:
                self.work(choice_list2)
            else:
                self.choice(list2,depth+1,choice_list2)
            
    def work(self,choice_list):
        """
Il est appelé lorsque la sélection de r est terminée.
        """        
        choice_list.sort()
        if self.pattern.count(choice_list) == 0:
            self.pattern.append(choice_list)
        
    def disp(self):
        for i in self.pattern:
            print(i)
        
if __name__ == '__main__' :
    hoge = Allpattern(5,3)
    hoge.make()
    hoge.disp()
    
    

Résultat d'exécution

[1, 2, 3]
[1, 2, 4]
[1, 2, 5]
[1, 3, 4]
[1, 3, 5]
[1, 4, 5]
[2, 3, 4]
[2, 3, 5]
[2, 4, 5]
[3, 4, 5]