Генерируйте N, 3 di git уникальных случайных чисел, где все цифры уникальны - PullRequest
Новая
       3

Генерируйте N, 3 di git уникальных случайных чисел, где все цифры уникальны

0 голосов
/ 17 января 2020

Ниже приведен мой код, который я пробовал до сих пор, и он работает: 

  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);
  }

Вывод правильный.

Если ab c является целым числом, тогда 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);



  }

Ответы [ 4 ]

6 голосов
/ 17 января 2020

Преобразование числа в строку и вызов split("") - это примерно самое медленное возможное решение, которое вы когда-либо могли придумать.

Если у вас 3-ди git число, и вам нужны 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);
}

Или использовать лямбда-выражение вместо ссылки на метод: 

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]
4 голосов
/ 17 января 2020

Вы разделяете строку, а затем не объединяете массив разбиения после этого.

Добавьте .map(strings -> String.join("", strings)) перед .toArray(String [] ::new);, чтобы решить проблему.

3 голосов
/ 17 января 2020

Один аспект не рассматривается: повторяющиеся числа в результате.

Можно также собрать результат в наборе, чтобы иметь также уникальные числа. Я использовал LinkedHashSet, который хранит сгенерированные числа в порядке их добавления, а не сортируется специально, как если бы HashSet (по отношению к 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;
}

Как прокомментировано этот алгоритм будет пытаться выполнить очень много вызовов randomUnique, когда размер приближается к 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) {
    ...
}
2 голосов
/ 17 января 2020

Вместо генерации случайных чисел, чтобы проверить их и отбросить недействительные, вы можете сгенерировать правильные числа в первую очередь.

Просто сгенерируйте их di git по di git. Первый, в позиции сотен, должен находиться в диапазоне 1… 9 без дополнительных ограничений, чтобы мы могли генерировать его напрямую. Второй должен находиться в диапазоне 0… 9, но он не должен быть равен первому, поэтому мы можем сгенерировать di git в диапазоне 1… 9 и заменить его на ноль, если он равен первому. Аналогично, di git для последней позиции генерируется в диапазоне 2… 9 и заменяется на ноль, если равен первому числу, или на единицу, если равен второму. Затем у нас есть действительное число без необходимости повторять процесс.

Как простой l oop, он выглядит как 

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 и тестируя размер вместо использования подсчета l oop, мы гарантируем генерацию N уникальных чисел.

В качестве альтернативы, мы можем сначала создать список всех допустимых чисел многократного использования, а затем задача изменится на «Выбрать N элементов из списка», которые также можно использовать в других контекстах.

Создать все действительные числа просто, перебрать все цифры и пропустить недопустимые, затем вычислить число, опять же, это проще, чем перебирать все числа и проверять их, требуя дорогого извлечения di git. 

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 внутри, но пропускает работу для элементов, которые мы не выбираем, и удаляет их в конце.

Мы может express тот же лог c с 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());

Вы можете заменить .boxed().collect(Collectors.toList()) на toArray(), если достаточно массива int[].

Для второго подхода мы можем использовать 

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). Опять же, вы можете заменить .mapToObj(ix -> validNumbers[ix]) .collect(Collectors.toList()) на .map(ix -> validNumbers[ix]) .toArray(), когда достаточно результата массива int[].

...