R - Сочетания кадра данных с ограничениями

Question

Я пытаюсь создать скрипт R для фэнтези-футбола (правильный футбол в Великобритании, а не рука яйцо :-)), где я могу ввести список игроков в csv и он будет плевать из каждой комбинации из 11 игроков, которые отвечают различным ограничениям.

Вот мой пример dataframe:

df <- read.csv("Filename.csv", 
       header = TRUE) 
    > print(df) 
         Name Positon Team Salary 
    1    Eric Dier  D TOT 9300000 
    2   Erik Pieters  D STO 9200000 
    3  Christian Fuchs  D LEI 9100000 
    4  Héctor Bellerín  D ARS 9000000 
    5  Charlie Daniels  D BOU 9000000 
    6   Ben Davies  D TOT 8900000 
    7 Federico Fernández  D SWA 8800000 
    8  Per Mertesacker  D ARS 8800000 
    9  Alberto Moreno  D LIV 8700000 
    10  Chris Smalling  D MUN 8700000 
    11  Seamus Coleman  D EVE 8700000 
    12  Jan Vertonghen  D TOT 8700000 
    13  Romelu Lukaku  F EVE 12700000 
    14   Harry Kane  F TOT 12500000 
    15   Max Gradel  F BOU 11900000 
    16  Alexis Sánchez  F ARS 11300000 
    17   Jamie Vardy  F LEI 11200000 
    18   Theo Walcott  F ARS 10700000 
    19  Olivier Giroud  F ARS 10700000 
    20  Wilfried Bony  F MCI 10000000 
    21 Kristoffer Nordfeldt  G SWA 7000000 
    22    Joe Hart  G MCI 6800000 
    23   Jack Rose  G WBA 6600000 
    24  Asmir Begovic  G CHE 6600000 
    25   Mesut Özil  M ARS 15600000 
    26   Riyad Mahrez  M LEI 15200000 
    27   Ross Barkley  M EVE 13300000 
    28  Dimitri Payet  M WHM 12800000 
    29    Willian  M CHE 12500000 
    30  Bertrand Traore  M CHE 12500000 
    31  Kevin De Bruyne  M MCI 12400000 

И ограничения заключаются в следующем:

1) Общая зарплата каждого 11 игроков очереди не может превышать 100000000

2) Там может только быть максимум четырьмя игроками из одной команды. Например. четыре игрока из «CHE» («Челси»).

3) Существует ограничение на количество игроков в каждой линейке из 11 игроков из каждой позиции. Там может быть:

1 G (вратарь), от 3 до 4 D (защитник), от 3 до 5 М (полузащитник), от 1 до 3 F (вперед)

я хотел каждую комбинацию 11 игрока, который соответствует вышеуказанным противопоказаниям, которые должны быть возвращены. Заказ не важен (например, 1,2,3 считается таким же, как 2,1,3, и его нельзя дублировать), и игрок может появиться в нескольких списках.

Я провел немало исследований и поиграл, но, похоже, с этим не может быть. Я новичок в Р. Я не ожидаю, что кто-нибудь приглушит это для меня, но если кто-то может указать новичку, как я, в правильном направлении, это будет очень признательно.

Спасибо.

Answer 1

грубой силы способ решения этой, (который также прекрасно параллелизуемое и гарантирует все возможные комбинации) является выкапывать разрешить все 11-игровые перестановки и затем отфильтровывать комбинации, которые не соответствуют вашим лимитам, поэтапно.

Чтобы сделать такую ​​программу подходящей в памяти вашего компьютера, дайте каждому игроку уникальный идентификатор целого числа и создайте векторы идентификаторов в качестве наборов команд. Когда вы затем реализуете свои фильтры, ваши функции могут ссылаться на информацию игрока по этому идентификатору в едином фреймворке данных.

Скажите df - это ваш кадр данных со всеми данными игрока.

df$id <- 1:nrow(df) 

Получить все комбинации идентификаторов:

# This will take a long time or run out of memory! 
# In my 2.8Gz laptop took 466 seconds just for your 31 players 
teams <- combn(df$id, 11) 

Конечно, если ваш dataframe большой (как и сотни игроков) эта реализация может занять невероятно много времени, чтобы закончить. Вероятно, вам было бы лучше просто отбирать 11 наборов из набора игроков без замены и строить команды по принципу «по требованию».

Более разумный способ состоит в том, чтобы разбить ваш набор данных в соответствии с положением игрока на один - для вратарей, один для защиты и т. Д. Затем используйте вышеупомянутый подход для создания перестановок разных игроков из каждой позиции и объединения конечных результатов. Это займет нелепо меньше времени, оно все равно будет параллелизуемо и исчерпывающим (дайте вам все возможные комбинации).

Answer 2

Это можно решить как программу линейного целого с использованием библиотеки LPSolve. Такие проблемы очень хорошо разрешимы - против того, что было написано ранее, - так как типичное число решений намного меньше, чем размер домена.

Вы можете добавить для каждого игрока нулевую переменную, независимо от того, находится ли этот игрок в команде.

Пакет может быть установлен с помощью

install.packages("lpSolve") 
install.packages("lpSolveAPI") 

документации можно найти по адресу: https://cran.r-project.org/web/packages/lpSolve/lpSolve.pdf

Первого ограничения суммы игроки 11

Зарплаты в основном сумма всех игроков переменных умноженным по столбцу зарплаты и т. д.

Чтобы получить правильные решения, необходимо указать в

lp.solve(all.bin=TRUE 

Такое, что все переменные, относящиеся к игрокам, равны нулю или одному.

(я понял, что вы пытаетесь узнать, поэтому я воздержусь от предоставления полного решения)

EDIT Как я получил вниз проголосовали, вероятно, из-за не дает полного решения.Вид грустный и как оригинальный автор явно писал, что он не ожидает, что полное решение

library(lpSolve) 

df <- read.csv("/tmp/football.csv",header = TRUE,sep=";") 

f.obj <- rep(1,nrow(df)) 

f.con <- 
    matrix(c(f.obj <- rep(1,nrow(df)), 
    as.vector(df$Salary), 
    (df$Positon=="G") *1.0, 
    (df$Positon=="D") *1.0, 
    (df$Positon=="D") *1.0, 
    (df$Positon=="M") *1.0, 
    (df$Positon=="M") *1.0, 
    (df$Positon=="F") *1.0, 
    (df$Positon=="F") *1.0),nrow=9,byrow= TRUE) 

f.dir <- c("==", "<=","==",">=","<=",">=","<=",">=","<=") 

f.rhs<- c(11, #number players 
     100000000, #salary 
     1 , #Goalkeeper 
     3 , # def min 
     4 , # def max 
     3 , # mdef min 
     5, # mdef max 
     1, # for, min 
     3 # wor, max 
     ) 



solutions <- lp ("max", f.obj, f.con, f.dir, f.rhs,all.bin=TRUE) 

Я не добавить в сборную команду Constraint, как это не дало бы никаких дополнительно идеи здесь ....

** EDIT2 ** Это может пригодиться, если вы измените набор данных R lpsolve binary find all possible solutions