java中的离散概率分布问题

Question

我试图解决一个入门级的java问题，但似乎不知道如何解决。目标如下：

编写一个程序DiscreteDistribution.java，它接受一个整数命令行参数m，然后是一系列正整数命令行自变量a1、a2、…、an，并打印m个随机索引(用空格分隔(，选择每个索引i的概率与ai成比例。

样本输入和输出如下：

> ~/Desktop/arrays> java DiscreteDistribution 25 1 1 1 1 1 1 5 2 4 4 5 5
> 4 3 4 3 1 5 2 4 2 6 1 3 6 2 3 2 4 1 4

到目前为止，我的实现如下：

public class DiscreteDistribution {
public static void main(String args[]) {
int n = args.length;
int[] freq = new int [n];
for(int i = 0; i < n; i++) {
freq[i] = Integer.parseInt(args[i]);
}
int total = 0;
for(int i = 1; i < freq.length;i++) {
total += freq[i];
}
int r = (int) (total * Math.random());
int sum = 0;
int event = -1;
for (int i = 0; i < n && sum <= r; i++) {
sum += freq[i];
event = i;
}
System.out.print(event);
}
}

问题的进一步文本建议如下：

定义累计和Si＝a1+a2+…+ai和S0＝0。在0和Sn−1之间均匀地选取一个随机整数r。求1和n之间的唯一索引i，使得Si−1≤r

我相信我已经在总变量中适当地定义了累积和，并选择了随机整数r。然而，我不知道如何找到唯一的索引。

Answer 1

在不重复的情况下获得m索引的随机样本的一个简单方法是生成一个序列，对其进行混洗，并获取第一个m项。

// Produce a sequence.
List<Integer> allIndices = new ArrayList<>();
for (int i = 0; i < freq.length; i += 1) allIndices.add(i);
// Shuffle the sequence in place.
Collection.shuffle(allIndices);
// Take a sublist of m elements, and use it.
List<Integer> indices = allIndices.subList(0, m - 1);
for (Integer ix : indices) {
// Here ix will be a unique random index into freq, use it.
} 

Answer 2

public class DiscreteDistribution {
public static void main(String[] args) {
int n = args.length;
int [] a = new int [n];
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(args[i]);
}
int [] s = new int [n];
for (int i = 1; i < n; i++) {
s[0] = 0;
s[i] = s[i-1] + a[i];
}
for (int m = 0; m < a[0]; m++) {
int index = 1;
int r = (int) (s[n-1] * Math.random());
for (int i = 1; i < n; i++) {
if (s[i-1] <= r && r < s[i])
index = i;
}
System.out.print(index + " ");
}
}
}