18
\$\begingroup\$

Here's a pretty common pattern for sorting algorithms:

def sort(l):
    while not is_sorted(l):
         choose indices i, j
         assert i < j
         if l[i] > l[j]:
             l[i], l[j] = l[j], l[i]

These algorithms work well because the indices i and j are chosen carefully, based on the state of the list l.

However, what if we couldn't see l, and just had to choose blindly? How fast could we sort the list then?


Your challenge is to write a function that outputs a random pair of indices, given only the length of l. Specifically, you must output two indices, i, j, with 0 <= i < j < len(l). Your function should work on any length of list, but it will be scored on a list of length 100.

Your score is the mean number of index choices necessary to sort a uniformly randomly shuffled list according to the above pattern, where the indices are chosen according to your function.

I will score submissions, taking the mean number of index choices over 1000 trials on a uniformly randomly shuffled list of length 100 with no repeated entries.

I reserve the right to run less trials if the submission is clearly non-competitive or does not terminate, and I will run more trials to differentiate the top competitors to find a single winner. If multiple top submissions remain within the margin of error at the limit of my computational resources, I will declare the earlier submission the winner, until further computational resources can be brought to bear.


Here's an example scoring program, in Python:

import random
def is_sorted(l):
    for x in range(len(l)-1):
        if l[x] > l[x+1]:
            return False
    return True

def score(length, index_chooser):
    steps = 0
    l = list(range(length))
    random.shuffle(l)

    while not is_sorted(l):
        i, j = index_chooser(length)
        assert (i < j)
        if l[i] > l[j]:
            l[i], l[j] = l[j], l[i]
        steps += 1
    return steps

Your function may not maintain any mutable state, interact with global variables, affect the list l, etc. Your function's only input must be the length of the list l, and it must output a ordered pair of integers in the range [0, len(l)-1] (or appropriate for your language's list indexing). Feel free to ask whether something's allowed in the comments.

Submissions may be in any free-to-use language. Please include a scoring harness if one has not already been posted for your language. You may post a provisional score, but I will leave a comment with the official score.

Scoring is the mean number of steps to a sorted list on a uniformly randomly shuffled list of length 100. Good luck.

\$\endgroup\$
11
  • 2
    \$\begingroup\$ @JoKing Indeed - your submission is a distribution \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 4:03
  • 2
    \$\begingroup\$ Why don't you allow mutable state? Allowing it means that submissions can better fine-tune their algorithms, as opposed to hoping that the right items get picked. \$\endgroup\$ Oct 17, 2018 at 4:07
  • 3
    \$\begingroup\$ @NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem. \$\endgroup\$ Oct 17, 2018 at 4:13
  • 3
    \$\begingroup\$ @NathanMerrill If you want to post that question, feel free. It's not this question, however. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 5:34
  • 3
    \$\begingroup\$ @NathanMerrill Oh, sure. The challenge "Design the best sorting network", while an interesting question, has been studied a lot in the CS research world. As a result, the best submissions would probably just consist of implementations of research papers, such as Batcher's bitonic sort. The question I've asked here is original as far as I know, and so should have more room for innovation. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:31

7 Answers 7

10
\$\begingroup\$

Python, score = 4508

def half_life_3(length):
    h = int(random.uniform(1, (length / 2) ** -3 ** -0.5) ** -3 ** 0.5)
    i = random.randrange(length - h)
    return i, i + h

Half-Life 3 confirmed.

Python, score = 11009

def bubble(length):
    i = random.randrange(length - 1)
    return i, i + 1

Apparently a randomized bubble sort doesn’t do all that much worse than a normal bubble sort.

Optimal distributions for small length

There’s no way this could be extended to length 100, but it’s interesting to look at anyway. I computed optimal distributions for small cases (length ≤ 7) using gradient descent and lots of matrix algebra. The kth column shows the probability of each swap at distance k.

length=1
score=0.0000

length=2
1.0000
score=0.5000

length=3
0.5000 0.0000
0.5000
score=2.8333

length=4
0.2957 0.0368 0.0000 
0.3351 0.0368 
0.2957 
score=7.5106

length=5
0.2019 0.0396 0.0000 0.0000 
0.2279 0.0613 0.0000 
0.2279 0.0396 
0.2019 
score=14.4544

length=6
0.1499 0.0362 0.0000 0.0000 0.0000 
0.1679 0.0558 0.0082 0.0000 
0.1721 0.0558 0.0000 
0.1679 0.0362 
0.1499 
score=23.4838

length=7
0.1168 0.0300 0.0041 0.0000 0.0000 0.0000 
0.1313 0.0443 0.0156 0.0000 0.0000 
0.1355 0.0450 0.0155 0.0000 
0.1355 0.0443 0.0041 
0.1313 0.0300 
0.1168 
score=34.4257
\$\endgroup\$
5
  • \$\begingroup\$ Your score: 11009 \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:13
  • 2
    \$\begingroup\$ Can you explain your half life 3 answer a bit? Is the point just to bias the random number towards the front of the list? \$\endgroup\$
    – Max
    Oct 17, 2018 at 16:04
  • 1
    \$\begingroup\$ The optimal distributions for small length are very interesting - I notice that biasing towards the center is useful, especially for larger swap distance. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 17:02
  • \$\begingroup\$ @Max The entire problem is about biasing the random numbers in useful ways; this way happened to be useful. Note that h is the distance between the swapped elements; it doesn’t represent the front or the back. \$\endgroup\$ Oct 17, 2018 at 23:18
  • 1
    \$\begingroup\$ Your half life score: 4508 on 10000 samples. \$\endgroup\$
    – isaacg
    Oct 18, 2018 at 0:19
