5

我正在尝试生成一个整数数组，其中包含随机数加起来一个特定的值。这是我的代码：

private long[] getRandoms(long size , long sum) throws Exception {
  double iniSum = 0;
  System.out.println("sum = " + sum);
  long[] ret = new long[(int) size];
  for (int i = 0 ; i < ret.length; i++) {
    ret[i] = randomInRange(1, sum);
    iniSum += ret[i];
  }

  double finSum = 0;
  for (int i = 0 ; i < ret.length; i++) {
    ret[i] =  Math.round((sum * ret[i]) / iniSum);
    System.out.println("ret[" + i +"] = " + ret[i]);
    finSum += ret[i];
  }

  if (finSum != sum) throw new Exception("Could not find " + size + " numbers adding up to " + sum  + " . Final sum = " + finSum);
  return ret;
}



private long randomInRange(long min , long max) {
  Random rand = new Random();
  long ret = rand.nextInt((int) (max - min + 1)) + min;
  System.out.println("ret = " + ret);
  return ret;
}

但是，结果并不准确，例如：

找不到 4194304 的 100 个数字。最终总和 = 4194305.0

我认为我在这一点上失去了准确性：

(sum * ret[i]) / iniSum

您能否在我的代码中推荐一种替代算法或修复方法来帮助我实现这一目标？

4

10 回答 10

6

每次用 缩放一个值时ret[i] = Math.round((sum * ret[i]) / iniSum)，都会损失一些精度，部分原因是除法运算本身，但主要是因为将缩放后的值存储为整数。后一种情况类似于比例选举制度，其中少数席位必须按比例分配给大量选票。

缓解这种情况的两种技术：

首先缩放列表中的所有值，但跟踪理想缩放值（实数）和存储的缩放值之间的差异。使用截断而不是四舍五入，以便差异始终为正。如果存在差异，您可以按照理想数量和当前存储数量之间的差异顺序增加一些值。

long finSum = 0;  // Might as well be a long
float[] idealValues = new float[size];
for (int i = 0 ; i < ret.length; i++) {
    ideal[i] = (sum * ret[i]) / iniSum;
    ret[i] = (long) (ideal[i]);  // Truncate, not round
    System.out.println("ret[" + i +"] = " + ret[i]);
    finSum += ret[i];
}

/* There are iniSum - finSum extra amounts to add. */
for (int i = 0; i < iniSum - finSum; i++)
{
    /* Pick a target slot to increment.  This could be done by keeping a priority queue. */
    int target = 0;
    float bestScore = 0.0;
    for (int j = 0; j < size; j++) {
        float score = (ideal[j] - ret[j])/ret[j];
        if (score > bestScore) {
            target = j;
            bestScore = score;
        }
    }

    /* Allocate an additional value to the target. */
    ret[target]++;
}

或者更简单地说，您可以将列表中的最后一个值设置为缩放完成所有其他值之后的突出值。然而，这确实会在统计上扭曲输出。

于 2012-04-05T02:35:14.490 回答
3

刚刚有了一个想法。将数组初始化为全0。随机选择数组中的一个数字，然后加1，减1，直到总和为0。总和很大时根本不实用:)

long ret = new long[size];
for(int i=0;i<size;i++) ret[i]=0;
for(int i=0;i<sum;i++) {
  int n = random(0,size);
  ret[n]++;
}
于 2012-04-05T02:25:14.807 回答
2

是的，有一种标准方法可以避免浮点数不准确。它与计算数字相加的方式数的方法有关ns。它并不复杂，但奇怪的是还没有人提到它，所以这里是：

想象一下，我们有一个带有n-1X 和so 的字符串。因此，例如，对于 s=5，n=3，一个示例字符串将是

oXooXoo

请注意，X 将 o 分为三个不同的组：长度 1、长度 2 和长度 2 之一。这对应于解 [1,2,2]。通过计算组合在一起的 o 的数量，每个可能的字符串都为我们提供了不同的解决方案（0 是可能的：例如，XoooooX将对应于 [0,5,0]）。

