Use random.sample
:
>>> random.sample(range(1,61), 6)
[39, 15, 37, 18, 52, 60]
Explanation:
A method that guarantees a fair draw (ie each element has the same chance of being drawn) and without repetition is the generation of a search space permutation - for example by Fisher-Yates algorithm - which removes only the first% of% elements you want.
If your search space is small, the implementation proposed by Luiz Vieira (create a list with all the elements and swapping it) is the simplest and perhaps most efficient way. In your question, the numbers go only from k
to 1
, so this simple solution is the one I would use. If you do not have numpy access, you can also use 60
function:
>>> nums = list(range(1, 61))
>>> random.shuffle(nums)
>>> nums[:6]
[14, 12, 56, 26, 42, 10]
On the other hand, if the search space was too large (eg you want 10 numbers from 1 to 1 billion) this implementation would be impracticable - not so much by the time but by the memory spent on the creation of the list. In this case, an alternative implementation would be:
def random_elements(a_sortear, total):
state = {}
for i in range(a_sortear):
# Troca o state[i] com um elemento aleatório
swap_with = random.randint(i, total - 1)
state[i], state[swap_with] = state.get(swap_with, swap_with), state.get(i, i)
return [state[i]+1 for i in range(a_sortear)]
print (random_elements(10, 1000000000))
Font (adapted)
This is a partial application of the same algorithm:
Instead of the list being created explicitly, it is implied that the index element random.shuffle
has the value i
if it is absent from the set:
state.get(swap_with, swap_with) # O valor padrão, se ausente, é o próprio índice
When two elements are changed (just like the original algorithm), they are explicitly placed in the array:
state[i], state[swap_with] = state.get(swap_with, swap_with), state.get(i, i)
The algorithm to toggle when the desired number of elements has already been obtained:
for i in range(a_sortear): # Não vai até total, mas para em a_sortear
swap_with = random.randint(i, total - 1) # Sorteia de 0 a total-1
...
For the result to go from i
to 1
, instead of N
to 0
, it moves whole set 1 to the right:
return [state[i]+1 for i in range(a_sortear)]
That is, in this implementation both the time and the memory spent are proportional to the number of elements one wants, instead of the total number of elements available to be drawn.
Finally, there is the alternative algorithm in which you simply draw lots of numbers and, if any one comes back, the draw is done again until all the results are different. This method may be even more efficient than the partial Fisher-Yates application when the overall set is too large (since the chance of collision is small). The Answers from Icarus Dantas and do Miguel give examples of implementation.
The use of N-1
- from what I understood from fonts - choose one or another implementation based on what would be most efficient depending on the sizes of the total set and the number of elements to be sorted.