算法：在用户定义的区间内随机选择点，这些点之间的间隔为用户定义的最小值。

Question

我需要开发一种算法，它可以在用户指定的区间内随机选择值。此外，这些值需要由用户定义的最小距离分隔。在我的情况下，这些值和区间是时间，但这对于开发通用算法可能并不重要。

例如：用户可能定义了三个时间间隔（0900-1200、1200-1500；1500-1800），并要在这些间隔中选择3个值（每个间隔1个）。用户还可以说他们希望这些值至少相隔30分钟。因此，值不能是1159、1201、1530，因为前两个元素只相隔2分钟。

将奖励几百个点（我能给多少就多少）给最有效的算法。答案可以是与语言无关的，但偏爱使用伪代码或JavaScript来回答。

注：

- 区间的数量和长度完全由用户确定。 - 两个随机选择的点之间的距离也完全由用户确定（但必须小于下一个区间的长度）。 - 用户定义的区间不会重叠。 - 可能存在用户定义的区间之间的间隙（例如0900-1200、1500-1800、2000-2300）。

我已经有了以下两种算法，并希望找到更高效的算法：

- 在区间＃1中随机选择值。如果此值距离区间＃2的开头小于用户指定的距离，则在随机选择区间＃2的值之前调整区间＃2的开头。对于所有区间重复此过程。 - 从所有区间中随机选择值。循环遍历所选值的数组，并确定它们是否由用户定义的最小距离分隔。如果不是（即值太接近），则随机选择新值。重复，直到有效数组。

- Brigadeiro

---

@Berto99，是的，这些区间不会重叠（我会编辑帖子以反映这一点）。 - Brigadeiro

只是好奇，这样实时生成有什么问题吗？从当前区间生成一个随机值，过滤掉下一个区间的无效值，继续进行？ - Abhinav Mathur

@Brigadeiro请看一下我的答案。 - Alberto Sinigaglia

@Berto99 谢谢你的回答！我会在一两天内回来并评估所有答案，不用担心！ - Brigadeiro

@Wyck 是的，我们正在讨论时间，是的，重叠部分会环绕，因此2359和0001之间相隔2分钟。是的，范围可以跨越午夜。 - Brigadeiro

Answer 1

这对我来说是有效的，目前我无法使其“更加高效”：

function random(intervals, gap = 1){
    if(!intervals.length) return [];

    // ensure the ordering of the groups
    intervals = intervals.sort((a,b) => a[0] - b[0])

    // check for distance, init to a value that can't exist
    let res = []
    for(let i = 0; i < intervals.length; i++){
        let [min, max] = intervals[i]

        // check if can exist a possible number
        if(i < intervals.length - 1 && min + gap > intervals[i+1][1]){
            throw new Error("invalid ranges and gap")
        }
        // if we can't create a number in the current section, try to generate another number from the previous
        if( i > 0 && res[i-1] + gap > max){
            // reset the max value for the previous interval to force the number to be smaller
            intervals[i-1][1] = res[i-1] - 1
            res.pop()
            i-=2
        }
        else {
            // set as min the lower between the min of the interval and the previous number generated + gap
            if( i > 0 ){
                min = Math.max(res[i-1] + gap , min)
            }
            // usual formula to get a random number in a specific interval
            res.push(Math.round(Math.random() * (max - min) + min))
        }
    }
    return res
}

console.log(random([
    [0900, 1200], 
    [1200, 1500],
    [1500, 1800],
], 400))

这是如何工作的：

1. 生成第一个数字()
2. 检查是否可以生成第二个数字(根据间隔规则)
   - 如果可以，生成它并返回到步骤2（但使用第三个数字）
   - 如果不能，则将前一个区间的最大值设置为生成的数字，并让其再次生成（以便生成较低的数字）

我无法确定复杂性，因为涉及到随机数，但在生成第100个随机数时可能会遇到无法生成的情况，所以在最坏的情况下，可能需要从第一个开始重新生成所有内容。

然而，每次回退都会缩小区间范围，因此如果存在解决方案，它将收敛到解决方案。

- Alberto Sinigaglia

Answer 2

这段代码似乎可以胜任。有关说明，请参见代码中的注释...

请注意，此代码不会检查您的条件，即不重叠的间隔和间隔足够大以允许满足mindist。如果条件不满足，则可能会生成错误结果。

该算法允许单独为每个间隔定义两个值之间的最小距离。

还要注意，此算法中的900之类的间隔限制并不表示9:00，而只是900的数值。如果您希望间隔表示时间，则必须将它们表示为自午夜以来的分钟数。例如，9:00将变为540，12:00将变为720，15:00将变为900。

编辑

通过当前编辑，它还支持午夜时分的包装（尽管不支持超过一整天的间隔或最小距离）。

