如何在均衡分布变量值的同时获取差异最大的组合？

核心目标 #

要让函数同时满足两个要求：

1. 变量取值均衡：每个变量的每个取值在最终组合中出现的次数尽可能接近（比如总需求n=11、每个变量有6个取值时，5个取值出现2次，1个取值出现1次）
2. 组合间差异最大化：优先选择与已选组合汉明距离最大的候选（汉明距离指两个组合中不同值的维度数，比如[0,0,0]和[1,2,3]的汉明距离为3，是该场景下的最大值）

具体修正步骤 #

1. 预生成全量候选组合 #

先通过笛卡尔积生成所有可能的变量组合，作为候选池。

2. 维护取值计数 #

为每个变量的每个取值维护计数，确保后续选择优先补足计数偏少的取值。

3. 贪心迭代选择逻辑 #

• 首次选择：任选一个基准组合（或随机选择），更新对应取值的计数。
• 后续每一步：
  • 从候选池中筛选能优化取值均衡性的候选（优先选包含当前计数最少的取值的组合）
  • 在筛选出的候选中，计算每个组合与所有已选组合的最小汉明距离（保证新组合和所有已选组合的差异都足够大）
  • 选择最小汉明距离最大的组合加入结果集，更新计数并从候选池中移除该组合

修正后的代码实现 #

import itertools
import pandas as pd

def get_distanced_creatives(variables, n):
    # variables为字典：键是变量名，值是变量的取值列表
    var_names = list(variables.keys())
    var_value_lists = [variables[name] for name in var_names]
    
    # 生成所有候选组合并转为DataFrame
    all_combinations = list(itertools.product(*var_value_lists))
    candidate_df = pd.DataFrame(all_combinations, columns=var_names)
    
    # 初始化每个变量取值的计数字典
    count_dict = {name: {val: 0 for val in variables[name]} for name in var_names}
    result = []
    
    for _ in range(n):
        if candidate_df.empty:
            break
        
        # 计算每个候选的均衡得分：包含计数越少的取值，得分越高
        def calc_balance_score(row):
            score = 0
            for name in var_names:
                val = row[name]
                score += len(variables[name]) - count_dict[name][val]
            return score
        
        candidate_df['balance_score'] = candidate_df.apply(calc_balance_score, axis=1)
        # 筛选均衡得分最高的候选子集
        top_balance_candidates = candidate_df[candidate_df['balance_score'] == candidate_df['balance_score'].max()]
        
        # 计算候选与已选组合的最小汉明距离
        def calc_min_hamming(row):
            current_comb = row[var_names].tolist()
            if not result:
                return len(var_names)  # 第一个组合默认最大距离
            min_dist = min(
                sum(a != b for a, b in zip(current_comb, selected))
                for selected in result
            )
            return min_dist
        
        top_balance_candidates['min_hamming'] = top_balance_candidates.apply(calc_min_hamming, axis=1)
        # 选择最小汉明距离最大的组合
        selected_row = top_balance_candidates[top_balance_candidates['min_hamming'] == top_balance_candidates['min_hamming'].max()].iloc[0]
        
        # 更新结果与计数
        selected_comb = selected_row[var_names].tolist()
        result.append(selected_comb)
        for name in var_names:
            count_dict[name][selected_row[name]] += 1
        
        # 从候选池移除已选组合
        candidate_df = candidate_df.drop(selected_row.name)
    
    return pd.DataFrame(result, columns=var_names)

# 测试示例
test_vars = {
    'cat0': [0,1,2,3,4,5],
    'cat1': [0,1,2,3,4,5],
    'cat2': [0,1,2,3,4,5]
}
# 测试n=6的情况
print("n=6的结果：")
print(get_distanced_creatives(test_vars, 6))
# 测试n=11的情况
print("\nn=11的结果：")
print(get_distanced_creatives(test_vars, 11))

优化说明 #

• 均衡得分机制：确保每次选择都优先填补计数不足的取值，避免单个取值出现次数偏差过大。
• 最小汉明距离筛选：保证新组合与所有已选组合的差异都处于较高水平，避免生成相似组合。
• 贪心迭代：通过每一步的局部最优选择，最终逼近全局最优的「均衡+最大差异」组合集合。

内容的提问来源于stack exchange，提问作者ASIER RODRIGUEZ GONZALEZ