带重复约束的大列表跨子群公平分配Python与Bash实现

约束说明 #

基于26个大写英文字母A到Z的集合，分配需满足以下规则：

• 每个「主字母」需匹配5个独立的「工作项字母」
• 每个工作字母在所有分配结果中的总出现次数恰好为5次（整体总分配量为26*5=130次，与单字母总出现5次的总量完全匹配）
• 同一主字母的分配清单中，不得出现重复的工作字母
• 理想规则：不将工作字母分配给与自身完全相同的主字母（如不向A的清单中分配A）

Python实现 #

核心思路：采用贪心策略逐行填充分配结果，每一步优先选择「已累计出现次数最少」的候选工作字母，从机制上保证各字母的出现次数均衡；同时直接在候选池中剔除当前主字母本身，完全规避自分配情况。

import random
from string import ascii_uppercase

# 初始化字母集合
letters = list(ascii_uppercase)
target_items_per_main = 5  # 每个主字母需分配的工作项数量
target_total_occurrence = 5 # 每个工作字母允许的最大出现次数

# 初始化存储结构
alloc = {char: set() for char in letters}
used_count = {char: 0 for char in letters}

# 逐主字母填充分配结果
for main_char in letters:
    # 生成候选池：排除当前主字母本身，优先筛选已用次数少的字母
    candidates = [
        c for c in letters
        if c != main_char
        and used_count[c] < target_total_occurrence
    ]
    candidates.sort(key=lambda x: used_count[x])
    
    # 选够5个工作项即可
    for _ in range(target_items_per_main):
        pick = candidates.pop(0)
        alloc[main_char].add(pick)
        used_count[pick] += 1

# 结果校验（可直接运行检查合规性）
assert len(letters) * target_items_per_main == sum(used_count.values()), "总分配量不匹配"
assert all(v == target_total_occurrence for v in used_count.values()), "单字母总出现次数不达标"
assert all(len(v) == target_items_per_main for v in alloc.values()), "主字母的工作项数量不达标"
assert all(main not in work_set for main, work_set in alloc.items()), "存在主字母自分配的情况"

# 格式化输出
for main_char in letters:
    print(f"{main_char}: {', '.join(sorted(alloc[main_char]))}")

Bash实现 #

适合无Python运行环境的场景，依赖系统自带的文本处理工具与随机打乱命令，实现同等约束下的分配逻辑。

#!/bin/bash
# 初始化26个大写字母集合
letters=({A..Z})
target_items_per_main=5
target_total_occurrence=5

# 初始化存储结构
declare -A alloc
declare -A used_count
for c in "${letters[@]}"; do
    alloc[$c]=""
    used_count[$c]=0
done

# 逐主字母处理分配
for main in "${letters[@]}"; do
    picked=0
    # 生成候选池：排除当前主字母，排除已达出现上限的工作字母
    candidates=()
    for c in "${letters[@]}"; do
        if [[ $c != "$main" ]] && [[ ${used_count[$c]} -lt $target_total_occurrence ]]; then
            candidates+=($c)
        fi
    done
    # 随机打乱候选顺序，避免固定分配结果
    shuffled=($(printf "%s\n" "${candidates[@]}" | shuf))

    for pick in "${shuffled[@]}"; do
        # 凑够5个工作项则停止选入
        if [[ $picked -ge $target_items_per_main ]]; then
            break
        fi
        # 跳过已分配给当前主字母的工作项，避免重复
        if [[ " ${alloc[$main]} " =~ " $pick " ]]; then
            continue
        fi
        # 写入分配结果
        alloc[$main]+="$pick "
        used_count[$pick]=$((used_count[$pick]+1))
        picked=$((picked+1))
    done
done

# 格式化输出结果
for main in "${letters[@]}"; do
    trimmed=$(echo "${alloc[$main]}" | sed 's/ $//' | sed 's/ /, /g')
    echo "$main: $trimmed"
done

内容的提问来源于stack exchange，提问作者User9123