//these are the values entered by the user
    //as intervals are non overlapping I interpret
    //an interval [100, 300, ...] as 100 <= x < 300
    //ie the upper limit is not part of that interval
    
    //the third value in each interval is the minimum
    //distance from the last value, ie [500, 900, 200] 
    //means a value between 500 and 900 and it must be
    //at least 200 away from the last value

    //if the upper limit of an interval is less than the lower limit
    //this means a wrap-around at midnight.

    //the minimin distance in the first interval is obviously 0
    let intervals = [
      [100, 300, 0],
      [500, 900, 200],
      [900, 560, 500]
    ]
    //the total upper limit of an interval (for instance number of minutes in a day)
    //lenght of a day. if you don't need wrap-arounds set to 
    //Number.MAX_SAFE_INTEGER
    let upperlimit = 1440; 

    //generates a random value x with    min <= x < max
    function rand(min, max) {
      return Math.floor(Math.random() * (max - min)) + min;
    }

    //holds all generated values
    let vals = []; 
    let val = 0; 

    //Iterate over all intervals, to generate one value 
    //from each interval
    for (let iv of intervals) {
      //the next random must be greater than the beginning of the interval
      //and if the last value is within range of mindist, also greater than
      //lastval + mindist
      let min = Math.max(val + iv[2], iv[0]);

      //the next random must be less than the end of the interval
      //if the end of the interval is less then current min
      //there is a wrap-around at midnight, thus extend the max
      let max = iv[1] < min ? iv[1] + upperlimit : iv[1];
      
      //generate the next val. if it's greater than upperlimit
      //it's on the next day, thus remove a whole day
      val = rand(min, max);
      if (val > upperlimit) val -= upperlimit;
      
      vals.push(val);
    }

    console.log(vals)

作为您可能已经注意到的，这更或多或少是您提议的第一种实现方式，但我没有看到任何比这更“计算效率高”的方法。您无法避免从每个区间中选择一个值，并且始终生成有效数字的最有效方法是调整区间的下限（如果必要）。

当然，采用这种方法时，下一个数字的选择总是受到前一个数字选择的限制。特别是如果两个数字之间的最小距离接近区间长度，并且先前选择的数字相对于其区间的上限而言较高。

- derpirscher

---

尝试使用以下代码：let intervals = [ [0900, 1200, 0], [1200, 1210, 300], [1500, 1800, 400], ] - Alberto Sinigaglia

@Berto 嗯，这个定义确实违反了 OP 的限制，即间隔始终大于最小距离。间隔 [1200、1210、300] 只有 10 个元素长，但最小距离为 300（“注释”中的第二个符号）。 - derpirscher

没有意义，问题中提到的“最小间隔”是指生成的数字，与区间大小无关。 - Alberto Sinigaglia

例如，您的程序允许解决方案1159、1201、1530，但OP并不希望这样。 - Alberto Sinigaglia

引用OP的话：“在我的情况下，值和间隔是时间，但这对于开发通用算法可能并不重要。”因此，无论您的间隔限制是什么，都只是另一种解释形式。而且，它不处理午夜环绕，因为当我发布这个答案时，这不是问题的一部分...特别是对于通用算法（即自然数而不是时间），定义像[2300, 0200]这样的间隔似乎有点奇怪。 - derpirscher

Answer 3

这可以通过将时间间隔按所需的分钟数分开来简单完成。然而，可能存在一些边缘情况，例如给定的时间间隔比分隔时间短，或者更糟糕的是，两个连续的时间间隔都比分隔时间短，在这种情况下，您可以安全地抛出错误。即在[[900,1200],[1200,1500]]的情况下，1500 - 900 < 30。因此，您最好在尝试任何进一步操作之前检查每个连续元组的情况，并在它们不满足时抛出错误。

然后就会变得有点棘手。我的意思是从概率上讲。一个天真的方法是在[900,1200]中选择一个随机值，并根据结果将30添加到它，然后相应地限制第二个元组的底部边界。假设在[900,1200]中选择的随机数为1190，那么我们将强制第二个随机数在[1220,1500]中选择。这使第二个随机选择取决于第一个选择的结果，就我记得从概率课程中，这样做不好。我相信我们必须找到所有可能的边界，然后在它们之间进行随机选择，然后进行两个安全的随机选择，分别从每个范围内选择。

另一个需要考虑的问题是，这可能是一个很长的元组列表。因此，我们应该注意不要限制每个轮次中第二个元组，因为它将成为下一轮的第一个元组，我们希望它尽可能地宽。因此，也许从第一个范围中获取最小可能值（尽可能限制第一个范围）可能比随机尝试更有成效，因为后续步骤可能会引起问题。我可以给你代码，但由于你还没有展示任何尝试，你必须用这根竿子去钓鱼。

- Redu