如何在总时长内随机排布子时长段？C#实现需求咨询

需求：总时长400秒，需将5秒、90秒、20秒、40秒等子时长段尽可能随机地排布其中。现有代码随机性不足，以下提供两种更优的实现思路及伪代码：

现有代码（C#） #

long DurationOccupiedIfArrangedFromLeftWithoutAnyGap = liIntervalsAllocated.Sum();

long startNo = DurationOccupiedIfArrangedFromLeftWithoutAnyGap;
long endNo = TimeInSeconds - liIntervalsAllocated[liIntervalsAllocated.Count - 1];


while (liIntervalsAllocated.Count > 0)
{
      long positionToPlace = CommonFn.GetRandomNumberBetweenTwo((int) startNo, (int) endNo);
      Debug.WriteLine("start No is " + startNo + " End no is " + endNo + " for element selected is " + liIntervalsAllocated[liIntervalsAllocated.Count - 1] + " . ELement is placed at " + positionToPlace);
      
      startNo = startNo - liIntervalsAllocated[liIntervalsAllocated.Count - 1];
      if (liIntervalsAllocated.Count == 1)
      {
          endNo = positionToPlace;
      }
      else
      {
          endNo = positionToPlace - liIntervalsAllocated[liIntervalsAllocated.Count - 2];
      }

      liIntervalsAllocated.RemoveAt(liIntervalsAllocated.Count - 1);
}

优化思路1：间隙分配法（高效且随机性均匀） #

核心逻辑：先计算所有子段的总占用时长，得出剩余可分配的总间隙，将总间隙拆分成「子段数量+1」个随机值（分别对应子段前、子段间、子段后的间隙），再按顺序累加间隙和子段得到每个子段的起始位置。

伪代码实现 #

// 定义子段列表和总时长
var segments = new List<long> { 5, 90, 20, 40 };
long totalDuration = 400;
long totalOccupied = segments.Sum();
long totalGap = totalDuration - totalOccupied;
int gapCount = segments.Count + 1; // 间隙数量 = 子段数 + 1

// 生成总和为totalGap的随机间隙列表
var gaps = GenerateRandomGaps(totalGap, gapCount);

// 计算每个子段的起始位置
long currentPos = 0;
var segmentPositions = new List<(long Start, long Duration)>();
for (int i = 0; i < segments.Count; i++)
{
    currentPos += gaps[i];
    segmentPositions.Add((currentPos, segments[i]));
    currentPos += segments[i];
}

// 辅助方法：生成指定数量、总和固定的非负随机数
List<long> GenerateRandomGaps(long total, int count)
{
    var gaps = new List<long>();
    long remaining = total;
    Random rng = new Random();
    
    for (int i = 0; i < count - 1; i++)
    {
        // 每次随机取0到剩余间隙之间的值
        long gap = rng.NextInt64(0, remaining + 1);
        gaps.Add(gap);
        remaining -= gap;
    }
    gaps.Add(remaining); // 最后一个间隙取剩余值，保证总和正确
    return gaps;
}

优化思路2：随机插入法（直观，适合少量子段） #

核心逻辑：先打乱子段顺序，然后逐个随机选择起始位置，检查是否与已放置的子段重叠，不重叠则完成放置。

伪代码实现 #

var segments = new List<long> { 5, 90, 20, 40 };
long totalDuration = 400;
Random rng = new Random();
var placedSegments = new List<(long Start, long Duration)>();

// 先打乱子段顺序，避免固定顺序影响随机性
foreach (var seg in segments.OrderBy(_ => rng.Next()))
{
    bool isPlaced = false;
    while (!isPlaced)
    {
        long maxStart = totalDuration - seg;
        if (maxStart < 0) throw new InvalidOperationException("总时长不足以容纳所有子段");
        
        // 随机生成起始位置
        long start = rng.NextInt64(0, maxStart + 1);
        long end = start + seg;
        
        // 检查是否与已放置的子段重叠
        bool hasOverlap = placedSegments.Any(p => !(end <= p.Start || start >= p.Start + p.Duration));
        if (!hasOverlap)
        {
            placedSegments.Add((start, seg));
            isPlaced = true;
        }
    }
}

// 可选：按起始位置排序，方便后续处理
placedSegments = placedSegments.OrderBy(p => p.Start).ToList();

两种思路对比 #

• 间隙分配法：无需检查重叠，计算效率高，随机性均匀，适合大多数场景，尤其是子段数量较多的情况。
• 随机插入法：逻辑直观易懂，但子段多、剩余间隙较小时可能会多次重试，适合子段数量少的场景。

原代码的问题在于从右往左放置时，起始和结束范围的限制导致子段容易集中分布，随机性不足，上述两种方法可有效解决该问题。

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