Mixing
Blind Random Sort
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
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 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
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.
code-challenge random sorting
asked 1 hour ago
isaacg
34.4k553185
add a comment |Â
up vote
3
down vote
favorite
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 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
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.
code-challenge random sorting
asked 1 hour ago
isaacg
34.4k553185
If we can't maintain a mutable state, then is the submission just based on whatever distribution we implement?
– Jo King
56 mins ago
@JoKing Indeed - your submission is a distribution
– isaacg
53 mins ago
1
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.
– Nathan Merrill
49 mins ago
@NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem.
– Anders Kaseorg
43 mins ago
1
Isn't finding efficient sorting networks of a large size a really hard problem? As long as N > 20, I don't see that being an issue.
– Nathan Merrill
37 mins ago
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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 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
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.
code-challenge random sorting
asked 1 hour ago
isaacg
34.4k553185
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 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
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.
code-challenge random sorting
code-challenge random sorting
asked 1 hour ago
isaacg
34.4k553185
asked 1 hour ago
isaacg
34.4k553185
asked 1 hour ago
isaacg
34.4k553185
asked 1 hour ago
isaacg
34.4k553185
asked 1 hour ago
isaacg
34.4k553185
34.4k553185
If we can't maintain a mutable state, then is the submission just based on whatever distribution we implement?
– Jo King
56 mins ago
@JoKing Indeed - your submission is a distribution
– isaacg
53 mins ago
1
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.
– Nathan Merrill
49 mins ago
@NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem.
– Anders Kaseorg
43 mins ago
1
Isn't finding efficient sorting networks of a large size a really hard problem? As long as N > 20, I don't see that being an issue.
– Nathan Merrill
37 mins ago
add a comment |Â
If we can't maintain a mutable state, then is the submission just based on whatever distribution we implement?
– Jo King
56 mins ago
@JoKing Indeed - your submission is a distribution
– isaacg
53 mins ago
1
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.
– Nathan Merrill
49 mins ago
@NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem.
– Anders Kaseorg
43 mins ago
1
Isn't finding efficient sorting networks of a large size a really hard problem? As long as N > 20, I don't see that being an issue.
– Nathan Merrill
37 mins ago
If we can't maintain a mutable state, then is the submission just based on whatever distribution we implement?
– Jo King
56 mins ago
If we can't maintain a mutable state, then is the submission just based on whatever distribution we implement?
– Jo King
56 mins ago
@JoKing Indeed - your submission is a distribution
– isaacg
53 mins ago
@JoKing Indeed - your submission is a distribution
– isaacg
53 mins ago
1
1
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.
– Nathan Merrill
49 mins ago
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.
– Nathan Merrill
49 mins ago
@NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem.
– Anders Kaseorg
43 mins ago
@NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem.
– Anders Kaseorg
43 mins ago
1
1
Isn't finding efficient sorting networks of a large size a really hard problem? As long as N > 20, I don't see that being an issue.
– Nathan Merrill
37 mins ago
Isn't finding efficient sorting networks of a large size a really hard problem? As long as N > 20, I don't see that being an issue.
– Nathan Merrill
37 mins ago
add a comment |Â
3 Answers
3
active
oldest
votes
up vote
2
down vote
Python, score ≈ 10990
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.
answered 37 mins ago
Anders Kaseorg
25.3k14291
add a comment |Â
up vote
1
down vote
Score ~4620
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.
answered 24 mins ago
xnor
87.8k17182433
add a comment |Â
up vote
0
down vote
Score: ~28500?
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.
answered 44 mins ago
Jo King
17.3k24196
add a comment |Â
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Python, score ≈ 10990
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.
answered 37 mins ago
Anders Kaseorg
25.3k14291
add a comment |Â
up vote
2
down vote
Python, score ≈ 10990
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.
answered 37 mins ago
Anders Kaseorg
25.3k14291
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Python, score ≈ 10990
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.
answered 37 mins ago
Anders Kaseorg
25.3k14291
Python, score ≈ 10990
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.
answered 37 mins ago
Anders Kaseorg
25.3k14291
answered 37 mins ago
Anders Kaseorg
25.3k14291
answered 37 mins ago
Anders Kaseorg
25.3k14291
answered 37 mins ago
Anders Kaseorg
25.3k14291
25.3k14291
add a comment |Â
add a comment |Â
up vote
1
down vote
Score ~4620
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.
answered 24 mins ago
xnor
87.8k17182433
add a comment |Â
up vote
1
down vote
Score ~4620
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.
answered 24 mins ago
xnor
87.8k17182433
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Score ~4620
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.
answered 24 mins ago
xnor
87.8k17182433
Score ~4620
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.
answered 24 mins ago
xnor
87.8k17182433
answered 24 mins ago
xnor
87.8k17182433
answered 24 mins ago
xnor
87.8k17182433
answered 24 mins ago
xnor
87.8k17182433
87.8k17182433
add a comment |Â
add a comment |Â
up vote
0
down vote
Score: ~28500?
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.
answered 44 mins ago
Jo King
17.3k24196
add a comment |Â
up vote
0
down vote
Score: ~28500?
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.
answered 44 mins ago
Jo King
17.3k24196
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Score: ~28500?
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.
answered 44 mins ago
Jo King
17.3k24196
Score: ~28500?
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.
answered 44 mins ago
Jo King
17.3k24196
edited 11 mins ago
answered 44 mins ago
Jo King
17.3k24196
answered 44 mins ago
Jo King
17.3k24196
answered 44 mins ago
Jo King
17.3k24196
17.3k24196
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f174162%2fblind-random-sort%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
If we can't maintain a mutable state, then is the submission just based on whatever distribution we implement?
– Jo King
56 mins ago
@JoKing Indeed - your submission is a distribution
– isaacg
53 mins ago
1
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.
– Nathan Merrill
49 mins ago
@NathanMerrill If mutable state were allowed, the winner would just be a sorting network which is already a well studied problem.
– Anders Kaseorg
43 mins ago
1
Isn't finding efficient sorting networks of a large size a really hard problem? As long as N > 20, I don't see that being an issue.
– Nathan Merrill
37 mins ago