[PYTHON] Finden Sie alle Muster, um eine bestimmte Zahl aus dem Satz zu extrahieren

Überblick

Finden Sie den Algorithmus, um alle Muster der kleinen Menge zu schreiben, die aus der Menge von 5 extrahiert wurden Ich habe auf [hier] verwiesen (http://www.nct9.ne.jp/m_hiroi/linux/clang04.html#ans09).

(Zusatz) Es gibt eine praktische Bibliothek, also lasst es uns benutzen. Danke, dass du es mir gesagt hast.

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

Die verwendete Sprache ist Python.

Algorithmus

Alle Muster 2 bis 3 herausnehmen (wenn es nicht verschwindet, auch wenn es herausgenommen wird)

Erstellen Sie eine Funktion namens "Auswahl", um eine aus dem gesamten Satz zu extrahieren. Wenn Sie eine mit "Auswahl" herausnehmen, erhöhen Sie die Tiefe um eins und rufen Sie erneut "Auswahl" auf. Wenn die Tiefe die herauszunehmende Zahl erreicht, kommt sie zurück. Jetzt können Sie alle Muster generieren.

Wenn Sie es herausnehmen und verschwinden möchten, führen Sie einfach "Auswahl" aus und übergeben Sie den gesamten Satz mit Ausnahme des ausgewählten an die nächste "Auswahl".

Ein Problem ist dies Es besteht das Problem, dass die gleichen Muster von [rot, grün] und [grün, rot] gemischt werden. Hier gibt es keine Hilfe dafür. Überprüfen Sie daher, ob es dasselbe Element gibt, und löschen Sie gegebenenfalls eines. Bitte lassen Sie mich wissen, ob es einen besseren Weg gibt.

Programm

import copy

class Allpattern():
    def __init__(self,n,r):
        self.n = n  #n Davon sind alle Muster herauszunehmen
        self.r = r
        self.pattern = []
        used = [0] * self.n
        hoge =[]
        for i in range(r):
            hoge.append(used)
            
    def make(self):
        """
        list1 = [1 ,・ ・ ・ ・, n]Mach das ganze Set
        """
        list1=[]
        for i in range(self.n):
            list1.append(i+1)
        
        """
        choice_Liste: Eine Liste, in der Sie Ihre Auswahl treffen können
        depth       :Anzahl der Auswahlmöglichkeiten
        """
        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)                           #Einmal wählen und nie wieder wählen
            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):
        """
Es wird aufgerufen, wenn die Auswahl von r abgeschlossen ist.
        """        
        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()
    
    

Ausführungsergebnis

[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]