lundi 28 novembre 2022

Optimized algorithm to generate a series of random numbers without repeats? [duplicate]

I need to implement an algorithm that will generate random numbers, take into account already generated numbers, and discard them.

For example:

  • We have a series of integers from 1 to 10
  • At the first generation of a random number in a given range, we get 3
  • Next, we should get a number from 1 to 2 or from 4 to 10
  • During the second random number generation, we get 7
  • Next, we should get a number from 1 to 2 or from 4 to 6 or from 8 to 10
  • And so on until we have generated all the numbers from the original range

Naive implementation:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

var numbersForRandom []int
var min, max int

func main() {
    // This will show the generation of numbers from 0 to 9 for simplicity
    numbersForRandom = []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
    min, max = 0, len(numbersForRandom)-1

    rand.Seed(time.Now().UnixNano())

    generatedNumbers := make([]int, 0)
    for len(generatedNumbers) < len(numbersForRandom) {
        generatedNumbers = GenerateRandomWithoutRepeats(generatedNumbers)
    }

    fmt.Println(generatedNumbers)
}

func GenerateRandomWithoutRepeats(generatedNumbers []int) []int {
    result := rand.Intn(max-min+1) + min

    for _, i := range generatedNumbers {
        if result == i {
            return generatedNumbers
        }
    }

    return append(generatedNumbers, result)
}

Link to this code on Go Playground: https://go.dev/play/p/wSj6nuOCtBN
Is there an algorithm that optimizes the solution of this problem?




Aucun commentaire:

Enregistrer un commentaire