> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/random-set.md).

# Random Set

**17.3 Random Set:** Write a method to randomly generate a set of m integers from an array of size n. Each element must have equal probability of being chosen.

**The Idea:** First lets think of some possible approaches. If n = m, then it is just a shuffle and returning the shuffled array of elements. Otherwise if m < n, we can return \[0-m] needed elements from this array. This would be O(N) time, but highly wasteful if we wanted to chose 1 element from an array of size 1 million.

Instead what we could do is randomly generate an index between `[0 - N]`, append this number to the result array, and then swap the last element with this chosen index in the array. Then our range of next possible elements to chosen from becomes `[0-(N-1)]`. For the next element, repeat the same process as between, but now swap with `N-2`, and so fourth.

**Complexity:** O(n) time where n is the number of elements to generate. O(1) extra space

```python
from random import randrange


def rand_set(nums, n):
    if n > len(nums):
        raise ValueError("Cannot extract that many elements")
    else:
        rand_elements = []
        back_iter = len(nums)
        for i in range(0, n):
            # generate a random index between 0 and the length of the list
            # decrement by 1 every time to ignore elements moved to the back
            rand_i = randrange(0, back_iter)
            rand_n = nums[rand_i]

            # add the result, and move it to the end of the list
            rand_elements.append(rand_n)
            nums[rand_i], nums[back_iter - 1] = nums[back_iter - 1], nums[rand_i]
            back_iter -= 1
        return rand_elements


nums = [0, 3, 6789, 6, 7, 8, 9, 34, 43, 45, 567, 56, 65, 46789, 78, 978, 83, 89, 90, 6878, 7654, 245, 765]
for i in range(0, len(nums)):
    print(rand_set(nums, i))
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/coding_practice_questions/hard/random-set.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.