nJava で、「線形降順分布」の間1でランダムな整数を作成するにはどうすればよいですか。k123k
このトピックにはすでに数十のスレッドがあることを知っており、新しいスレッドを作成して申し訳ありませんが、それらから必要なものを作成できないようです. 私はimport java.util.*;、コードを使用することを知っています
Random r=new Random();
int n=r.nextInt(k)+1;
1との間のランダムな整数を作成し、k一様に分散します。
一般化:任意に分散された整数 (つまりf(n)=some function, P(n)=f(n)/(f(1)+...+f(k))) を作成するためのヒントも歓迎されます。たとえば、次のようになります。
.
これにより、必要なものが得られます。
public static int getLinnearRandomNumber(int maxSize){
//Get a linearly multiplied random number
int randomMultiplier = maxSize * (maxSize + 1) / 2;
Random r=new Random();
int randomInt = r.nextInt(randomMultiplier);
//Linearly iterate through the possible values to find the correct one
int linearRandomNumber = 0;
for(int i=maxSize; randomInt >= 0; i--){
randomInt -= i;
linearRandomNumber++;
}
return linearRandomNumber;
}
また、開始インデックスから停止インデックスまでの範囲に沿った POSITIVE 関数 (負の関数は実際には意味がありません) の一般的な解決策を次に示します。
public static int getYourPositiveFunctionRandomNumber(int startIndex, int stopIndex) {
//Generate a random number whose value ranges from 0.0 to the sum of the values of yourFunction for all the possible integer return values from startIndex to stopIndex.
double randomMultiplier = 0;
for (int i = startIndex; i <= stopIndex; i++) {
randomMultiplier += yourFunction(i);//yourFunction(startIndex) + yourFunction(startIndex + 1) + .. yourFunction(stopIndex -1) + yourFunction(stopIndex)
}
Random r = new Random();
double randomDouble = r.nextDouble() * randomMultiplier;
//For each possible integer return value, subtract yourFunction value for that possible return value till you get below 0. Once you get below 0, return the current value.
int yourFunctionRandomNumber = startIndex;
randomDouble = randomDouble - yourFunction(yourFunctionRandomNumber);
while (randomDouble >= 0) {
yourFunctionRandomNumber++;
randomDouble = randomDouble - yourFunction(yourFunctionRandomNumber);
}
return yourFunctionRandomNumber;
}
注: 負の値を返す可能性のある関数の場合、1 つの方法として、その関数の絶対値を取得し、それを yourFunction 呼び出しごとに上記のソリューションに適用することができます。
したがって、最も可能性の低いものから最も可能性の高いものまで、次の分布が必要です。
*
**
***
****
*****
等
一様分布の整数確率変数をその分布にマッピングしてみましょう。
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
等
このように、1からたとえばこの場合は15までの均一に分散されたランダム整数を生成する場合、K = 5それがどのバケットに適合するかを把握する必要があります。トリッキーな部分は、これを行う方法です。
右側の数字は三角数であることに注意してください！これは、ランダムに生成されたXfrom1から、の場合、そのようなものT_nを見つける必要があることを意味します。幸い、与えられた数の「三角形のルート」を見つけるための明確に定義された式があります。これは、一様分布からバケットへのマッピングのコアとして使用できます。NT_(n-1) < X <= T_n
// Assume k is given, via parameter or otherwise
int k;
// Assume also that r has already been initialized as a valid Random instance
Random r = new Random();
// First, generate a number from 1 to T_k
int triangularK = k * (k + 1) / 2;
int x = r.nextInt(triangularK) + 1;
// Next, figure out which bucket x fits into, bounded by
// triangular numbers by taking the triangular root
// We're dealing strictly with positive integers, so we can
// safely ignore the - part of the +/- in the triangular root equation
double triangularRoot = (Math.sqrt(8 * x + 1) - 1) / 2;
int bucket = (int) Math.ceil(triangularRoot);
// Buckets start at 1 as the least likely; we want k to be the least likely
int n = k - bucket + 1;
nこれで、指定された分布を持つはずです。
rlibby に触発された別の答えも試してみましょう。この特定の分布は、同じ範囲から一様にランダムに選択された 2 つの値のうち小さい方の分布でもあります。
累積分布関数 (cdf) を計算できる分布であれば、配列などでこれをシミュレートする必要はありません。上に確率分布関数 (pdf) があります。曲線の下の面積は 1 でなければならないため、h は実際に決定されます。数学を簡単にするために、[0,k) の数値を選択していると仮定します。
ここの pdf は f(x) = (2/k) * (1 - x/k) です。cdf は pdf と完全に統合されています。ここでは、F(x) = (2/k) * (x - x^2 / 2k) です。(積分可能な場合は、任意の pdf 関数に対してこのロジックを繰り返すことができます。)
次に、cdf 関数の逆関数 F^-1(x) を計算する必要があります。
しかし、良いニュースは次のとおりです。F^-1(x) を取得したら、それを [0,1] のランダム値分布に一様に適用し、それに関数を適用するだけです。java.util.Random は、注意を払ってそれを提供できます。これは、分布からランダムにサンプリングされた値です。
これは三角分布と呼ばれますが、最頻値が最小値に等しい縮退した場合です。ウィキペディアには、一様分布（0,1）変数が与えられた場合の作成方法に関する方程式があります。
このようなもの....
class DiscreteDistribution
{
// cumulative distribution
final private double[] cdf;
final private int k;
public DiscreteDistribution(Function<Integer, Double> pdf, int k)
{
this.k = k;
this.cdf = new double[k];
double S = 0;
for (int i = 0; i < k; ++i)
{
double p = pdf.apply(i+1);
S += p;
this.cdf[i] = S;
}
for (int i = 0; i < k; ++i)
{
this.cdf[i] /= S;
}
}
/**
* transform a cumulative distribution between 0 (inclusive) and 1 (exclusive)
* to an integer between 1 and k.
*/
public int transform(double q)
{
// exercise for the reader:
// binary search on cdf for the lowest index i where q < cdf[i]
// return this number + 1 (to get into a 1-based index.
// If q >= 1, return k.
}
}
頭に浮かぶ最初の解決策は、ブロック配列を使用することです。各インデックスは、必要な「可能性」に応じて値の範囲を指定します。この場合、k の値が小さい (1 としましょう) に達するまで、1 の範囲を広くし、2 の範囲を狭くします。
int [] indexBound = new int[k];
int prevBound =0;
for(int i=0;i<k;i++){
indexBound[i] = prevBound+prob(i);
prevBound=indexBound[i];
}
int r = new Random().nextInt(prevBound);
for(int i=0;i<k;i++){
if(r > indexBound[i];
return i;
}
問題は、乱数を見つけて、その数をバケットにマッピングすることです。各間隔の幅を離散化できる場合は、任意の分布に対してこれを行うことができます。アルゴリズムまたはその正確さを説明する際に何か不足している場合はお知らせください。言うまでもなく、これは最適化する必要があります。
最も簡単な方法は、重みで可能なすべての値のリストまたは配列を生成することです。
int k = /* possible values */
int[] results = new int[k*(k+1)/2];
for(int i=1,r=0;i<=k;i++)
for(int j=0;j<=k-i;j++)
results[r++] = i;
// k=4 => { 1,1,1,1,2,2,2,3,3,4 }
// to get a value with a given distribution.
int n = results[random.nextInt(results.length)];
これは、比較的小さな k 値に最適です。k < 1000.;)
より大きな数の場合は、バケット アプローチを使用できます
int k =
int[] buckets = new int[k+1];
for(int i=1;i<k;i++)
buckets[i] = buckets[i-1] + k - i + 1;
int r = random.nextInt(buckets[buckets.length-1]);
int n = Arrays.binarySearch(buckets, r);
n = n < 0 ? -n : n + 1;
二分探索のコストはかなり小さいですが、直接検索ほど効率的ではありません (小さな配列の場合)。
任意分布の場合double[]、累積分布に a を使用し、二分探索を使用して値を見つけることができます。
カスタム分布 (離散分布とも呼ばれます) を使用して整数乱数を生成する方法は多数あります。選択は、選択する整数の数、分布の形状、分布が時間の経過とともに変化するかどうかなど、多くのことに依存します。
カスタム重み関数で整数を選択する最も簡単な方法の 1 つf(x)は、棄却サンプリング法です。f以下では、 の可能な最大値が であると想定していますmax。拒否サンプリングの時間の複雑さは平均して一定ですが、分布の形状に大きく依存し、最悪の場合は永久に実行されます。k棄却サンプリングを使用して [1, ]の整数を選択するには、次のようにします。
i[1, k]の一様乱数整数を選択します。f(i)/maxで、 を返しiます。それ以外の場合は、ステップ 1 に進みます。他のアルゴリズムの平均サンプリング時間は、分布 (通常は定数または対数) にそれほど大きく依存しませんが、多くの場合、セットアップ ステップで重みを事前に計算し、それらをデータ構造に格納する必要があります。それらのいくつかは、平均して使用するランダム ビット数の点でも経済的です。これらのアルゴリズムには、エイリアス メソッド、Fast Loaded Dice Roller、Knuth-Yao アルゴリズム、MVN データ構造などが含まれます。調査については、私のセクション「置換による加重選択」を参照してください。