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)、部分的に除算自体から精度が失われますが、ほとんどはスケーリングされた値を整数として格納するためです。後者の状況は、多数の票に比例して少数の議席を割り当てなければならない比例選挙制度に似ています。

これを軽減するための 2 つの手法:

最初にリスト内のすべての値をスケーリングしますが、スケーリングされた理想的な値 (実数) と保存されたスケーリングされた値との差を追跡します。不一致が常に正になるように、丸めの代わりに切り捨てを使用します。不一致がある場合は、理想的な量と現在の保存量の差の順にいくつかの値を増やすことができます。

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 に初期化します。配列内の数値をランダムに選択し、合計が 0 になるまで 1 ずつ増やし、合計を 1 減らします。合計が大きい場合はまったく実用的ではありません:)

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 を 3 つの異なるグループ (長さ 1、長さ 2、および長さ 2 のいずれか) に分割することに注意してください。これは、解 [1,2,2] に対応します。考えられるすべての文字列は、一緒にグループ化された o の数を数えることによって、異なる解決策を提供します(0 も可能です。たとえば、XoooooX[0,5,0] に対応します)。

したがって、X の位置をランダムに選択してそのような文字列を作成することを想像しn-1、それに対応する解を見つけ出すだけです。より詳細な内訳は次のとおりです。

  1. n-1の間に一意の乱数を生成[1, s+n-1]します。これを行うのは、棄却サンプリングを使用すれば十分簡単です。ある数値が 2 回選択された場合は、その数値をドロップして別の数値を選択するだけです。
  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、コードを変更して double を使用し、精度の低下を避けることにあると思います

于 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

これは確かに興味深い質問です (賛成票を投じてください!)。さらに創造的な解決策が見られることを楽しみにしています。リストしたコードで私が抱えている問題の1つはRandom、longではなく整数のみを返すクラスを使用していることですが、それをlongにキャストするだけです。したがって、関数が本当に long を必要とする場合は、別の乱数ジェネレーターを見つける必要があります。

「理想的な」解決策は、すべての可能な追加の組み合わせ (パーティションと呼ばれる) を生成し、ランダムに 1 つを選択することです。ただし、これを行うための最もよく知られているアルゴリズムは、実際には非常に高価です。この問題については、優れたソース資料がたくさんあります。パーティショニングアルゴリズムに関する特に良い読み物は次のとおりです。

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

問題の一部は、この場合の「ランダム」の意味を理解することです。たとえば、合計が 1000 になる 5 つの数値の配列を探している場合、{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 未満)、すべてのパーティションを生成し、ランダムに 1 つを選択するという真のランダム アプローチを実際に実現できます。たとえば、パーティショニング アルゴリズムは次のとおりです (礼儀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)最初の要素を取り出すことを意味します...最近の Java には、それを行うための同等の魔法があると確信しています。)xa

これにより、パーティションのリストが返されます...ランダムに1つを選択するだけで、完全にランダムな分布が得られます.

于 2012-04-05T07:55:07.633 に答える
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

-これはどう？

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 に答える
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) になります。したがって、2 番目の for ループは削除できます。

于 2012-04-05T02:29:39.037 に答える