Can this algorithm be optimized?

Question

I have a list of some objects and I want to iterate over them in a specific sequence for a specific number returned by the next function. Which does the following: removes each number based on the hash number module by the size of the list and generates a sequence.

def genSeq(hash,n): l = range(n) seq = [] while l: ind = hash % len(l) seq.append(l[ind]) del l[ind] return seq 

For example: genSeq (53.5) will return [3, 1, 4, 2, 0]

I introduce algo in python for easy understanding. I have to write C ++ code. The complexity in this form is in O (n ^ 2) for both the vector and the list. (we either pay for deletion or for access). Can this be done better?

Answer 1

A skip list will give you O(log n) access and deletion. So your total travel time will be O(n log n) .

I would like to think that there is a linear solution, but nothing jumps at me.

Answer 2

The sequence [hash% (i + 1) in the range (len (l))] can be considered as a number in factoradic . There is a bijection between permutations and factor numbers.

The mapping from factorial numbers to permutations is described in the upper answer in the section "Transferring a List Using an Index Sequence". Unfortunately, the proposed algorithm is quadratic. However, there is a commenter that points to a data structure that would make the O (nlog (n)) algorithm.

Answer 3

You should not remove from your vector, but exchange with the end and decrease the fill pointer. Think of a Fisher-Yate shuffle.