Ruby实现：如何将大于8的用户数划分为每组3/4/5人的多组

核心思路 #

由于3、4、5是连续的三个整数，对于任何n>8的整数，都可以拆分为若干个3、4、5的和，且至少包含2个小组。我们可以通过n除以3的余数快速推导分组方案：以3为基础数，用4（补余数1）或5（补余数2）调整，同时支持多种合法组合。

分情况推导 #

1. 当n是3的倍数（n=3k，k≥3，即n≥9）

• 基础方案：直接拆分为k个3人组，比如9→[3,3,3]，12→[3,3,3,3]
• 可选方案：
  • 若k≥3，可将其中3个3替换为4+5（总和不变：3×3=9=4+5），比如9→[4,5]，12→[3,4,5]
  • 若n是5的倍数，可直接拆分为全5人组，比如15→[5,5,5]

2. 当n除以3余1（n=3k+1，k≥3，即n≥10）

• 方案1：用1个4替换1个3（4=3+1），得到(k-1)个3 + 1个4，比如10→[3,3,4]，13→[3,3,3,4]
• 方案2：用2个5替换3个3（5+5=10=3×3+1），得到(k-3)个3 + 2个5，比如10→[5,5]，13→[5,5,3]

3. 当n除以3余2（n=3k+2，k≥3，即n≥11）

• 方案1：用1个5替换1个3（5=3+2），得到(k-1)个3 + 1个5，比如11→[3,3,5]，14→[3,3,3,5]
• 方案2：用2个4替换2个3（4+4=8=3×2+2），得到(k-2)个3 + 2个4，比如11→[3,4,4]，14→[3,3,4,4]
• 可选方案：优先用5人组，剩余部分补4或3，比如14→[5,5,4]

代码实现（Python） #

def generate_groups(n):
    if n <= 8:
        return None  # 不符合题目要求的用户数
    
    groups_list = []
    remainder = n % 3
    k = n // 3

    # 处理余数0的情况
    if remainder == 0:
        # 基础方案：全3
        full_3 = [3] * k
        groups_list.append(full_3)
        # 替换3个3为4+5（至少3个3时）
        if k >= 3:
            alt1 = full_3[:-3] + [4, 5]
            groups_list.append(alt1)
        # 全5方案（n是5的倍数时）
        if n % 5 == 0:
            full_5 = [5] * (n // 5)
            groups_list.append(full_5)
    
    # 处理余数1的情况
    elif remainder == 1:
        # 方案1：(k-1)个3 + 4
        plan1 = [3] * (k - 1) + [4]
        groups_list.append(plan1)
        # 方案2：(k-3)个3 + 5+5（k>=3即n>=10）
        if k >= 3:
            plan2 = [3] * (k - 3) + [5, 5]
            groups_list.append(plan2)
    
    # 处理余数2的情况
    else:
        # 方案1：(k-1)个3 +5
        plan1 = [3] * (k - 1) + [5]
        groups_list.append(plan1)
        # 方案2：(k-2)个3 +4+4（k>=3即n>=11）
        if k >= 3:
            plan2 = [3] * (k - 2) + [4, 4]
            groups_list.append(plan2)
        # 优先用5的方案
        temp = n
        plan3 = []
        while temp >= 5:
            plan3.append(5)
            temp -= 5
        if temp in (3,4):
            plan3.append(temp)
        if len(plan3) >=2 and sum(plan3) ==n:
            groups_list.append(plan3)
    
    # 去重（避免重复方案）
    unique_groups = []
    seen = set()
    for g in groups_list:
        sorted_g = tuple(sorted(g))
        if sorted_g not in seen:
            seen.add(sorted_g)
            unique_groups.append(list(sorted_g))
    return unique_groups

示例验证 #

• 输入9：返回[[3,3,3], [4,5]]，符合要求
• 输入10：返回[[3,3,4], [5,5]]，匹配示例
• 输入14：返回[[3,3,3,5], [3,3,4,4], [4,5,5]]，覆盖示例中的两种组合

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