Here's one approach:

Use numpy.unique to both sort the array and remove duplicate items. Pass the return_inverse argument to get the indices into the sorted array that give the values of the original array. Then, you can get all of the indices of the tied items by finding the indices of the inverse array whose values are equal to the index into the unique array for that item.

For example:

foo = array([3, 1, 4, 0, 1, 0])
foo_unique, foo_inverse = unique(foo, return_inverse=True)

# Put largest items first
foo_unique = foo_unique[::-1]
foo_inverse = -foo_inverse + len(foo_unique) - 1

foo_top3 = foo_unique[:3]

# Get the indices into foo of the top item
first_indices = (foo_inverse == 0).nonzero()

# Choose one at random
first_random_idx = random.choice(first_indices)

second_indices = (foo_inverse == 1).nonzero()
second_random_idx = random.choice(second_indices)

# And so on...

numpy.unique is implemented using argsort, so a glance at its implementation might suggest a simpler approach.

One trick would be to add uniform noise in [0,1) range and then perform argsort-ing. Adding such a noise forces sorting only within their respective bins and gives randomized sort indices restricted to those bins -

(x+np.random.rand(len(x))).argsort()

What about simply this?

(-foo).argsort(kind='mergesort')[:3]

Why this works:

Argsorting in descending order (not what np.argsort does) is the same as argsorting in ascending order (what np.argsort does) the opposite values. You then just need to pick the first 3 sorted indices. Now all you need is make sure that the sort is stable, meaning in case of ties, keep first index first. NOTE: I thought the default kind=quicksort was stable but from the doc it appears only kind=mergesort is guaranteed to be stable: (https://docs.scipy.org/doc/numpy/reference/generated/numpy.sort.html)

The various sorting algorithms are characterized by their average speed, worst case performance, work space size, and whether they are stable. A stable sort keeps items with the same key in the same relative order. The three available algorithms have the following properties:

kind speed worst case work space stable

‘quicksort’ 1 O(n^2) 0 no

‘mergesort’ 2 O(n*log(n)) ~n/2 yes

‘heapsort’ 3 O(n*log(n)) 0 no

You need to tell argsort to use a stable sorting method.

>>> print(B.argsort(kind='stable')) #trying to sort
[    0     1     2 ... 22997 22998 22999]

According to the documentation

Returns the indices that would sort an array.

• 2 is the index of 0.0.
• 3 is the index of 0.1.
• 1 is the index of 1.41.
• 0 is the index of 1.48.

I understand that you want to rank the elements so that the tiebreaking is random. For this you just need to invert the permutation that you got from lexsort:

output = np.argsort(np.lexsort((rnd_array,a)))

My output (which is not identical to yours because of randomness):

array([ 4,  3,  0,  1, 10,  9,  8,  2,  7,  5,  6, 11])