红包分配算法

红包分配算法：n元分配为m个（下面将n元转换为n分，方便算法实现）

1. m个红包的金额之和恰好等于n分钱
2. 每个红包至少有1分钱

普通随机

余量扣除：逐个红包分配，每个红包从区间 $(0, 剩余金额]$ 取随机数，最后一个红包取剩余金额即可

第k个红包的数学期望是 $\frac{n}{2^{k}}$ ，大概率呈现长尾状分配，前面分配得多，而后面分配得少

package algorithm

import (
  "math/rand"
)

// SplitRedPacket 普通随机-余量扣除
func SplitRedPacket(n int, m int) []int {
  ans := make([]int, m)
  // 保证每个红包至少有1分
  for i := 0; i < m; i++ {
    n--
    ans[i]++
  }
  // 每个红包加上区间[0, 剩余金额]内获取的随机数
  for i := 0; i < m-1; i++ {
    v := rand.Intn(n + 1)
    ans[i] += v
    n -= v
  }
  ans[m-1] += n
  return ans
}

均匀随机

二倍均值：逐个红包分配，每个红包从区间 $(0, 2 \times \frac{剩余金额}{剩余个数})$ 取随机数，使每个红包的数学期望相同均为 $\frac{n}{m}$

可理解为对n元红包做了m等分，随即范围设置上限为剩余均值的二倍，使每个红包的数学期望为原始均值

假设100元分为10个

1. 分配第1个时，剩余金额为100元，剩余个数为10，从区间 $(0, 2 \times \frac{100}{10})$ 取随机数，数学期望为10元
2. 分配第2个时，剩余金额为90元，剩余个数为9，从区间 $(0, 2 \times \frac{100}{10})$ 取随机数，数学期望为10元
3. 以此类推，每个红包的数学期望相等

package algorithm

import (
  "math/rand"
)

// SplitRedPacket 均匀随机-二倍均值
func SplitRedPacket(n int, m int) []int {
  ans := make([]int, m)
  // 保证每个红包至少有1分
  for i := 0; i < m; i++ {
    n--
    ans[i]++
  }
  // 每个红包加上区间[0, 二倍均值]内获取的随机数
  for i := 0; i < m-1; i++ {
    v := rand.Intn(2*n/(m-i) + 1)
    ans[i] += v
    n -= v
  }
  ans[m-1] += n
  return ans
}

完全随机

线段切割：将红包分配问题转换为如何将长为n的线段切割为m段的问题

基于蓄水池抽样算法选取不重复的线段点

基于蓄水池抽样算法：遍历线段点，等概率地选取不重复的线段点，以保证线段长度非零

package algorithm

import (
  "math/rand"
  "sort"
)

// SplitRedPacket 完全随机-线段切割1：基于蓄水池抽样，随机选取不重复的m-1个线段点
func SplitRedPacket(n int, m int) []int {
  // 快速路径
  switch m {
  case 1:
    return []int{n}
  case 2:
    x := 1 + rand.Intn(n-1) // x = [1, n-1]
    return []int{x, n - x}
  }

  // 设红包由n个线段和n+1个点(点的编号为[0, n])组成

  // 蓄水池抽样样本集，随机选取m-1个不重复的线段点
  points := make([]int, m-1)

  // 忽略最左端点0和最右端点n, 从1遍历至n-1
  for point := 1; point < n; point++ {
    // i - 在数据流中的索引号
    // point - 具体数据
    i := point - 1

    if i < len(points) {
      points[i] = point
      continue
    }

    ri := rand.Intn(i + 1)
    if ri < len(points) {
      points[ri] = point
      continue
    }
  }

  // 随机选取了m-1个点，对随机选取的点按位置顺序排序
  sort.Ints(points)

  // 计算m个线段长度
  ans := make([]int, m)
  ans[0] = points[0]
  for i := 1; i < m-1; i++ {
    ans[i] = points[i] - points[i-1]
  }
  ans[m-1] = n - points[m-2]
  return ans
}

基于set随机选取不重复的线段点

基于set：无需遍历所有线段点，在线段点编号范围内取随机数，使用set保证选取的线段点不重复，点集越小，冲突概率越大，可能导致选取超时

package algorithm

import (
  "maps"
  "math/rand"
  "slices"
)

// SplitRedPacket 完全随机-线段切割2：基于set，随机选取不重复的m-1个线段点
func SplitRedPacket(n int, m int) []int {
  // 快速路径
  switch m {
  case 1:
    return []int{n}
  case 2:
    x := 1 + rand.Intn(n-1) // x = [1, n-1]
    return []int{x, n - x}
  }

  // 设红包由n个线段和n+1个点(点的编号为[0, n])组成

  // 随机选取m-1个不重复的线段点
  mp := make(map[int]struct{}, m-1)
  
  // 忽略最左端点0和最右端点n，取[1, n-1]
  for len(mp) < m-1 {
    mp[1+rand.Intn(n-1)] = struct{}{}
  }

  // 随机选取了m-1个点，对随机选取的点按位置顺序排序
  points := slices.Sorted(maps.Keys(mp))

  // 计算m个线段长度
  ans := make([]int, m)
  ans[0] = points[0]
  for i := 1; i < m-1; i++ {
    ans[i] = points[i] - points[i-1]
  }
  ans[m-1] = n - points[m-2]
  return ans
}

下限预分配，随机选取可重复的线段点

无需遍历所有点，无需set，每个红包分配下限后，允许线段长度为0，从而允许随机选取的线段点重复

package algorithm

import (
  "math/rand"
  "sort"
)

// SplitRedPacket 完全随机-线段切割3：每个红包先分配下限，随机选取可重复的m-1个线段点
func SplitRedPacket(n int, m int) []int {
  // 快速路径
  switch m {
  case 1:
    return []int{n}
  case 2:
    x := 1 + rand.Intn(n-1) // x = [1, n-1]
    return []int{x, n - x}
  }

  // 设红包由n个线段和n+1个点(点的编号为[0, n])组成

  // 每个红包先分配下限
  ans := make([]int, m)
  for i := 0; i < m; i++ {
    n--
    ans[i]++
  }

  // 随机选取m-1个可重复的线段点
  points := make([]int, m-1)

  for i := 0; i < m-1; i++ {
    points[i] = rand.Intn(n + 1)
  }

  // 随机选取了m-1个点，对随机选取的点按位置顺序排序
  sort.Ints(points)

  // 计算m个线段长度
  ans[0] += points[0]
  for i := 1; i < m-1; i++ {
    ans[i] += points[i] - points[i-1]
  }
  ans[m-1] += n - points[m-2]
  return ans
}

单位线段随机分配到各红包

随机分配所有单位线段，算法实现较简单且能够适配带上下限场景

package algorithm

import (
  "math/rand"
)

// SplitRedPacket 完全随机-线段切割4：随机分配所有单位线段到每个红包
func SplitRedPacket(n int, m int) []int {
  ans := make([]int, m)
  // 保证每个红包至少有1分
  for i := 0; i < m; i++ {
    n--
    ans[i]++
  }
  // 对每个单位线段作随机分配
  for n > 0 {
    ans[rand.Intn(m)]++
    n--
  }
  return ans
}

具上下限随机

每个红包下限从1分提升为1元，上限设置为红包总额的30%

1. 平均值动态修正随机（见带上下限的红包算法实践总结 - hduhans - 博客园）
2. 单位线段随机分配
   1. 先对所有红包分配下限
   2. 再随机分配单位线段到各红包，当某个红包达到上限则移除分配逻辑（swap到数组末尾）
   3. 最后使用洗牌算法打乱数组