algorithm - pseudocodigo - operaciones con listas enlazadas

Algoritmo para barajar una lista enlazada en n registro n tiempo

Question

Estoy tratando de barajar una lista enlazada usando un algoritmo de dividir y vencer que aleatoriamente baraja una lista enlazada en tiempo linealitmico (n log n) y espacio logaritmico (log n) extra.

Soy consciente de que puedo hacer una mezcla de Knuth similar a la que se podría usar en una simple serie de valores, pero no estoy seguro de cómo haría esto con dividir y conquistar. Lo que quiero decir es, ¿qué estoy dividiendo realmente? ¿Simplemente divido a cada nodo individual en la lista y luego vuelvo a reunir la lista de forma aleatoria usando algún valor aleatorio?

¿O le doy a cada nodo un número aleatorio y luego hago una combinación en los nodos en función de los números aleatorios?

Answer 1

Código

Enfoque al azar

Esta versión (lua) se ha mejorado de la respuesta de foxcub para eliminar la necesidad de nodos ficticios.

Para simplificar ligeramente el código en esta respuesta, esta versión supone que sus listas conocen sus tamaños. En caso de que no lo hagan, siempre puede encontrarlo en O(n) , pero aún mejor: se puede hacer una adaptación sencilla en el código para no requerir que se realice un cálculo previo (como subdividir uno sobre dos en lugar de primero). y segunda mitad).

