Генерировать массив уникальных случайных чисел в пределах включенного диапазона

Я пытаюсь написать функцию в Apple Swift (iOS), которая будет генерировать любое заданное количество уникальных случайных чисел, которые находятся в пределах данного открытого диапазона, скажем, между 0 и 10. Поэтому, если я скажу, что хочу 5 уникальных случайных чисел между 0 и 10, он возвратит массив с [7, 10, 2, 3, 0] или [7, 10, 2, 8, 0] и т.д.

У меня есть эта часть, работающая с:

// Returns an array of unique numbers
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: ******) -> [Int] {
 var uniqueNumbers = [Int]()
 while uniqueNumbers.count < numberOfRandoms {
 let randomNumber = Int(arc4random_uniform(maxNum + 1)) + minNum
 var found = false
 for var index = 0; index < uniqueNumbers.count; ++index {
 if uniqueNumbers[index] == randomNumber {
 found = true
 break
 }
 }
 if found == false {
 uniqueNumbers.append(randomNumber)
 }
 }
 return uniqueNumbers
}
print(uniqueRandoms(5, minNum: 0, maxNum: 10))

Теперь я хочу добавить возможность черного списка одного номера в пределах этого диапазона, который я не хочу. Скажем, я все еще хочу 5 уникальных случайных чисел от 0 до 10, но я не хочу, чтобы он когда-либо включал 8.

Эта часть вызывает бесконечный цикл (25% + времени или более), и я не могу понять, почему? Вот что у меня есть:

var blackListNum = 8
// Returns an array of unique numbers
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: ******, checkBlackList: Bool = false) -> [Int] {
 var uniqueNumbers = [Int]()
 while uniqueNumbers.count < numberOfRandoms {
 let randomNumber = Int(arc4random_uniform(maxNum + 1)) + minNum
 var found = false
 for var index = 0; index < uniqueNumbers.count; ++index {
 if checkBlackList == false {
 if uniqueNumbers[index] == randomNumber {
 found = true
 break
 }
 } else {
 if uniqueNumbers[index] == randomNumber || uniqueNumbers[index] == blackListNum {
 found = true
 break
 }
 }
 }
 if found == false {
 uniqueNumbers.append(randomNumber)
 }
 }
 return uniqueNumbers
}
print(uniqueRandoms(5, minNum: 0, maxNum: 10, checkBlackList: true))

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

6 ответов

Вы можете сделать свою жизнь намного проще, используя Set для хранения всех случайных чисел, пока не достигнете ожидаемого количества рандомов:

func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: ******) -> [Int] {
 var uniqueNumbers = Set<int>()
 while uniqueNumbers.count < numberOfRandoms {
 uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
 }
 return Array(uniqueNumbers).shuffle
}
print(uniqueRandoms(5, minNum: 0, maxNum: 10))
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: ******, blackList: Int?) -> [Int] {
 var uniqueNumbers = Set<int>()
 while uniqueNumbers.count < numberOfRandoms {
 uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
 }
 if let blackList = blackList {
 if uniqueNumbers.contains(blackList) {
 while uniqueNumbers.count < numberOfRandoms+1 {
 uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
 }
 uniqueNumbers.remove(blackList)
 }
 }
 return Array(uniqueNumbers).shuffle
}
uniqueRandoms(3, minNum: 0, maxNum: 10, blackList: 8) // [0, 10, 7]
</int></int>

Вам понадобится это расширение, чтобы перетасовать результат:

