生成 N 位、3 位唯一随机整数，其中所有数字都是唯一的

Question

以下是我到目前为止尝试过的代码，它可以工作：

public static void main(String[] args) {
Random random = new Random();
Integer[] integers = random.ints(10, 100, 999).boxed().toArray(Integer[]::new);
List<Integer> list = new ArrayList<>();
for (int i = 0; i < integers.length; i++) {
String[] split = integers[i].toString().split("");
int a = 0, b = 0, c = 0;
a = Integer.valueOf(split[0]);
b = Integer.valueOf(split[1]);
c = Integer.valueOf(split[2]);
if ((a != b) && (a != c) && (b != c)) {
list.add(Integer.valueOf(integers[i]));
}
}
list.forEach(System.out::println);
}

输出正确。

如果abc是整数，则a !=b和a ! c和b !=c， 使所有数字唯一。

我尝试在流中应用后面的部分，但我没有得到预期的结果。有人可以指导我哪里出错了吗？

Java-8版本：

public static void main(String[] args) {
Random random = new Random();
Integer[] integers = random.ints(10, 100, 999).boxed().toArray(Integer[]::new);
String[] collect = Arrays.stream(integers).map(s -> {
String[] split = s.toString().split("");
return split;
}).filter(
k -> (Integer.valueOf(k[0]) != Integer.valueOf(k[1])) && (Integer.valueOf(k[0]) != Integer
.valueOf(k[2])) && (Integer.valueOf(k[1]) != Integer.valueOf(k[2])))
.toArray(String [] ::new);
Arrays.stream(collect).forEach(System.out::println);

}

Answer 1

将数字转换为字符串并调用split("")即将成为您能想到的最慢的解决方案。

如果您有 3 位数字，并且需要 3 位数字，请使用除法和余数运算符：

int i = /*assign some non-negative number of at most 3 digits*/;
int d1 = i / 100;
int d2 = i / 10 % 10;
int d3 = i % 10;

---

如果需要N数字，则无法生成N数字然后丢弃其中一些数字。这将使您的数字少于N。丢弃错误数字后，您必须计数。

static int[] generate(int n) {
// Numbers 100 and 101 contain duplicates, so lower limit is 102.
// Upper limit is 987 (inclusive), since 988, 989, and 99x all contain duplicates.
return new Random().ints(102, 988)
.filter(Test::isThreeUniqueDigits)
.limit(n)
.toArray();
}
private static boolean isThreeUniqueDigits(int i) {
int d1 = i / 100;
int d2 = i / 10 % 10;
int d3 = i % 10;
return (d1 != d2 && d1 != d3 && d2 != d3);
}

或者使用 lambda 表达式而不是方法引用：

static int[] generate(int n) {
return new Random().ints(102, 988).filter(i -> {
int d1 = i / 100, d2 = i / 10 % 10, d3 = i % 10;
return (d1 != d2 && d1 != d3 && d2 != d3);
}).limit(n).toArray();
}

示例结果

[416, 613, 401, 250, 507, 306, 179, 152, 850, 504]
[913, 304, 174, 874, 714, 245, 632, 890, 357, 382]
[618, 706, 946, 364, 209, 320, 690, 529, 824, 651]
[419, 386, 547, 471, 952, 917, 389, 469, 640, 285]
[120, 347, 549, 247, 619, 328, 814, 240, 984, 630]
[127, 174, 723, 287, 149, 329, 176, 964, 451, 617]
[539, 587, 768, 594, 296, 948, 157, 409, 952, 395]
[602, 392, 698, 761, 231, 764, 517, 147, 402, 841]
[194, 294, 923, 542, 362, 248, 352, 286, 407, 348]
[631, 502, 461, 439, 174, 278, 407, 394, 617, 370]
[754, 193, 539, 290, 504, 684, 921, 962, 724, 196]
[125, 586, 925, 857, 879, 761, 134, 620, 134, 723]
[457, 307, 524, 536, 249, 349, 901, 623, 247, 320]
[103, 903, 506, 645, 431, 802, 695, 761, 609, 867]
[569, 894, 608, 963, 681, 365, 162, 874, 452, 307]
[807, 178, 983, 837, 956, 273, 295, 527, 798, 406]
[157, 936, 398, 379, 618, 920, 957, 921, 430, 879]
[396, 280, 315, 569, 328, 138, 931, 623, 413, 926]
[987, 972, 518, 391, 138, 691, 372, 193, 402, 678]
[346, 328, 940, 768, 307, 419, 146, 950, 671, 530]

Answer 2

您正在拆分字符串，然后不合并拆分数组。

在.toArray(String [] ::new);之前添加.map(strings -> String.join("", strings))以解决问题。

Answer 3

一个方面没有处理：结果中的重复数字。