function listUpShuffle (l)
local lsz = #l
if lsz <= 1 then return l end
local lsz2 = math.floor(lsz/2)
local l1, l2 = {}, {}
for k = 1, lsz2 do l1[#l1+1] = l[k] end
for k = lsz2+1, lsz do l2[#l2+1] = l[k] end
l1 = listUpShuffle(l1)
l2 = listUpShuffle(l2)
local res = {}
local i, j = 1, 1
while i <= #l1 or j <= #l2 do
local rem1, rem2 = #l1-i+1, #l2-j+1
if math.random() < rem1/(rem1+rem2) then
res[#res+1] = l1[i]
i = i+1
else
res[#res+1] = l2[j]
j = j+1
end
end
return res
end

Para evitar el uso de nodos ficticios, debe compensar el hecho de que las dos listas intermedias pueden tener diferentes longitudes variando la probabilidad de elegir en cada lista. Esto se hace probando un [0,1] número aleatorio uniforme contra la proporción de nodos seleccionados de la primera lista sobre el número total de nodos seleccionados (en las dos listas).

Abajo shuffle enfoque

También puede barajar mientras subdivide recursivamente, lo que en mis humildes pruebas mostró un rendimiento ligeramente mejor (pero de manera constante). Puede provenir de menos instrucciones o, por otra parte, puede haber aparecido debido al calentamiento de la memoria caché en luajit, por lo que tendrá que hacer un perfil de sus casos de uso.

function listDownShuffle (l)
local lsz = #l
if lsz <= 1 then return l end
local lsz2 = math.floor(lsz/2)
local l1, l2 = {}, {}
for i = 1, lsz do
local rem1, rem2 = lsz2-#l1, lsz-lsz2-#l2
if math.random() < rem1/(rem1+rem2) then
l1[#l1+1] = l[i]
else
l2[#l2+1] = l[i]
end
end
l1 = listDownShuffle(l1)
l2 = listDownShuffle(l2)
local res = {}
for i = 1, #l1 do res[#res+1] = l1[i] end
for i = 1, #l2 do res[#res+1] = l2[i] end
return res
end

Pruebas

La fuente completa está en mi listShuffle.lua Gist .

Contiene un código que, cuando se ejecuta, imprime una matriz que representa, para cada elemento de la lista de entrada, el número de veces que aparece en cada posición de la lista de salida, después de un número específico de ejecuciones. Una matriz bastante uniforme ''muestra'' la uniformidad de la distribución de caracteres, de ahí la uniformidad de la baraja.

Aquí hay un ejemplo de ejecución con 1000000 iteraciones usando una lista de 3 elementos (sin poder de dos):

>> luajit listShuffle.lua 1000000 3
Up shuffle bias matrix:
333331 332782 333887
333377 333655 332968
333292 333563 333145
Down shuffle bias matrix:
333120 333521 333359
333435 333088 333477
333445 333391 333164

Answer 2

¿Qué pasa con lo siguiente? Realice el mismo procedimiento que la ordenación por fusión. Al fusionar, en lugar de seleccionar un elemento (uno por uno) de las dos listas en orden ordenado, lanza una moneda. Elija si desea elegir un elemento de la primera o de la segunda lista en función del resultado del lanzamiento de la moneda.

Algoritmo.

shuffle(list):
if list contains a single element
return list
list1,list2 = [],[]
while list not empty:
move front element from list to list1
if list not empty: move front element from list to list2
shuffle(list1)
shuffle(list2)
if length(list2) < length(list1):
i = pick a number uniformly at random in [0..length(list2)]
insert a dummy node into list2 at location i
# merge
while list1 and list2 are not empty:
if coin flip is Heads:
move front element from list1 to list
else:
move front element from list2 to list
if list1 not empty: append list1 to list
if list2 not empty: append list2 to list
remove the dummy node from list

El punto clave para el espacio es que dividir la lista en dos no requiere ningún espacio adicional. El único espacio adicional que necesitamos es mantener los elementos de registro n en la pila durante la recursión.

El punto con el nodo ficticio es darse cuenta de que insertar y quitar un elemento ficticio mantiene la distribución uniforme de los elementos.

Análisis. ¿Por qué la distribución es uniforme? Después de la combinación final, la probabilidad P_i(n) de cualquier número dado que termine en la posición i es la siguiente. O bien fue:

• en el i -ésimo lugar en su propia lista, y la lista ganó el lanzamiento de la moneda las primeras i veces, la probabilidad de esto es 1/2^i ;
• en el primer lugar de i-1 en su propia lista, y la lista ganó el lanzamiento de la moneda i-1 veces, incluida la última y perdida una vez, la probabilidad de esto es (i-1) choose 1 veces 1/2^i ;
• en el lugar i-2 -nd en su propia lista, y la lista ganó el lanzamiento de la moneda i-2 veces, incluida la última y perdida dos veces, la probabilidad de esto es (i-1) choose 2 veces 1/2^i ;
• y así.

Entonces la probabilidad

P_i(n) = /sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * P_j(n/2).

Inductivamente, puedes mostrar que P_i(n) = 1/n . Le dejo verificar el caso base y asumo que P_j(n/2) = 2/n . El término /sum_{j=0}^{i-1} (i-1 choose j) es exactamente el número de números binarios de i-1 bit, es decir, 2^{i-1} . Así obtenemos

P_i(n) = /sum_{j=0}^{i-1} (i-1 choose j) * 1/2^i * 2/n
= 2/n * 1/2^i * /sum_{j=0}^{i-1} (i-1 choose j)
= 1/n * 1/2^{i-1} * 2^{i-1}
= 1/n

Espero que esto tenga sentido. El único supuesto que necesitamos es que n es par, y que las dos listas se barajan uniformemente. Esto se logra agregando (y luego eliminando) el nodo ficticio.

PD: Mi intuición original no era ni mucho menos rigurosa, pero la menciono por si acaso. Imagina que asignamos números entre 1 y n al azar a los elementos de la lista. Y ahora ejecutamos una clasificación de fusión con respecto a estos números. En cualquier paso de la fusión, debe decidir cuál de los jefes de las dos listas es más pequeño. Pero la probabilidad de que uno sea mayor que el otro debería ser exactamente 1/2, por lo que podemos simular esto lanzando una moneda.

PPS ¿Hay una manera de incrustar LaTeX aquí?

Answer 3

Aquí hay una posible solución:

#include <stdlib.h>
typedef struct node_s {
struct node_s * next;
int data;
} node_s, *node_p;
void shuffle_helper( node_p first, node_p last ) {
static const int half = RAND_MAX / 2;
while( (first != last) && (first->next != last) ) {
node_p firsts[2] = {0, 0};
node_p *lasts[2] = {0, 0};
int counts[2] = {0, 0}, lesser;
while( first != last ) {
int choice = (rand() <= half);
node_p next = first->next;
first->next = firsts[choice];
if( !lasts[choice] ) lasts[choice] = &(first->next);
++counts[choice];
first = next;
}
lesser = (counts[0] < counts[1]);
if( !counts[lesser] ) {
first = firsts[!lesser];
*(lasts[!lesser]) = last;
continue;
}
*(lasts[0]) = firsts[1];
*(lasts[1]) = last;
shuffle_helper( firsts[lesser], firsts[!lesser] );
first = firsts[!lesser];
last = *(lasts[!lesser]);
}
}
void shuffle_list( node_p thelist ) { shuffle_helper( thelist, NULL ); }

Esto es básicamente de orden rápida, pero sin pivote, y con partición aleatoria.

El bucle while externo reemplaza una llamada recursiva.

El bucle while interno mueve aleatoriamente cada elemento en uno de dos sublistas.

Después del bucle while interno, conectamos las sublistas entre sí.

Luego, nos ocupamos de la sublista más pequeña y hacemos un bucle de la sublista más pequeña.

Dado que la lista secundaria más pequeña nunca puede tener más de la mitad del tamaño de la lista inicial, la peor de las recursiones es la base de registro dos del número de elementos. La cantidad de memoria necesaria es O (1) veces la profundidad de la recursión.

El tiempo de ejecución promedio, y el número de llamadas a rand() es O (N log N).

Un análisis más preciso del tiempo de ejecución requiere una comprensión de la frase "casi con seguridad".

Answer 4

De abajo hacia arriba fusionar orden sin comparaciones. Mientras que la fusión no hace ninguna comparación, simplemente intercambie los elementos.

Answer 5

Realmente puedes hacerlo mejor que eso: el mejor algoritmo de selección aleatoria es O (n log n) tiempo y solo O (1) espacio . (También puede barajar en tiempo O (n) y espacio O (n) construyendo una matriz de punteros para la lista, mezclándola en su lugar utilizando Knuth y volviendo a enhebrar la lista en consecuencia).

Prueba de complejidad

Para ver por qué el tiempo O (n log n) es mínimo para el espacio O (1), observe que:

• Con el espacio O (1), la actualización del sucesor de un elemento de lista arbitrario lleva necesariamente O (n) tiempo.
• Wlog, puede suponer que siempre que actualice un elemento, también actualice todos los demás elementos (dejándolos sin cambios si lo desea), ya que esto también lleva solo O (n).
• Con O (1) espacio, hay como máximo O (1) elementos para elegir para el sucesor de cualquier elemento que esté actualizando (los elementos específicos que dependerán obviamente del algoritmo).
• Por lo tanto, una sola actualización O (n) en el tiempo de todos los elementos podría dar como resultado, como máximo, diferentes permutaciones de lista.
• Ya que hay n! = O (n ^ n) = O (c ^ (n log n)) posibles permutaciones de la lista, necesita al menos O (log n) actualizaciones.

Estructura de datos de listas enlazadas (porque Python)

import collections
class Cons(collections.Sequence):
def __init__(self, head, tail=None):
self.head = head
self.tail = tail
def __getitem__(self, index):
current, n = self, index
while n > 0:
if isinstance(current, Cons):
current, n = current.tail, n - 1
else:
raise ValueError("Out of bounds index [{0}]".format(index))
return current
def __len__(self):
current, length = self, 0
while isinstance(current, Cons):
current, length = current.tail, length + 1
return length
def __repr__(self):
current, rep = self, []
while isinstance(current, Cons):
rep.extend((str(current.head), "::"))
current = current.tail
rep.append(str(current))
return "".join(rep)

Algoritmo de fusión de estilo

Aquí hay un tiempo O (n log n) y un algoritmo de espacio O (1) basado en la ordenación de combinación iterativa. La idea básica es simple: barajar la mitad izquierda, luego la mitad derecha, luego fusionarlas seleccionando al azar de las dos listas. Dos cosas que vale la pena señalar:

1. Al hacer que el algoritmo sea iterativo en lugar de recursivo, y devolver un puntero al último elemento al final de cada paso de fusión, reducimos el requisito de espacio a O (1) mientras mantenemos el costo mínimo.
2. Para asegurarnos de que todas las posibilidades son igualmente probables para todos los tamaños de entrada, utilizamos las probabilidades del modelo de Gilbert – Shannon – Reeds al azar al fusionar (consulte http://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model ).

import random
def riffle_lists(head, list1, len1, list2, len2):
"""Riffle shuffle two sublists in place. Returns the new last element."""
for _ in range(len1 + len2):
if random.random() < (len1 / (len1 + len2)):
next, list1, len1 = list1, list1.tail, len1 - 1
else:
next, list2, len2 = list2, list2.tail, len2 - 1
head.tail, head = next, next
head.tail = list2
return head
def shuffle_list(list):
"""Shuffle a list in place using an iterative merge-style algorithm."""
dummy = Cons(None, list)
i, n = 1, len(list)
while (i < n):
head, nleft = dummy, n
while (nleft > i):
head = riffle_lists(head, head[1], i, head[i + 1], min(i, nleft - i))
nleft -= 2 * i
i *= 2
return dummy[1]

Otro algoritmo

Otro interesante algoritmo O (n log n) que produce shuffles no bastante uniformes consiste simplemente en cambiar aleatoriamente la lista 3/2 log_2 (n) veces. Como se describe en http://en.wikipedia.org/wiki/Gilbert%E2%80%93Shannon%E2%80%93Reeds_model , esto deja solo un número constante de bits de información.

Answer 6

Yo diría que la respuesta de foxcub es incorrecta. Para demostrar que introduciré una definición útil para una lista perfectamente mezclada (llámela matriz o secuencia o lo que quiera).

Definición: Supongamos que tenemos una Lista L contiene los elementos a1, a2 ... an y los índices 1, 2, 3..... n . Si exponemos la L a una operación aleatoria (a la que no tenemos acceso), L se baraja perfectamente si y solo si al conocer los índices de algunos elementos k ( k< n ) no podemos deducir los índices de los elementos nk restantes. Es decir, los elementos nk restantes son igualmente probables de revelarse en cualquiera de los índices nk restantes.

Ejemplo: si tenemos una lista de cuatro elementos [a, b, c, d] y después de barajarla, sabemos que su primer elemento es a ( [a, .., .., ..] ) que la probabilidad para cualquier de los elementos b, c, d que se producen en, digamos, la tercera celda es igual a 1/3 .

Ahora, la lista más pequeña para la cual el algoritmo no cumple con la definición tiene tres elementos. Pero el algoritmo lo convierte a una lista de 4 elementos de todos modos, por lo que trataremos de mostrar su error en una lista de 4 elementos.

Considere una entrada L = [a, b, c, d] Después de la primera ejecución del algoritmo, la L se dividirá en l1 = [a, c] y l2 = [b, d] . Después de barajar estos dos sublistas (pero antes de fusionarnos con el resultado de cuatro elementos) podemos obtener cuatro listas de dos elementos igualmente probables:

l1shuffled = [a , c] l2shuffled = [b , d]
l1shuffled = [a , c] l2shuffled = [d , b]
l1shuffled = [c , a] l2shuffled = [b , d]
l1shuffled = [c , a] l2shuffled = [d , b]

Ahora trata de responder dos preguntas.
1. ¿Cuál es la probabilidad de que, después de fusionarse con el resultado final, sea el primer elemento de la lista?
Simplemente, podemos ver que solo dos de los cuatro pares de arriba (de nuevo, igualmente probables) pueden dar tal resultado ( p1 = 1/2 ). Para cada uno de estos pares, las heads deben dibujarse durante el primer giro en la rutina de fusión ( p2 = 1/2 ). Por lo tanto, la probabilidad de tener a como primer elemento de Lshuffled es p = p1*p2 = 1/4 , lo cual es correcto.

2. Sabiendo que a está en la primera posición de Lshuffled , cuál es la probabilidad de tener c (también podríamos elegir b o d sin pérdida de generalidad) en la segunda posición de Lshuffled
Ahora, de acuerdo con la definición anterior de una lista perfectamente mezclada, la respuesta debería ser 1/3 , ya que hay tres números para colocar en las tres celdas restantes de la lista
Vamos a ver si el algoritmo lo asegura.
Después de elegir 1 como el primer elemento de Lshuffled ahora tendríamos:
l1shuffled = [c] l2shuffled = [b, d]
o:
l1shuffled = [c] l2shuffled = [d, b]
La probabilidad de elegir 3 en ambos casos es igual a la probabilidad de voltear las heads ( p3 = 1/2 ), por lo tanto, la probabilidad de tener 3 como el segundo elemento de Lshuffled , al saber que el primer elemento de Lshuffled es 1 es igual a 1/2 . 1/2 != 1/3 que termina la prueba de la incorrecta del algoritmo.

La parte interesante es que el algoritmo cumple la condición necesaria (pero no suficiente) para un orden aleatorio perfecto, a saber:

Dada una lista de n elementos, para cada índice k ( <n ), para cada elemento ak : después de barajar la lista m veces, si hemos contado las veces en que ocurrió ak en el índice k , esta cuenta tenderá a m/n por probabilidad, con m tendiendo al infinito.