Python-Pandas自连接为合并笛卡尔积生成所有组合和和

Question

我对Python是全新的，似乎它有很多灵活性，比传统的RDBMS系统更快。在

在一个非常简单的过程中创建随机幻想团队。我来自RDBMS背景（oraclesql），对于这种数据处理来说，这似乎不是最佳选择。在

我用pandas从csv文件中读取数据帧，现在有了一个包含两列的简单数据框：Player、Salary：

`                    Name  Salary
0              Jason Day   11700
1         Dustin Johnson   11600
2           Rory McIlroy   11400
3          Jordan Spieth   11100
4         Henrik Stenson   10500
5         Phil Mickelson   10200
6            Justin Rose    9800
7             Adam Scott    9600
8          Sergio Garcia    9400
9          Rickie Fowler    9200`

我想通过python（pandas）来制作6个玩家的所有组合，他们的薪水在45000-50000之间。在

在查找python选项时，我发现itertools的组合很有趣，但它会生成一个庞大的组合列表，而不会过滤工资总额。在

在传统的SQL中，我会执行一个大规模的合并笛卡尔连接w/SUM，但是我会让玩家在不同的位置。。在

比如A，B，C然后，C，B，A。。在

我的传统SQL不能很好地工作，如下所示：

^{pr2}$

在Pandas/Python中有没有一种方法可以做到这一点？在

任何可以指出的文档都是很棒的！在

Answer 1

我对6个组合进行了测试，结果没有一个团队满意。我用了5个。在

这会让你达到目的：

from itertools import combinations
import pandas as pd


s = df.set_index('Name').squeeze()
combos = pd.DataFrame([c for c in combinations(s.index, 5)])
combo_salary = combos.apply(lambda x: s.ix[x].sum(), axis=1)
combos[(combo_salary >= 45000) & (combo_salary <= 50000)]

Answer 2

这是一个使用简单算法的非Pandas解决方案。它从按薪水排序的玩家列表递归地生成组合。这使得它可以跳过生成超过薪资上限的组合。在

正如piRSquared提到的，没有6人的团队在问题中提到的薪水限制之内，所以我选择了限制来产生一小部分团队。在

#!/usr/bin/env python3

''' Limited combinations

    Generate combinations of players whose combined salaries fall within given limits

    See http://stackoverflow.com/q/38636460/4014959

    Written by PM 2Ring 2016.07.28
'''

data = '''\
0              Jason Day   11700
1         Dustin Johnson   11600
2           Rory McIlroy   11400
3          Jordan Spieth   11100
4         Henrik Stenson   10500
5         Phil Mickelson   10200
6            Justin Rose    9800
7             Adam Scott    9600
8          Sergio Garcia    9400
9          Rickie Fowler    9200
'''

data = [s.split() for s in data.splitlines()]
all_players = [(' '.join(u[1:-1]), int(u[-1])) for u in data]
all_players.sort(key=lambda t: t[1])
for i, row in enumerate(all_players):
    print(i, row)
print('- '*40)

def choose_teams(free, num, team=(), value=0):
    num -= 1
    for i, p in enumerate(free):
        salary = all_players[p][1]
        newvalue = value + salary
        if newvalue <= hi:
            newteam = team + (p,)
            if num == 0:
                if newvalue >= lo:
                    yield newteam, newvalue
            else:
                yield from choose_teams(free[i+1:], num, newteam, newvalue)
        else:
            break

#Salary limits
lo, hi = 55000, 60500

#Indices of players that can be chosen for a team 
free = tuple(range(len(all_players)))

for i, (t, s) in enumerate(choose_teams(free, 6), 1):
    team = [all_players[p] for p in t]
    names, sals = zip(*team)
    assert sum(sals) == s
    print(i, t, names, s)

输出

^{pr2}$

---

如果使用的Python旧版本不支持yield from语法，则可以替换它

yield from choose_teams(free[i+1:], num, newteam, newvalue)

与

for t, v in choose_teams(free[i+1:], num, newteam, newvalue):
    yield t, v

Answer 3

正如评论中提到的，这是一个约束满足问题。它有一个组合部分，但由于您没有定义最小化或最大化的目标，所以它不是一个优化问题（还没有）。你可以用很多方法来解决这个问题：你可以尝试像piRSquared这样的暴力，或者使用像pm2ring这样的启发式算法。我将提出一个0-1线性规划的解决方案，并使用PuLP库来建模和解决问题。在