extension Array {
 var shuffle:[Element] {
 var elements = self
 for index in 0..


Прямой подход заключается в том, чтобы создать массив чисел на выбор, а затем удалить числа по мере их выбора:

// create an array of 0 through 10
var nums = Array(0...10)
// remove the blacklist number
nums.removeAtIndex(nums.indexOf(8)!)
var randoms = [Int]()
for _ in 1...5 {
 let index = Int(arc4random_uniform(******(nums.count)))
 randoms.append(nums[index])
 nums.removeAtIndex(index)
}

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


Распределение решений и производительности в Swift 4.0

Недавно мне стало нужно решение этой же проблемы, но без черного списка, и я увидел ответы на этой странице, а также на этом вопросе, но Меня беспокоила производительность, когда набор номеров на выбор был очень большим, а также при выборе большого количества номеров (например, там, где вы выбираете более 50% номеров в общем пуле).

Итак, я опробовал несколько решений.

Первым был вид, в котором вы выбираете номер в случайном порядке, проверьте, был ли ранее выбран номер, и либо выберите другой вариант, либо добавьте его в список чисел.

func randomNumber(between lower: Int, and upper: Int) -> Int {
 return Int(arc4random_uniform(******(upper - lower))) + lower
}
func generateRandomUniqueNumbers1(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
 guard iterations <= (upper - lower) else { return [] }
 var numbers: [Int] = []
 (0..
<p>Второе решение в значительной степени совпадает с тем, которое предлагает vacawama. Вы начинаете с загрузки массива всех доступных номеров, выбираете один случайным образом и удаляете его из доступного массива и добавляете его в свой массив чисел. Повторяйте столько чисел, сколько хотите.</p> <pre class="prettyprint linenums">func generateRandomUniqueNumbers2(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] { guard iterations <= (upper - lower) else { return [] } var indices: [Int] = (lower..</pre><code> <p>Третьим решением была адаптация первого решения для устранения того факта, что массивы медленны при поиске элементов внутри них. Изменяя массив сохраненных чисел в Set, эта операция должна выполняться быстрее.</p> <pre class="prettyprint linenums">func generateRandomUniqueNumbers3(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] { guard iterations <= (upper - lower) else { return [] } var numbers: Set<int> = Set<int>() (0..</int></int></pre><code> <p>Я был уверен, что решение 1 будет увязываться в ситуациях, когда у вас есть 100 номеров на выбор, и вы хотите, чтобы 90 уникальных. К тому времени, когда вы выбираете 80-е число, у вас есть только 20% -ный шанс выбрать тот, который еще не выбран. И он очень сильно масштабируется, если у вас есть 5000 номеров, и вы все еще хотите 90% из них.</p> <p>Я решил, что решение 2 будет лучше справляться с этим, но я не был уверен, какой удар производительности удалит так много значений из большого массива.</p> <p>Я не был уверен, что делать с решением 3. Возможно, где-то посередине была моя догадка.</p> <p>Я установил XCTest для измерения некоторой производительности для обоих алгоритмов в разных условиях нагрузки. Было 2 параметра: популяция и плотность. Население - это общее количество чисел на выбор, а плотность - это процентная доля населения, которую мы хотели вытащить (т.е. Население 80 означает 80 номеров на выбор, а плотность 50% означает, что мы хотим выбрать 40 уникальных чисел случайным образом из популяции 80).</p> <p>Я провел 9 тестов для каждой комбинации из 3 разных популяций (5, 250 и 12 500) и значений плотности (10%, 50% и 90%). В зависимости от того, насколько быстро или медленно тест был закончен, я скорректировал количество итераций теста, который я выполнил (варьировался от одного прохода до 2500 проходов).</p> <p>Это были результаты:</p> <h2> Решение 1</h2> <pre class="prettyprint linenums">(Population: 5; Density: 10%; Iterations: 2,500): 0.0056s (Population: 250; Density: 10%; Iterations: 50) : 0.0046s (Population: 12,500; Density: 10%; Iterations: 10) : 1.33s (Population: 5; Density: 50%; Iterations: 2,500): 0.0131s (Population: 250; Density: 50%; Iterations: 50) : 0.0912s (Population: 12,500; Density: 50%; Iterations: 1) : 4.09s (Population: 5; Density: 90%; Iterations: 2,500): 0.0309s (Population: 250; Density: 90%; Iterations: 10) : 0.0993s (Population: 12,500; Density: 90%; Iterations: 1) : 23s </pre> <h2> Решение 2</h2> <pre class="prettyprint linenums">(Population: 5; Density: 10%; Iterations: 2,500): 0.0184s (Population: 250; Density: 10%; Iterations: 50) : 0.0086s (Population: 12,500; Density: 10%; Iterations: 10) : 0.103s (Population: 5; Density: 50%; Iterations: 2,500): 0.0233s (Population: 250; Density: 50%; Iterations: 50) : 0.0125s (Population: 12,500; Density: 50%; Iterations: 1) : 0.0209s (Population: 5; Density: 90%; Iterations: 2,500): 0.0242s (Population: 250; Density: 90%; Iterations: 10) : 0.0046s (Population: 12,500; Density: 90%; Iterations: 1) : 0.0278s </pre> <h2> Решение 3</h2> <pre class="prettyprint linenums">(Population: 5; Density: 10%; Iterations: 2,500): 0.00672s (Population: 250; Density: 10%; Iterations: 50) : 0.0024s (Population: 12,500; Density: 10%; Iterations: 10) : 0.0148s (Population: 5; Density: 50%; Iterations: 2,500): 0.0134s (Population: 250; Density: 50%; Iterations: 50) : 0.00769s (Population: 12,500; Density: 50%; Iterations: 1) : 0.00789s (Population: 5; Density: 90%; Iterations: 2,500): 0.0209s (Population: 250; Density: 90%; Iterations: 10) : 0.00397s (Population: 12,500; Density: 90%; Iterations: 1) : 0.0163s </pre> <h2> Сравнение</h2> <pre class="prettyprint linenums">(Case 1): Solution 1 is fastest; then 3; then 2 (Case 2): Solution 3 is fastest; then 1; then 2 (Case 3): Solution 3 is fastest; then 2; then 3 (Case 4): Solution 1 is fastest; then 3; then 2 (Case 5): Solution 3 is fastest; then 2; then 1 (Case 6): Solution 3 is fastest; then 2; then 1 (Case 7): Solution 3 is fastest; then 2; then 1 (Case 8): Solution 3 is fastest; then 2; then 1 (Case 9): Solution 3 is fastest; then 2; then 1 </pre> <h2> Заключение</h2> <p>Как я подозревал в первом решении, он действительно увяз с большой популяцией и высокой плотностью. Это все еще достаточно быстро, когда у вас нет такой большой численности населения или когда вы выбираете только 2 числа, но все решения были довольно быстрыми в целом в этих условиях. Даже если бы это было так, что решение 1 могло выбрать 25 случайных чисел из населения в 250 раз быстрее, чем решение 2 или 3, разница в реальном времени была довольно маленькой.</p> <p>Однако полезно отметить, что если вам нужно очень мало уникальных чисел из действительно большой совокупности (т.е. 2 уникальных номера из пула из 12 500), решение 1 является самым быстрым, примерно на 77% быстрее, чем решение 3, и оба уровня на порядок быстрее, чем решение 2. В моем конкретном случае это ближе к тому, что я буду делать почти все время, поэтому я, вероятно, сделаю определенную функцию, которая использует решение 1 для конкретного выбора 2 уникальных номеров из большого пула данных.</p> <p>В целом решение 3 довольно близко к универсальному алгоритму. Но с большими наборами данных рассмотрите каждое из этих решений на основе того, что вы планируете использовать для них.</p>


Вот мое решение. SwiftStub:

extension Array {
 func shuffle() -> Array<element> {
 var newArray = self
 for i in 0..<newarray.count {="" let="" j="Int(arc4random_uniform(******(newArray.count)))" guard="" i="" !="j" else="" continue="" }="" swap(&newarray[i],="" &newarray[j])="" return="" newarray="" func="" uniquerandoms(count:="" int,="" inrange="" range:="" range<int="">, blacklist: [Int] = []) -> [Int] {
 var r = [Int](range)
 .filter{ !blacklist.contains($0) }
 .shuffle()
 return Array(r[0..</newarray.count></element>
<p> <code>filter отфильтровывает номера в черном списке.

shuffle - это расширение, добавленное к классу Array. Вы реализуете его как отдельную функцию, если хотите.

return Array(r[0..<count])< code=""> создает новый массив из <code>Slice существующего массива.

<p>У этого есть потенциальный индекс из связанной ошибки, когда список меньше, чем запрос <code>count. Например, это приведет к сбою:

let a = uniqueRandoms(10, inRange: 1...5)
let b = uniqueRandoms(3, inRange: 1...5, blacklist: [1,2,3,4])

Обработка, которая остается как упражнение для OP.


// 1st version where I only blacklisted 8
var randomNumbers = [Int]()
for _ in 1...7 {
 var number = Int(arc4random_uniform(8))+1
 while randomNumbers.contains(number) || number == 8{
 number = Int(arc4random_uniform(8))+1
 }
 randomNumbers.append(number)
}
print(randomNumbers)
// 2nd version where I created an array of blacklisted numbers
var randomNumbers = [Int]()
var blackList = [8, 5, 2, 7]
for _ in 1...3 {
 var number = Int(arc4random_uniform(10))+1
 while randomNumbers.contains(number) || blackList.contains(number){
 number = Int(arc4random_uniform(10))+1
 }
 randomNumbers.append(number)
}
print(randomNumbers)

Я создал 2 пустых массива "randomNumbers" и "blackList", затем установил оператор for for. В инструкции цикла я инициализирую переменную "число" . Я назначаю "число" случайному числу, затем я использую оператор while и .contians, чтобы проверить, находится ли "число" уже в массиве "randomNumbers" или если "number" находится в массиве "blackList", если какой-либо массив содержит "number" , "number" присваивается, пока ни один массив не содержит "число" . Затем я randomNumbers.append(число) добавляет "число" в "randomNumbers" , затем цикл начинается снова.


так легко:

let UniqueIdNumber = CFUUIDCreateString(nil, CFUUIDCreate(nil))

licensed under cc by-sa 3.0 with attribution.