八个随机整数的数组，其中每个整数与数组中的所有其他整数相差至少 15?

Question

我正在尝试编写一种方法来创建并返回一个长度为 8 且在[25, 725]范围内的随机Integer数组。

数组中的每个Integer必须比数组中的每个其他Integer高或低至少 15。但是，我的方法没有返回满足此要求的数组。

我设置了一个main()方法，该方法检查方法的输出 100,000 次，如果有任何Integers太近，则抛出Exception。

如何创建一个方法，该方法将返回一个Integers数组，其中每个Integer和每个其他Integer之间的差异至少为 15？

public class Test {
public static void main(String[] args) throws Exception {
Integer[] distances = new Integer[8];
for (int i = 0; i < 100000; i++) {
distances = createPlanetDistances(distances.length);
// check distances for values within 15
for (int x = 0; x < distances.length; x++) {
for (int y = 0; y < distances.length; y++) {
if (x == y)
continue;
if (Math.abs(distances[x] - distances[y]) < 15) {
System.out.println(distances[x] + " " + distances[y]);
throw new Exception("Doesn't work");
}
}
}
for (int distance : distances)
System.out.print(distance + " ");
System.out.println(System.lineSeparator());
}
}
/**
* Creates an array of distances-from-the-sun for a given number of Planets.
* It does not allow distances to be within 15 of any other distance.
*
* @param planetAmount The number of distances to return.
* @return An array of distances-from-the-sun.
*/
private static Integer[] createPlanetDistances(int planetAmount) {
SplittableRandom random = new SplittableRandom();
final int min = 25;
final int max = 726;
HashSet<Integer> distanceSet = new HashSet<>();
// make sure there are no duplicate Integers
for(int i = 0; i < planetAmount; i++) {
int num = random.nextInt(min, max);
while (distanceSet.contains(num))
num = random.nextInt(min, max);
distanceSet.add(num);
}
// make sure each distance is 15 away from all others
Integer[] distances = distanceSet.toArray(new Integer[]{});
for(int i = 0; i < distances.length; i++) {
// check distances[i] with all other Integers
for (int j = 0; j < distances.length; j++) {
// do not compare an element with itself
if (j == i)
continue;
int difference = Math.abs(distances[i] - distances[j]);
if (difference < 15) {
while (difference < 15) {
distances[i] = random.nextInt(min, max);
difference = Math.abs(distances[i] - distances[j]);
}
// check all Integers again
System.out.println("HERE " + i + " " + j);
i = 0;
break;
}
}
}
return distanceSet.toArray(new Integer[]{});
}
}

Answer 1

若要查找范围MIN到MAX(不包括)中相距超过DISTANCE的COUNT数字，请构建一个TreeSet并使用ceiling(...)方法查找附近的值。

例

final int DISTANCE = 15, MIN = 25, MAX = 726, COUNT = 8;
ThreadLocalRandom random = ThreadLocalRandom.current();
TreeSet<Integer> numbers = new TreeSet<>();
while (numbers.size() < COUNT) {
int value = random.nextInt(MIN, MAX);
Integer ceiling = numbers.ceiling(value - DISTANCE);
if (ceiling == null || ceiling > value + DISTANCE)
numbers.add(value);
}
System.out.println(numbers);

示例输出

[86, 104, 120, 369, 425, 532, 682, 713]

如果您不希望结果按升序排列，则始终可以随机排列结果。

工作原理

ceiling方法返回集合中大于或等于给定值的最小值，如果没有此类值，则返回 null。

因此，如果例如value为 134，DISTANCE为 15，则ceiling(value - DISTANCE)将找到>= 119 的最小值。如果该值为>= 149，那么我们知道附近的范围 119-149 是明确的，我们可以使用 134 值。

Answer 2

您正在生成行星轨道，因此单调增加的数字应该是可以的。您生成的每个数字都有以下数字对其施加的约束，并在生成后反过来对它们施加约束。

约束：如果要在min和max之间生成N轨道，并用D分隔，则第一个轨道的边界[min, max - D * (N - 1)]。这仅仅是因为你不能将以下N - 1颗行星打包到一个小于D * (N - 1)的空间中。

您可以随时更新第二个约束，因为新的最小值将是最后生成的数字 +D.这是一个简单的O(n)实现(假设生成随机数是O(1))：

final int DISTANCE = 15, MIN = 25, MAX = 726, COUNT = 8;
Random random = Random();
orbits = new int[COUNT];
if(MAX - MIN < DISTANCE * COUNT) {
throw new IllegalArgumentException("Insert pithy comment about COUNT");
}
min = MIN;
for(int i = 0; i < COUNT; i++) {
max = MAX - DISTANCE * (COUNT - i - 1);
orbits[i] = random.nextInt(max - min + 1) + min;
min = orbits[i] + DISTANCE;
}

Answer 3

以下方法通过消除间距要求、在相应缩短的范围内均匀生成值、将间距间隙相加并随机排列以产生结果来避免接受/拒绝抽样。

static Random r = new Random();
public static ArrayList<Integer>
gen_array(int lower_bound, int upper_bound, int n, int separation) {
upper_bound -= (n - 1) * separation;
if(upper_bound < lower_bound) {
throw new IllegalArgumentException("Infeasible arguments");
}
ArrayList<Integer> ary = new ArrayList<>();
while(ary.size() < n) {
ary.add(lower_bound + r.nextInt(upper_bound - lower_bound + 1));
}
Collections.sort(ary);
for (int i = 0; i < n; ++i) {
ary.set(i, ary.get(i) + i * separation);
}
Collections.shuffle(ary);
return ary;
}

如果你用值 8 表示n、lower_bound25、upper_bound130 和separation15 调用它，它会立即产生正确的结果，其中接受/拒绝方法可能需要大量的迭代来咳出答案的唯一值集。