from pulp import *
import pandas as pd
df = df.set_index('Name')
feasible_solutions = []

为了对问题建模，首先需要定义决策变量。这里，决策变量将是每个玩家的指示变量：如果选择了该玩家，则为1，否则为0。下面是如何在纸浆中做到这一点：

^{pr2}$

接下来，您将创建一个问题：

prob = pulp.LpProblem('Team Selection', pulp.LpMinimize)

正如我前面提到的，你的问题没有说明任何目标。你只想创建所有可能的团队。因此，我们将定义一个任意目标函数（我将再次回到这个任意函数）。在

prob += 0

主要有两个约束：

1）球队将有5名球员：

prob += lpSum([players[player] for player in players]) == 5

记住，玩家字典存储我们的决策变量。players[player]为1（如果该玩家在团队中）或0（否则）。因此，如果你把它们加起来，结果应该等于5。在

2）工资总额应在45k到50k之间

prob += lpSum([players[player] * df.at[player, 'Salary'] 
                                        for player in players]) <= 50000
prob += lpSum([players[player] * df.at[player, 'Salary'] 
                                        for player in players]) >= 45000

这与第一个约束类似。在这里，我们不计算工资，而是将工资相加（当球员在队中时，该值将为1，因此将乘以相应的工资。否则，值将为零，乘法也将为零）。在

主要建模在这里完成。如果您调用prob.solve()，它将找到满足这些约束的解决方案。通常，在优化问题中，我们提供一个目标函数，并试图使其最大化或最小化。例如，假设你有玩家技能的分数。你的预算是有限的，你不能继续选择前5名球员。因此，在我们所说的prob += 0的部分中，您可以定义一个目标函数来最大化总技能分数。但那不是你想要的，所以我们继续吧。在

找到解决方案后，可以向问题添加另一个约束，声明下一个解决方案应该与此不同，您可以生成所有解决方案。在

while prob.solve() == 1:
    current_solution = [player for player in players if value(players[player])]
    feasible_solutions.append(current_solution)
    prob += lpSum([players[player] for player in current_solution]) <= 4

prob.solve()是解决问题的方法。基于结果，它返回一个整数。如果找到一个最优解，结果是1。对于不可行或无限解，有不同的代码。所以只要我们能找到新的解决方案，我们就继续循环。在

在循环中，我们首先将当前解决方案附加到feasible_solutions列表中。然后，我们添加另一个约束：对于这5个玩家，变量之和不能超过4（最大值5，如果是5，我们知道这是相同的解）。在

如果你运行这个，你会得到和piRSquared相同的结果。在

那么，这有什么好处呢？在

我们使用整数/二进制线性规划的主要原因是组合的数量增长非常快。这叫做combinatorial explosion。看看可能的团队数量（没有任何限制）：

from scipy.misc import comb
comb(10, 5)
Out: 252.0

comb(20, 5)
Out: 15504.0

comb(50, 5)
Out: 2118760.0

comb(100, 5)
Out: 75287520.0

几乎不可能评估所有的组合。在

当然，当你想列出满足这些约束的所有组合时，你仍然在冒这个风险。如果满足约束条件的组合数量很大，则需要花费大量时间进行计算。你无法避免。但是，如果这个子集很小或者仍然很大，但是你正在计算这个集合上的一个函数，它会更好。在

例如，考虑以下数据帧：

import numpy as np
np.random.seed(0)
df = pd.DataFrame({'Name': ['player' + str(i).zfill(3) for i in range(100)],
                   'Salary': np.random.randint(0, 9600, 100)})

75287520个解决方案中有268个满足薪资限制。在我的电脑里花了44秒才把它们列出来。用暴力手段找到他们需要几个小时（更新：It需要8小时21分钟）。在

默认情况下，PuLP使用开源解算器Cbc。还有其他开源/商业替代解决方案可以与PuLP一起使用。商业化的通常比预期的更快（尽管它们非常昂贵）。在

另一种选择是我在评论中提到的约束编程。对于这类问题，您可以找到许多聪明的方法，通过约束编程来减少搜索空间。我对整数编程很满意，所以我展示了一个基于此的模型，但是我应该注意到约束编程可能会更好。在