Combinatorial optimization to find the hand of "Millijan"

what is this

Solved "Improved algorithm that automatically determines the hand of" Mirijan "" using Combinatorial optimization in Python. I tried it.

Sample data

Use pattern 2 from the original article.

#Pattern 2
hands = ['Haruka', 'Chihaya', 'Miki', 'true', 'Takane', 'Yayoi', 'Festival', 'true美', 'Emily', 'Ami', 'Momoko', 'Iori', 'Raising']

hand_unit_list = [
 {'member': {'Iori', 'Emily'}, 'name': 'little trip around the world'},
 {'member': {'Emily', 'Festival'}, 'name': 'Charlotte Charlotte'},
 {'member': {'Mami', 'Yayoi'}, 'name': 'Wants →'},
 {'member': {'Chihaya', 'Haruka'}, 'name': 'CRIMSON LOVERS'},
 {'member': {'Miki', 'Iori'}, 'name': "First Don't worry"},
 {'member': {'Raising', 'Iori', 'Momoko'}, 'name': 'Kyun! Vampire girl'},
 {'member': {'true', 'Iori', 'Yayoi'}, 'name': 'Stand-by prince'},
 {'member': {'Miki', 'Iori', 'Takane'}, 'name': '99 Nights'},
 {'member': {'true', 'true美', 'Haruka'}, 'name': 'Don't bloom! !! Maiden Juku'},
 {'member': {'Miki', 'Chihaya', 'Haruka'}, 'name': 'Fate of the World'},
 {'member': {'Mami', 'Ami', 'Yayoi'}, 'name': 'Funny Logic'},
 {'member': {'Miki', 'Mami', 'Ami', 'Iori'}, 'name': 'Hoshisai Stepper'},
 {'member': {'Miki', 'Haruka', 'true', 'Chihaya', 'Yayoi'}, 'name': 'Merry'},
 {'member': {'Miki', 'Haruka', 'true', 'Chihaya', 'Emily'}, 'name': 'World changer'},
 {'member': {'Iori', 'Haruka', 'true', 'true美', 'Ami'}, 'name': 'Miracle Night'},
 {'member': {'Miki', 'Takane', 'true', 'true美', 'Yayoi', 'Ami'}, 'name': 'SHOW at The Live Revolution!'}
]

Try to solve

Let's solve it as Combination auction problem.

import pandas as pd
from pulp import lpSum
from ortoolpy import model_max, addbinvars, addvals
df = pd.DataFrame([hand_unit['name'] for hand_unit in hand_unit_list],
                  columns=['name'])
for hand in hands:
    df[hand] = False
for i, hand_unit in enumerate(hand_unit_list):
    for member in hand_unit['member']:
        df.loc[i, member] = True
addbinvars(df)

m = model_max()
m += lpSum(df.Var)
for hand in hands:
    m += lpSum(df[df[hand] == True].Var) <= 1
m.solve()
addvals(df)
print(df[df.Val > 0])
name Haruka Chihaya Miki true Takane Yayoi Festival Mami Emily Ami Momoko Iori Raising Var Val
1 Charlotte Charlotte False False False False False False True False True False False False False v000002 1
2 Wants → False False False False False True False True False False False False False v000003 1
3 CRIMSON LOVERS True True False False False False False False False False False False False v000004 1
5 Kyun! Vampire girl False False False False False False False False False False True True True v000006 1

I got the same result as the original article.

Recommended Posts

Combinatorial optimization to find the hand of "Millijan"
The power of combinatorial optimization solvers
How to find the area of the Voronoi diagram
Minimize the number of polishings by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
Combinatorial optimization to investigate stars
I tried to find the entropy of the image with python
How to find the optimal number of clusters in k-means
Let's decide the lecture of PyCon JP 2016 by combinatorial optimization
I tried to find the average of the sequence with TensorFlow
Let's decide the position of the fire station by combinatorial optimization
Inherit the standard library to find the average value of Queue
How to find the scaling factor of a biorthogonal wavelet
Find the definition of the value of errno
Pave the road with combinatorial optimization
Design of experiments and combinatorial optimization
Supplement to the explanation of vscode
How to find the memory address of a Pandas dataframe value
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems
[Python] A simple function to find the center coordinates of a circle
The story of trying to reconnect the client
Script to change the description of fasta
10 methods to improve the accuracy of BERT
How to check the version of Django
The story of adding MeCab to ubuntu 16.04
How to find out the number of CPUs without using the sar command
Migemo version of the: find command,: mfind
I tried to find the optimal path of the dreamland by (quantum) annealing
Find the minimum value of a function by particle swarm optimization (PSO)
The story of pep8 changing to pycodestyle
Find the coefficients of the least squares polynomial
[Circuit x Python] How to find the transfer function of a circuit using Lcapy
A programming beginner tried to find out the execution time of sorting etc.
[Scientific / technical calculation by Python] Numerical calculation to find the value of derivative (differential)
[Scientific / technical calculation by Python] Analytical solution to find the solution of equation sympy
How to find the coefficient of the trendline that passes through the vertices in Python
[Verification] Try to align the point cloud with the optimization function of pytorch Part 1
How to calculate the volatility of a brand
Combinatorial optimization --Typical problem-- Partition of a set problem
Setting to output the log of cron execution
The inaccuracy of Tensorflow was due to log (0)
Let's decide the date course by combinatorial optimization
Set the range of active strips to the preview range
I tried to find 100 million digits of pi
I tried to touch the API of ebay
Find the number of days in a month
I tried to correct the keystone of the image
Change the decimal point of logging from, to.
Find the divisor of the value entered in python
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Find the solution of the nth-order equation in python
Find out the day of the week with datetime
Find the geometric mean of n! Using Python
To get the path of the currently running python.exe
[Introduction to Algorithm] Find the shortest path [Python3]
I want to customize the appearance of zabbix
Move your hand to understand the chi-square distribution
From the introduction of pyethapp to the execution of contract
Try to simulate the movement of the solar system
The story of moving from Pipenv to Poetry