jeudi 28 mai 2020

Randomly Consuming a Set of Elements Indexed From 1 to N

In this problem, I have a set of elements that are indexed from 1 to n. Each element actually corresponds to a graph node and I am trying to calculate random one-to-one matchings between the nodes. For the sake of simplicity, I neglect further details of the actual problem. I need to write a fast algorithm to randomly consume these elements (nodes) and do this operation multiple times in order to calculate different matchings. The purpose here is to create randomized inputs to another algorithm and each calculated matching at the end of this will be another input to that algorithm.

The most basic algorithm I can think of is to create copies of the elements in the form of an array, generate random integers, and use them as array indices to apply swap operations. This way each random copy can be created in O(n) but in practice, it uses a lot of copy and swap operations. Performance is very important and I am looking for faster ways (algorithms and data structures) of achieving this goal. It just needs to satisfy the two conditions:

  1. It shall be able to consume a random element.
  2. It shall be able to consume an element on the given index.

I tried to write as clear as possible. If you have any questions, feel free to ask and I am happy to clarify. Thanks in advance.

Note: Matching is an operation where you pair the vertices on a graph if there exists an edge between them.




Aucun commentaire:

Enregistrer un commentaire