Генерация случайных чисел, где разница всегда положительна

Question

Я пытаюсь сгенерировать некоторые числа, чтобы разница всегда была положительной.пользователь вводит количество цифр и количество строк, которые они хотят.например, 3 цифры, 3 строки:

971
888
121

Я хочу убедиться, что разница между ними всегда положительна.Есть ли какой-то алгоритм, который я могу использовать.прямо сейчас у меня есть программа, которая создает числа, затем вычитает их, и если получится отрицательный результат, он сделает это снова ... и снова.Это очень медленно.

Я думал о том, чтобы сначала создать разницу, а затем добавить ее, пока не будет достигнуто количество нужных строк.Но я столкнулся с проблемами, если я генерирую очень большое количество.

вот код, который я использую для генерации случайного числа с X цифрами, на всякий случай, если это имеет значение

private fun createRandomNumber(digits: Int): Int {
        val numberArray = IntArray(digits)
        for (number in 0 until numberArray.size){
            numberArray[number] = 9
        }
        val maxnumber:Int = numberArray.joinToString("").toInt()
        numberArray[0] = 1
        for (number in 1 until numberArray.size){
            numberArray[number] = 0
        }
        val minnumber:Int = numberArray.joinToString("").toInt()
        return (minnumber..maxnumber).random()
    }

, основываясь на предложении Джеффа Боумена, я начал с сортировки массива:все числа, которые генерируются, и это ускоряет все до приемлемого количества!

Answer 1

Даже если решение @forpas в порядке, оно все равно работает на O(n log n) из-за окончательной сортировки.Мое решение просто генерирует увеличивающиеся интервалы, где генерируются случайные числа (для равномерного распределения), а затем map каждый интервал к случайному числу в этом диапазоне, что позволяет избежать необходимости сортировки окончательного списка.Сложность O(n)

Я решил использовать Stream, чтобы избежать мутации или явной рекурсии, но это не обязательно.

Пример

fun main(args: Array<String>) {
    val count = 20L
    val digits = 5

    val min =  pow(10.0, digits.toDouble() - 1).toLong()
    val max = min*10 - 1
    val gap = (max - min)/count + 1

    val numbers =
        Stream.iterate(Pair(min, min + gap)) { (_, prev) -> Pair(prev, prev + gap) }
            .map { (start, end) -> Random.nextLong(start, end) }
            .limit(count)
            .collect(Collectors.toList()) 

    numbers.forEach(::println)
}

Выход

11298
16284
20841
26084
31960
35538
37208
45325
46970
52918
57514
59769
67689
70135
75338
78075
84561
86652
91938
99931

Answer 2

Я бы использовал эту функцию для создания случайного числа с определенным количеством цифр:

fun createRandomNumber(digits: Int) = (10f.pow(digits - 1).toInt() until 10f.pow(digits).toInt()).shuffled().first()

вам понадобится этот импорт:

import kotlin.math.pow

И затем с этим:

fun main(args: Array<String>) {
    print("how many numbers?: ")
    val numbers = readLine()!!.toInt()
    print("how many digits?: ")
    val digits = readLine()!!.toInt()

    val set = mutableSetOf<Int>()

    do {
        set.add(createRandomNumber(digits))
    } while (set.size < numbers)

    val array = set.toTypedArray().sortedArrayDescending()
    array.forEach { println(it) }
}

Вы получаете ввод пользователя и создаете набор случайных чисел.С toTypedArray().sortedArrayDescending() вы получите массив.