Find all patterns to extract a specific number from the set

Overview

Find the algorithm to write out all the patterns of the small set extracted from the set of 5 I referred to here.

(Addition) There is a convenient library, so let's use it. Thank you for telling me.

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

The language used is python. 4.png

algorithm

All patterns to take out 2 to 3 (if it does not disappear even if taken out) 5.png

Create a function called "choice" that extracts one from the whole set. If you take out one with "choice", increase the depth by one and call "choice" again. When the depth reaches the number to be taken out, it will come back. Now you can generate all the patterns.

If you want to take it out and disappear, you can execute "choice" and pass the whole set excluding the selected one to the next "choice".

One problem is that this is There is a problem that the same patterns of [red, green] and [green, red] are mixed. There is no help for it here, so check if there is the same element, and if there is, delete one. Please let me know if there is a better way.

program


import copy

class Allpattern():
    def __init__(self,n,r):
        self.n = n  #n Of these, r all patterns to take out
        self.r = r
        self.pattern = []
        used = [0] * self.n
        hoge =[]
        for i in range(r):
            hoge.append(used)
            
    def make(self):
        """
        list1 = [1 ,・ ・ ・ ・, n]Make the whole set
        """
        list1=[]
        for i in range(self.n):
            list1.append(i+1)
        
        """
        choice_list: A list to put the choices
        depth       :Number of choices
        """
        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)                           #Choose once and never choose again
            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):
        """
It is called when the selection of r is completed.
        """        
        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()
    
    

Execution result

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

Recommended Posts

Find all patterns to extract a specific number from the set
Find a guideline for the number of processes / threads to set in the application server
Extract the value closest to a value from a Python list element
How to extract the desired character string from a line 4 commands
Find the number of days in a month
How to extract coefficients from a fractional formula
Set the number of elements in a NumPy one-dimensional array to a power of 2 (0 padded)
Find the ideal property by scraping! A few minutes walk from the property to the destination
Use python's pixivpy to download all the works of a specific user from pixiv at once (including moving)
How to post a ticket from the Shogun API
Python --Read data from a numeric data file to find the covariance matrix, eigenvalues, and eigenvectors
[Python] Programming to find the number of a in a character string that repeats a specified number of times.
How to find the average amount of information (entropy) of the original probability distribution from a sample
Extract only the sound of a specific instrument from a MIDI file and make it a separate file
How to get only the data you need from a structured data set using a versatile method
I tried to find the trend of the number of ships in Tokyo Bay from satellite images.
[Python] A program to find the number of apples and oranges that can be harvested
Define a task to set the fabric env in YAML
How to find the optimal number of clusters in k-means
Let Code Day 64 starting from zero "287. Find the Duplicate Number"
[python] Change the image file name to a serial number
A program that removes specific characters from the entered text
Get the number of specific elements in a python list
How to extract other than a specific index with Numpy
How to find the scaling factor of a biorthogonal wavelet
After all, the story of returning from Linux to Windows
Extract specific languages from Wiktionary
I tried to sort out the objects from the image of the steak set meal-② Overlap number sorting
Extract the index of the original set list that corresponds to the list of subsets.
How to get all the possible values in a regular expression
Read all the contents of proc / [pid] ~ From setgroups to wchan ~
TensorFlow To learn from a large number of images ... ~ (almost) solution ~
From a book that programmers can learn (Python): Find the mode
I want to find the shortest route to travel through all points
Read all the contents of proc / [pid] ~ From cwd to loginuid ~
How to find the memory address of a Pandas dataframe value
Read all the contents of proc / [pid] ~ From map_files to numa_maps ~
Read all the contents of proc / [pid] ~ From oom_adj to sessionid ~
I tried to cut out a still image from the video
A script that returns 0, 1 attached to the first Python prime number
Read all the contents of proc / [pid] ~ from attr to cpuset ~
[Python] A simple function to find the center coordinates of a circle
A story about creating a program that will increase the number of Instagram followers from 0 to 700 in a week
Extract specific data from complex JSON
Extract a page from a Wikipedia dump
[Python] What is a formal argument? How to set the initial value
Use shutil to delete all folders with a small number of files
I tried to verify the best way to find a good marriage partner
[Python] A program that calculates the number of socks to be paired
I want to send a signal only from the sub thread to the main thread
How to find out the number of CPUs without using the sar command
[Python memo] I want to get a 2-digit hexadecimal number from a decimal number
Extract lines that match the conditions from a text file with python
Command to find the desired header file from the GCC, Clang include directories
[Python] How to use the enumerate function (extract the index number and element)
How to find a specific type (str, float etc) column in a DataFrame column
[Development environment] How to create a data set close to the production DB
How to play a video while watching the number of frames (Mac)
Let Code Day 66 "438. Find All Anagrams in a String" starting from scratch
TensorFlow To learn from a large number of images ... (Unsolved problem) → 12/18 Solved
Try to extract specific data from JSON format data in object storage Cloudian/S3