Aquí hay un patrón bastante común para los algoritmos de clasificación:

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]

Estos algoritmos funcionan bien porque los índices iy jse eligen cuidadosamente, en función del estado de la lista l.

Sin embargo, ¿qué pasaría si no pudiéramos ver ly solo tuviéramos que elegir a ciegas? ¿Qué tan rápido podríamos ordenar la lista entonces?

Su desafío es escribir una función que genere un par aleatorio de índices, dada solo la longitud de l. Específicamente, debe generar dos índices i, j, con 0 <= i < j < len(l). Su función debería funcionar en cualquier longitud de la lista, pero se puntuará en una lista de longitud 100.

Su puntaje es el número medio de opciones de índice necesarias para ordenar una lista aleatoria uniforme de manera aleatoria de acuerdo con el patrón anterior, donde los índices se eligen de acuerdo con su función.

Calificaré las presentaciones, tomando el número medio de opciones de índice de más de 1000 ensayos en una lista aleatoria uniformemente aleatoria de longitud 100 sin entradas repetidas.

Me reservo el derecho de realizar menos pruebas si la presentación es claramente no competitiva o no finaliza, y realizaré más pruebas para diferenciar a los principales competidores para encontrar un único ganador. Si varias presentaciones principales permanecen dentro del margen de error en el límite de mis recursos computacionales, declararé la presentación anterior como ganadora, hasta que se puedan obtener más recursos computacionales.

Aquí hay un ejemplo de programa de puntuación, en 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

Es posible que su función no mantenga ningún estado mutable, interactúe con variables globales, afecte la lista l, etc. La única entrada de su función debe ser la longitud de la lista ly debe generar un par ordenado de enteros en el rango [0, len(l)-1](o apropiado para el idioma de su idioma). lista de indexación). No dude en preguntar si hay algo permitido en los comentarios.

Los envíos pueden estar en cualquier idioma de uso gratuito. Incluya un arnés de puntuación si aún no ha publicado uno para su idioma. Puede publicar un puntaje provisional, pero dejaré un comentario con el puntaje oficial.

La puntuación es el número medio de pasos para una lista ordenada en una lista aleatoriamente uniforme de longitud 100. Buena suerte.

Python, puntuación = 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 confirmado.

Python, puntaje = 11009

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

Aparentemente, un tipo de burbuja aleatorio no hace mucho peor que un tipo de burbuja normal.

Distribuciones óptimas para longitud pequeña.

No hay forma de que esto se pueda extender a la longitud 100, pero es interesante mirar de todos modos. Calculé distribuciones óptimas para casos pequeños (longitud ≤ 7) usando el descenso de gradiente y mucho álgebra matricial. La columna k muestra la probabilidad de cada intercambio a la distancia 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

Puntuación: 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)

Pruébalo en línea!

Emite índices aleatorios cuya distancia se elige de manera uniforme [1,1,4,16]. La idea es tener una combinación de intercambios de 1 paso con intercambios a escalas más grandes.

Ajusté manualmente estos valores para listas de longitud 100, y es probable que estén lejos de ser óptimos. Algunas búsquedas automáticas probablemente podrían optimizar la distribución por distancias para la estrategia de pares aleatorios con la distancia elegida.

Puntuación: 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])

Pruébalo en línea!

Esta solución solo selecciona valores distintos xy yaleatoriamente del rango y los devuelve en orden ordenado. Por lo que puedo decir, esto funciona mejor que elegir y xluego elegir yentre los valores restantes.

Python, puntuación: 39525

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

$[0, l-1)$$x$
$x$$[x+1, l)$$y$

Pruébalo en línea.

Python, puntuación ≈ 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

Probado con un montón de valores de épsilon, 0.25 parece ser el mejor.

Puntuación ≈ 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

Un enfoque diferente. No es tan bueno, y muere horriblemente con una longitud no divisible por el número de segmentos, pero aún así es divertido de construir.

Puntuación: 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)

Pruébalo en línea!

No tengo idea de por qué. Acabo de probar las secuencias enumeradas en wikipedia artical para shellsort . Y este parece funcionar mejor. Obtiene una puntuación similar con la publicada por xnor .

Pitón 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)])

Pruébalo en línea!