7
\$\begingroup\$

Score: 4627

def rand_step(n):
	step_size = random.choice([1, 1, 4, 16])
	
	if step_size > n - 1:
		step_size = 1 
	
	start = random.randint(0, n - step_size - 1)
	return (start, start + step_size)

Try it online!

Outputs random indices whose distance apart is chosen uniformly from [1,1,4,16]. The idea is to have a mix of 1-step swaps with swaps at larger scales.

I hand-tweaked these values for lists of length 100, and they are likely far from optimal. Some machine search could probably optimize the distribution over distances for the random-pair-with-chosen-distance strategy.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Your score: 4627 on 10,000 samples. I'll run it again with more samples if you're among the leaders after a few days. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:14
3
\$\begingroup\$

Score: 28493

def x_and_y(l):
    x = random.choice(range(l))
    y = random.choice(range(l))
    while y == x and l != 1: y = random.choice(range(l))
    return sorted([x,y])

Try it online!

This solution just selects distinct values for x and y randomly from the range and returns them in sorted order. As far as I can tell, this performs better than choosing x then choosing y from the remaining values.

\$\endgroup\$
1
  • \$\begingroup\$ Your score: 28493 \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:13
3
\$\begingroup\$

Python, score: 39525

def get_indices(l):
    x = random.choice(range(l-1))
    y = random.choice(range(x+1,l))
    return [x,y]

First it chooses a random value in the range \$[0, l-1)\$ for the \$x\$-index.
After that it will choose another random value larger than \$x\$ in the range \$[x+1, l)\$ for the \$y\$-index.

Try it online.

\$\endgroup\$
1
  • \$\begingroup\$ Your score: 39525 \$\endgroup\$
    – isaacg
    Oct 18, 2018 at 0:18
2
\$\begingroup\$

Python, score ≈ 5000

def exponentialDistance(n):
    epsilon = 0.25
    for dist in range(1, n):
        if random.random() < epsilon:
            break
    else:
        dist = 1
    low = random.randrange(0, n - dist)
    high = low + dist
    return low, high

Tried with a bunch of epsilon values, 0.25 seems to be the best.

Score ≈ 8881

def segmentedShuffle(n):
    segments = 20
    segmentLength = (n - 1) // segments + 1

    if random.random() < 0.75:
        a = b = 0
        while a == b or a >= n or b >= n:
            segment = random.randrange(segments)
            a = random.randrange(segmentLength) + segment * segmentLength
            b = random.randrange(segmentLength) + segment * segmentLength
        return sorted([a, b])

    highSegment = random.randrange(1, segments)
    return highSegment * segmentLength - 1, highSegment * segmentLength

A different approach. Not as good, and it dies horribly with length not divisible by the number of segments, but still fun to build.

\$\endgroup\$
1
  • \$\begingroup\$ Your scores: Exponential distance: 5055. Segmented shuffle: 8901 \$\endgroup\$
    – isaacg
    Oct 18, 2018 at 0:17
1
\$\begingroup\$

Score: 4583

def rand_shell(l):
    steps = [1, 3, 5, 9, 17, 33, 65, 129]
    candidates = [(left, left + step)
            for (step, nstep) in zip(steps, steps[1:])
            for left in range(0, l - step)
            for i in range(nstep // step)
    ]
    return random.choice(candidates)

Try it online!

I've no idea why. I just tried sequences listed on wikipedia artical for shellsort. And this one seem works best. It get similar score with the one xnor posted.

\$\endgroup\$
4
  • \$\begingroup\$ Your score: 4583 on 10,000 samples. I'll run it again with more samples if you're among the leaders in a few days. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:14
  • \$\begingroup\$ Also, I'm running a faster program that samples the same distribution, so I can get more samples. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:18
  • 2
    \$\begingroup\$ @isaacg For better testing performance, moving candidates out of the function as a global variable should work. \$\endgroup\$
    – tsh
    Oct 17, 2018 at 6:21
  • 1
    \$\begingroup\$ Thanks, that's much faster than what I was doing. \$\endgroup\$
    – isaacg
    Oct 17, 2018 at 6:26
1
\$\begingroup\$

Python 2, 4871

import random
def index_chooser(length):
    e= random.choice([int(length/i) for i in range(4,length*3/4)])
    s =random.choice(range(length-e))
    return [s,s+e]
def score(length, index_chooser):
    steps = 0
    l = list(range(length))
    random.shuffle(l)
    while True:
        for x in range(length-1):
            if l[x] > l[x+1]:
                break
        else:
            return steps
        i, j = index_chooser(length)
        assert(i < j)
        if l[i] > l[j]:
            l[i], l[j] = l[j], l[i]
        steps += 1

print sum([score(100, index_chooser) for t in range(100)])

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Your score: 4871 on 10000 samples \$\endgroup\$
    – isaacg
    Oct 18, 2018 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.