所以，我们需要做的就是想象通过为n-1X 选择随机位置来创建这样一个字符串，然后找出对应的解决方案。以下是更详细的细分：

  1. 在 之间生成n-1唯一的随机数[1, s+n-1]。使用拒绝抽样来做到这一点很简单——如果一个数字被选择了两次，只需放下它并选择另一个。
  2. 对它们进行排序，然后找出每个 X 之间的 o 数。这个数字原来是currentValue - previousValue - 1。

最后，这里是一些应该执行此操作的示例 Java（未经测试）：

private List<long> getRandomSequenceWithSum(int numValues, long sum)
{
    List<long> xPositions = new List<long>();
    List<long> solution = new List<long>();
    Random rng = new Random();

    //Determine the positions for all the x's
    while(xPositions.size() < numValues-1)
    {
        //See https://stackoverflow.com/a/2546186/238419
        //for definition of nextLong
        long nextPosition = nextLong(rng, sum+numValues-1) + 1; //Generates number from [1,sum+numValues-1]
        if(!xPositions.contains(nextPosition))
            xPositions.add(nextPosition);
    }

    //Add an X at the beginning and the end of the string, to make counting the o's simpler.
    xPositions.add(0);
    xPositions.add(sum+numValues);
    Collections.sort(xPositions);

    //Calculate the positions of all the o's
    for(int i = 1; i < xPositions.size(); i++)
    {
        long oPosition =  xPositions[i] - xPositions[i-1] - 1;
        solution.add(oPosition);
    }

    return solution;
}
于 2012-04-06T16:49:01.047 回答
1

我相信您的问题在于Math.round尝试修改代码以使用双精度并避免任何精度损失

于 2012-04-05T02:16:20.567 回答
1

一个好的方法是使用一个间隔列表，然后在每个步骤中对其进行拆分。这是伪代码

 array intervals = [(0,M)]
   while number intervals<desired_number
     pick an split point x
     find the interval containing x
     split that interval at x

如果你想非常小心，你需要检查你的分割点 x 不是间隔的终点。你可以通过拒绝来做到这一点，或者你可以选择要拆分的区间，然后在哪里拆分该区间，但在这种情况下，你需要小心不要引入偏见。（如果你关心偏见）。

于 2012-04-05T02:35:22.330 回答
0

这个怎么样：

long finSum = 0;
for (int i = 0 ; i < ret.length; i++) {
  ret[i] =  Math.round((sum * ret[i]) / iniSum);
  System.out.println("ret[" + i +"] = " + ret[i]);
  finSum += ret[i];
}
ret[0] += sum - finSum;

换句话说，将所有舍入误差放入第一个元素中。

于 2012-04-05T02:29:09.373 回答
0

建议：

  for (int i = 0 ; i < ret.length; i++) {
    ret[i] = randomInRange(1, sum);
    iniSum += ret[i];
  }

在第一个 for 循环中，不是从 0 迭代到 (ret.length-1)，而是仅使用从 0 到 (ret.length-2) 的迭代。保留最后一个元素进行调整。

也不要调用 randomInRange(1, sum)，而是使用 randomInRange(1, sum-iniSum)。这将减少所需的标准化。

最后，最后一个输出数字将是 (sum-iniSum)。因此，可以删除第二个 for 循环。

于 2012-04-05T02:29:39.037 回答
0

拿一个号码。从中减去一个合理的随机数。重复直到你得到足够的数字。根据定义，它们的总和是固定的，并且等于初始数字。您在需要的数字数量处进行精确n操作；n没有猜测。

这是Python代码：

import random
def generate_randoms(initial, n):
  # generates n random numbers that add up to initial.
  result = [] # empty list
  remainder = initial # we'll subtract random numbers and track the remainder
  numbers_left = n
  while numbers_left > 1:
    # guarantee that each following step can subtract at least 1
    upper_bound = remainder - numbers_left 
    next_number = random.randrange(1, upper_bound) # [1, upper_bound) 
    result.append(next_number)
    remainder -= next_number # chop off
    numbers_left -= 1
  result.append(remainder) # we've cut n-1 numbers; don't forget what remains
  return result

它有效，但它有一个缺点：数字越远，它们越小。您可能需要对结果列表进行洗牌来解决这个问题，或者使用较小的上限。