人们可以将结果收集在一个集合中，以具有唯一的数字。 我使用了一个LinkedHashSet，它保持生成的数字按相加顺序， 不像HashSet(w.r.t.到hashCode(或TreeSet(按顺序(那样特别排序。

然后，由于重复项需要更多尝试，因此无法使用随机整数列表。

您的算法将变为：

// Maximal different numbers 9*9*8 as different digits 10*9*8 and first digit not 0.
final int MAX_N = 9*9*8; // 648
int size = N;
if (size > MAX_N) {
throw new IllegalArgumentException("More than maximum " + MAX_N + ": " + size);
}
Set<Integer> result = new LinkedHashSet<Integer>();
Random random = new Random();
for (int i = 0; i < size; ++i) {
int n = randomUnique(random);
if (!result.add(n)) {
--i; // Already added, take a new random int.
// When size nears MAX_N the looping take enormous long!
}
}
System.out.println(result);

但是选择的随机唯一数字可以立即正确：

static int randomUnique(Random random) {
// 1-9
int d2 = 1 + random.nextInt(9);
int n = d2;
// 0-9 without d1
int d1 = random.nextInt(9); // As index in those digits.
if (d1 >= d2) {
++d1;
}
n = 10 * n + d1;
// 0-9 without d1 and d2
int d0 = random.nextInt(8); // As index in those digits.
if (d0 >= d1 || d0 >= d2) {
++d0;
if (d0 >= d1 && d0 >= d2) {
++d0;
}
}
n = 10 * n + d0;
return n;
}

如前所述，当大小接近MAX_N时，该算法将尝试大量随机唯一调用。

更好的方法是取 100-999 之间的所有数字的集合，然后随机取一个大小合适的子集。

因为这似乎是某种难题，家庭作业，只是指向更好，通常更快的算法的一些指针：

BitSet uniqueNumbers = new BitSet(1000);
for (int num = 100; num < 1000; ++num) {
uniqueNumbers.set(num, isUnique(num));
}
... take N elements
boolean isUnique(int num) {
...
}

Answer 4

您可以首先生成有效数字，而不是生成随机数来测试它们并删除无效数字。

只需逐个数字生成它们。第一个，在百位，必须在 1...9范围没有额外的约束，所以我们可以直接生成它。第二个必须在 0...9 范围，但它不能等于第一个，所以我们可以在 1...9 范围，如果等于第一个，则用零替换它。同样，最后一个位置的数字在 2...9 范围，如果等于第一个数字，则替换为零，如果等于第二个数字，则替换为 1。然后，我们有一个有效的数字，无需重复该过程。

作为一个简单的循环，它看起来像

if(N > 648) throw new IllegalArgumentException("There can't be "+N+" unique numbers");
ThreadLocalRandom r = ThreadLocalRandom.current();
Set<Integer> result = new LinkedHashSet<>(N);
while(result.size() < N) {
int hundreds = r.nextInt(1, 10);
int tens = r.nextInt(1, 10);
if(tens == hundreds) tens = 0;
int ones = r.nextInt(2, 10);
if(ones == hundreds) ones = 0;
if(ones == tens) ones = 1;
result.add(hundreds * 100 + tens * 10 + ones);
}

通过使用Set并测试大小而不是使用计数循环，我们确保生成N唯一数字。

---

或者，我们可以先创建一个所有有效数字的可重用列表，然后任务更改为"从列表中选择 N 个项目"，也可以在其他上下文中重用。

生成所有有效数字很简单，遍历所有数字并跳过无效数字，然后计算数字，同样，这比迭代所有数字并测试它们更简单，需要昂贵的数字提取。

List<Integer> validNumbers = new ArrayList<>();
for(int h = 1; h < 10; h++) {
for(int t = 0; t < 10; t++) {
if(t == h) continue;
for(int o = 0; o < 10; o++) {
if(o != t && o != h) validNumbers.add(h * 100 + t * 10 + o);
}
}
}

然后，我们可以挑选N独特的元素：

if(N > validNumbers.size()) throw new IllegalArgumentException();
// copying, so validNumbers can be reused
List<Integer> result = new ArrayList<>(validNumbers);
if(N == result.size()) {
Collections.shuffle(result);
}
else {
for (int i = 0; i < N; i++) {
Collections.swap(result, i, r.nextInt(i, result.size()));
}
result.subList(N, result.size()).clear();
}

第一个分支，当N == validNumbers.size()时，我们只需要洗牌数字并N有效的随机元素。另一种选择，当N较小时，基本上与shuffle内部所做的相同，但省略了我们不选择的元素的工作，并在最后删除它们。

---

我们可以用 Stream API 表达相同的逻辑，但这并不总是一个胜利。

第一个变体可能是

List<Integer> result = IntStream.generate(() -> {
ThreadLocalRandom r = ThreadLocalRandom.current();
int h = r.nextInt(1, 10), t = r.nextInt(1, 10), o = r.nextInt(2, 10);
if(t == h) t = 0;
if(o == h) o = 0;
if(o == t) o = 1;
return h * 100 + t * 10 + o;
})
.distinct().limit(N).boxed()
.collect(Collectors.toList());

如果int[]数组结果足够，您可以将.boxed().collect(Collectors.toList())替换为toArray()。

对于第二种方法，我们可以使用

int[] validNumbers = IntStream.range(1, 10)
.flatMap(h -> IntStream.range(0, 10).filter(t -> t != h)
.flatMap(t -> IntStream.range(0, 10).filter(o -> o != t && o != h)
.map(o -> h * 100 + t * 10 + o)))
.toArray();

获取有效数字和

List<Integer> result = ThreadLocalRandom.current()
.ints(0, validNumbers.length)
.distinct().limit(N)
.mapToObj(ix -> validNumbers[ix])
.collect(Collectors.toList());

选择N不同的元素(这可能比shuffle方法更昂贵(。同样，当int[]数组结果足够时，您可以将.mapToObj(ix -> validNumbers[ix]) .collect(Collectors.toList())替换为.map(ix -> validNumbers[ix]) .toArray()。