python - 对字典数组进行排序以使不同组的成员相邻

Question

如何从对象数组中创建尽可能多的随机用户对，使成对的用户来自不同的团队。

users = [
{"name" : "mike", "team" : "sales"},
{"name" : "sara", "team" : "sales"},
{"name" : "tom", "team" : "sales"},
{"name" : "piku", "team" : "admin"},
{"name" : "cante", "team" : "engg"},
{"name": "jeff", "team": "engg"},
{"name": "roy", "team": "marketing"},
{"name": "lee", "team": "dev"},
{"name": "anil", "team": "dev"},
{"name": "james", "team": "dev"}
]

result = [("mike", "lee"), ("sara", "anil"), ("tom", "james"), ("piku", "cante"), ("jeff", "roy")]

我已经尝试使用以下代码，假设用户数组已经排序，这样相邻的用户就不会来自同一个团队。问题是如何对输入数组进行排序，使不同团队的用户相邻，从而形成最大可能的对。

   def getRandomPair(users):
      #users = sorted(users, key=lambda i: i['team'])
      result, pair = [], []
      for user in users:
          pair.append(user["name"])
          if len(pair) == 2:
              result.append(pair)
              pair = []
      return result

Answer 1

让 v 成为你的一组。给定 s:v->{int,S} 一个函数，它根据 v 返回在 v 和 中找到的最大有效对数>S 找到的实际对的数组

然后你可以像这样实现

def s(v):
    g_best = {'size':0, 'S':[[]]}
    for every valid pair as p in v:
        v_recurse = v.copy().without(p)
        result = s(v_recurse)
        best = 1 + result['size']
        if best > g_best['size']:
            g_best = {
                'size':1+g_best['size']
                'S': [p] + g_best['S']
            }
        end
    end
    return g_best

这给出了一些类似的东西

users = [
    {"name" : "mike", "team" : "sales"},
    {"name" : "sara", "team" : "sales"},
    {"name" : "tom", "team" : "sales"},
    {"name" : "piku", "team" : "admin"},
    {"name" : "cante", "team" : "engg"},
    {"name": "jeff", "team": "engg"},
    {"name": "roy", "team": "marketing"},
    {"name": "lee", "team": "dev"},
    {"name": "anil", "team": "dev"},
    {"name": "james", "team": "dev"}
]
def s(v):
    valid_pairs = []
    for ai in range(0, len(v)):
        for bi in range(ai+1, len(v)):
            [a,b] = [v[ai], v[bi]]
            if a == b or a['team'] == b['team']:
                break
            valid_pairs.append([a,b])
    g_best = {'size':0, 'S':[[]]}
    for p in valid_pairs:

        v_recurse = list(filter(lambda guy: guy not in p, v))
        result = s(v_recurse)
        cur_size = 1 + result['size']
        if cur_size > g_best['size']:
            g_best = {
                'size':1+result['size'],
                'S': [p] + result['S']
            }
    return g_best
print('result', s(users)['S'])
#result [[{'name': 'tom', 'team': 'sales'}, {'name': 'piku', 'team': 'admin'}], [{'name': 'sara', 'team': 'sales'}, {'name': 'cante', 'team': 'engg'}], [{'name': 'mike', 'team': 'sales'}, {'name': 'lee', 'team': 'dev'}], [{'name': 'jeff', 'team': 'engg'}, {'name': 'anil', 'team': 'dev'}], [{'name': 'roy', 'team': 'marketing'}, {'name': 'james', 'team': 'dev'}], []]

请注意，您可以通过内存或采用动态规划方法来优化此算法，但我猜这是题外话？