于 2012-04-05T02:44:17.240 回答
0

这肯定是一个有趣的问题（赞成！），我期待看到一些更有创意的解决方案。我对您列出的代码的一个问题是您正在使用Random该类，它只返回整数，而不是长整数，但是您只需将其转换为长整数。因此，如果您的函数确实需要 long，则必须找到不同的随机数生成器。

“理想”的解决方案是生成所有可能的加法组合（称为分区），然后随机选择一个。然而，最知名的算法确实非常昂贵。关于这个问题有很多很好的源材料。这是关于分区算法的特别好的阅读：

http://www.site.uottawa.ca/~ivan/F49-int-part.pdf

部分问题是在这种情况下弄清楚你所说的“随机”是什么意思。例如，如果您要查找一个由 5 个数字组成且总和为 1000 的数组，则 {1000,0,0,0,0} 与 {200,200,200,200,200} 一样有效，与 {136,238,124,66,436} 一样有效. 具有相同机会生成任何这些集合的算法将是真正随机的。

但是，我猜您不是在寻找完全随机的分布，而是介于两者之间。

不幸的是，我的 Java 已经很生疏了，而且这些天我几乎所有的事情都是用 C# 做的，所以我将用 C# 来介绍……将这些算法转换成 Java 不需要太多的翻译。

这是我对这个问题的看法：

public int[] GetRandoms( int size, int sum, Random r=null ) {
  if( r==null ) r = new Random();
  var ret = new int[size];
    while( sum > 0 ) {
      var n = r.Next( 1, (int)Math.Ceiling((double)sum/size)+1 );
      ret[r.Next(size)] += n;
      sum -= n;
    }
    return ret;
}

（实际上，看看我是如何传入我的随机数生成器null的？为了方便起见，我将其默认为并创建一个新的，但现在我可以传入一个种子随机数生成器，并在以下情况下生成相同的结果我希望，这非常适合测试目的。每当您有使用随机数生成器的方法时，我强烈建议采用这种方法。）

该算法基本上不断将随机数添加到数组中的随机条目，直到达到总和。由于它的加法性质，它将有利于更大的数字（即，小数字极不可能出现在结果中）。但是，这些数字看起来是随机的，并且它们会适当地相加。

如果您的目标数量很小（比如说 100 以下），您实际上可以实现真正的随机方法，即生成所有分区并随机选择一个。例如，这是一个分区算法（由http://homepages.ed.ac.uk/jkellehe/partitions.php提供，翻译成 C#）：

public List<int[]> GetPartitions( int n ) {
var result = new List<int[]>();
var a = new int[n+1];
var k = 1;
a[0] = 0;
var y = n - 1;
while( k != 0 ) {
    var x = a[k-1] + 1;
    k--;
    while( 2*x <= y ) {
        a[k] = x;
        y -= x;
        k++;
    }
    var l = k + 1;
    while( x <= y ) {
        a[k] = x;
        a[l] = y;
        result.Add( a.Take( k + 2 ).ToArray() );
        x++;
        y--;
    }
    a[k] = x + y;
    y = x + y - 1;
    result.Add( a.Take( k + 1 ).ToArray() );
}
return result;
}

（为了帮助您进行 Java 翻译，a.Take(x)意味着将第一个x元素从数组中取出a......我相信这些天在 Java 中有一些等效的魔法可以做到这一点。）

这将返回一个分区列表......只需随机选择一个，您将获得完美的随机分布。

于 2012-04-05T07:55:07.633 回答
0

-这个怎么样？

private long[] getRandoms(int size , long sum) {
    long[] array = new long[size];
    long singleCell = sum / size;
    Arrays.fill(array, singleCell);
    array[size-1] += sum % singleCell;
    int numberOfCicles = randomInRange(size, size*10);
    for (int i = 0; i < numberOfCicles; i++) {
        int randomIndex = randomInRange(0, size);
        long randomNumToChange = randomInRange(0, array[randomIndex]);
        array[randomIndex] -= randomNumToChange;
        array[randomInRange(0, size)] += randomNumToChange;
    }
    return array;
}
于 2012-04-05T08:27:32.623 回答