Can this algorithm be optimised?

Question

I have a list of some objects and I want to iterate through them in a specific sequence for a particular number as returned by the following function. What the following does is, removes each number based on the modulo of the hash number to the list size 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

Eg: genSeq(53,5) will return [3, 1, 4, 2, 0]

I am presenting the algo in python for easy understanding. I am supposed to code in c++. The complexity in this form in O(n^2) both for vector and list. (we either pay for removing or for access). Can this be made any better ?

Using an appropriate datastructure for your `l` theoretically a `log n` performance is possible which would then be `n log n` in total. Nevertheless I doubt that this performance gain is big unless your `n` is really large. — Howard, Dec 29 '11 at 16:04

score 1 · Accepted Answer · answered Dec 29 '11 at 16:50

1

A skip list would give you O(log n) access and removal. So your total traversal time would be O(n log n).

I'd like to think there is a linear solution, but nothing jumps out at me.

answered Dec 29 '11 at 16:50

Jim Mischel

131,090
20
188
351

score 0 · Answer 2 · edited May 23 '17 at 12:29

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

The mapping from factoradic numbers to permutations is described in the top answer under the section "Permuting a list using an index sequence". Unfortunately the algorithm provided is quadratic. However there is a commenter which points to a data-structure which would make the algorithm O(nlog(n)).

score -1 · Answer 3 · answered Dec 29 '11 at 19:10

-1

You should not delete from your vector, but swap with the end and decrease a fill pointer. Think about the Fisher-Yates shuffle.

answered Dec 29 '11 at 19:10

Svante

50,694
11
78
122

That's not going to work because it will change the order of items. You wouldn't get the same order as if you used his algorithm. – Jim Mischel Dec 29 '11 at 19:42

Can this algorithm be optimised?

3 Answers3