python - Controlando la distancia de barajar

algorithm python-3.x

Question

He intentado hacer esta pregunta antes , pero nunca he podido expresarlo correctamente. Espero tenerlo bien esta vez:

Tengo una lista de elementos únicos. Quiero barajar esta lista para producir una nueva lista. Sin embargo, me gustaría restringir el orden aleatorio, de modo que la nueva posición de cada elemento esté a lo sumo d alejada de su posición original en la lista.

Así por ejemplo:

L = [1,2,3,4]
d = 2
answer = magicFunction(L, d)

Ahora, un posible resultado podría ser:

>>> print(answer)
[3,1,2,4]

Observe que 3 ha movido dos índices, 1 y 2 ha movido un índice y 4 no se ha movido en absoluto. Por lo tanto, esta es una combinación válida, según mi definición anterior. El siguiente fragmento de código se puede utilizar para validar esto:

old = {e:i for i,e in enumerate(L)}
new = {e:i for i,e in enumerate(answer)}
valid = all(abs(i-new[e])<=d for e,i in old.items())

Ahora, fácilmente podría generar todas las permutaciones posibles de L , filtrar las válidas y elegir una al azar. Pero eso no parece muy elegante. ¿Alguien tiene alguna otra idea sobre cómo lograr esto?

Answer 1

Aquí hay dos bocetos en Python; uno basado en swap, el otro no basado en swap. En la primera, la idea es hacer un seguimiento de dónde se han movido los índices y probar si el próximo intercambio sería válido. Se agrega una variable adicional para el número de swaps a realizar.

from random import randint
def swap(a,b,L):
L[a], L[b] = L[b], L[a]
def magicFunction(L,d,numSwaps):
n = len(L)
new = list(range(0,n))
for i in xrange(0,numSwaps):
x = randint(0,n-1)
y = randint(max(0,x - d),min(n - 1,x + d))
while abs(new[x] - y) > d or abs(new[y] - x) > d:
y = randint(max(0,x - d),min(n - 1,x + d))
swap(x,y,new)
swap(x,y,L)
return L
print(magicFunction([1,2,3,4],2,3)) # [2, 1, 4, 3]
print(magicFunction([1,2,3,4,5,6,7,8,9],2,4)) # [2, 3, 1, 5, 4, 6, 8, 7, 9]

Al usar print(collections.Counter(tuple(magicFunction([0, 1, 2], 1, 1)) for i in xrange(1000))) encontramos que la permutación de la identidad aparece con este código (la razón por la cual es dejado como ejercicio para el lector).

Alternativamente, podemos pensar que se busca una matriz de permutación con restricciones de intervalo, donde abs(i - j) <= d where M(i,j) would equal 1 . Podemos construir una ruta aleatoria única eligiendo una j aleatoria para cada fila de las que aún están disponibles. x en el siguiente ejemplo representan celdas matriciales que invalidan la solución (la diagonal noroeste a sureste representaría la permutación de la identidad), las restrictions representan la cantidad de i aún están disponibles para cada j . (Adaptado de mi versión anterior para elegir aleatoriamente la siguiente i y la siguiente j, inspirado en la respuesta de user2357112):

n = 5, d = 2
Start:
0 0 0 x x
0 0 0 0 x
0 0 0 0 0
x 0 0 0 0
x x 0 0 0
restrictions = [3,4,5,4,3] # how many i''s are still available for each j
1.
0 0 1 x x # random choice
0 0 0 0 x
0 0 0 0 0
x 0 0 0 0
x x 0 0 0
restrictions = [2,3,0,4,3] # update restrictions in the neighborhood of (i ± d)
2.
0 0 1 x x
0 0 0 0 x
0 0 0 0 0
x 0 0 0 0
x x 0 1 0 # random choice
restrictions = [2,3,0,0,2] # update restrictions in the neighborhood of (i ± d)

3.
0 0 1 x x
0 0 0 0 x
0 1 0 0 0 # random choice
x 0 0 0 0
x x 0 1 0
restrictions = [1,0,0,0,2] # update restrictions in the neighborhood of (i ± d)
only one choice for j = 0 so it must be chosen
4.
0 0 1 x x
1 0 0 0 x # dictated choice
0 1 0 0 0
x 0 0 0 0
x x 0 1 0
restrictions = [0,0,0,0,2] # update restrictions in the neighborhood of (i ± d)
Solution:
0 0 1 x x
1 0 0 0 x
0 1 0 0 0
x 0 0 0 1 # dictated choice
x x 0 1 0
[2,0,1,4,3]

Código de Python (adaptado de mi versión anterior para elegir aleatoriamente la siguiente i y la siguiente j , inspirado en la respuesta del usuario2357112):

from random import randint,choice
import collections
def magicFunction(L,d):
n = len(L)
restrictions = [None] * n
restrict = -1
solution = [None] * n
for i in xrange(0,n):
restrictions[i] = abs(max(0,i - d) - min(n - 1,i + d)) + 1
while True:
availableIs = filter(lambda x: solution[x] == None,[i for i in xrange(n)]) if restrict == -1 else filter(lambda x: solution[x] == None,[j for j in xrange(max(0,restrict - d),min(n,restrict + d + 1))])
if not availableIs:
L = [L[i] for i in solution]
return L
i = choice(availableIs)
availableJs = filter(lambda x: restrictions[x] <> 0,[j for j in xrange(max(0,i - d),min(n,i + d + 1))])
nextJ = restrict if restrict != -1 else choice(availableJs)
restrict = -1
solution[i] = nextJ
restrictions[ nextJ ] = 0
for j in xrange(max(0,i - d),min(n,i + d + 1)):
if j == nextJ or restrictions[j] == 0:
continue
restrictions[j] = restrictions[j] - 1
if restrictions[j] == 1:
restrict = j
print(collections.Counter(tuple(magicFunction([0, 1, 2], 1)) for i in xrange(1000)))

Usando print(collections.Counter(tuple(magicFunction([0, 1, 2], 1)) for i in xrange(1000))) encontramos que la permutación de la identidad se print(collections.Counter(tuple(magicFunction([0, 1, 2], 1)) for i in xrange(1000))) con este código (por qué se deja como ejercicio) para el lector).

Answer 2

Aquí hay una adaptación del código de @ גלעד ברקן que toma solo un pase a través de la lista (en orden aleatorio) y cambia solo una vez (usando una elección aleatoria de posiciones posibles):

from random import choice, shuffle
def magicFunction(L, d):
n = len(L)
swapped = [0] * n # 0: position not swapped, 1: position was swapped
positions = list(xrange(0,n)) # list of positions: 0..n-1
shuffle(positions) # randomize positions
for x in positions:
if swapped[x]: # only swap an item once
continue
# find all possible positions to swap
possible = [i for i in xrange(max(0, x - d), min(n, x + d)) if not swapped[i]]
if not possible:
continue
y = choice(possible) # choose another possible position at random
if x != y:
L[y], L[x] = L[x], L[y] # swap with that position
swapped[x] = swapped[y] = 1 # mark both positions as swapped
return L

Aquí hay un refinamiento del código anterior que simplemente encuentra todas las posibles posiciones adyacentes y elige una:

from random import choice
def magicFunction(L, d):
n = len(L)
positions = list(xrange(0, n)) # list of positions: 0..n-1
for x in xrange(0, n):
# find all possible positions to swap
possible = [i for i in xrange(max(0, x - d), min(n, x + d)) if abs(positions[i] - x) <= d]
if not possible:
continue
y = choice(possible) # choose another possible position at random
if x != y:
L[y], L[x] = L[x], L[y] # swap with that position
positions[x] = y
positions[y] = x
return L

Answer 3

En resumen, la lista que se debe barajar se ordena por la suma del índice y un número aleatorio.

import random
xs = range(20) # list that should be shuffled
d = 5 # distance
[x for i,x in sorted(enumerate(xs), key= lambda (i,x): i+(d+1)*random.random())]

Afuera:

[1, 4, 3, 0, 2, 6, 7, 5, 8, 9, 10, 11, 12, 14, 13, 15, 19, 16, 18, 17]

Eso es básicamente eso. Pero esto parece un poco abrumador, por lo tanto ...

El algoritmo en más detalle.

Para comprender mejor esto, considere esta implementación alternativa de una ordenación aleatoria ordinaria:

import random
sorted(range(10), key = lambda x: random.random())

Afuera:

[2, 6, 5, 0, 9, 1, 3, 8, 7, 4]

Para restringir la distancia, tenemos que implementar una función de clave de clasificación alternativa que depende del índice de un elemento. La función sort_criterion es responsable de eso.

import random
def exclusive_uniform(a, b):
"returns a random value in the interval [a, b)"
return a+(b-a)*random.random()
def distance_constrained_shuffle(sequence, distance,
randmoveforward = exclusive_uniform):
def sort_criterion(enumerate_tuple):
"""
returns the index plus a random offset,
such that the result can overtake at most ''distance'' elements
"""
indx, value = enumerate_tuple
return indx + randmoveforward(0, distance+1)
# get enumerated, shuffled list
enumerated_result = sorted(enumerate(sequence), key = sort_criterion)
# remove enumeration
result = [x for i, x in enumerated_result]
return result

Con el argumento randmoveforward puede pasar un generador de números aleatorios con una función de densidad de probabilidad diferente (pdf) para modificar la distribución de la distancia.

El resto es prueba y evaluación de la distribución a distancia.

Función de prueba

Aquí hay una implementación de la función de prueba. La función de validate realidad se toma del OP, pero eliminé la creación de uno de los diccionarios por razones de rendimiento.

def test(num_cases = 10, distance = 3, sequence = range(1000)):
def validate(d, lst, answer):
#old = {e:i for i,e in enumerate(lst)}
new = {e:i for i,e in enumerate(answer)}
return all(abs(i-new[e])<=d for i,e in enumerate(lst))
#return all(abs(i-new[e])<=d for e,i in old.iteritems())
for _ in range(num_cases):
result = distance_constrained_shuffle(sequence, distance)
if not validate(distance, sequence, result):
print "Constraint violated. ", result
break
else:
print "No constraint violations"
test()

Afuera:

No constraint violations

Distribución a distancia

No estoy seguro de si hay una manera de hacer que la distancia sea distribuida uniformemente, pero aquí hay una función para validar la distribución.

def distance_distribution(maxdistance = 3, sequence = range(3000)):
from collections import Counter
def count_distances(lst, answer):
new = {e:i for i,e in enumerate(answer)}
return Counter(i-new[e] for i,e in enumerate(lst))
answer = distance_constrained_shuffle(sequence, maxdistance)
counter = count_distances(sequence, answer)
sequence_length = float(len(sequence))
distances = range(-maxdistance, maxdistance+1)
return distances, [counter[d]/sequence_length for d in distances]
distance_distribution()

Afuera:

([-3, -2, -1, 0, 1, 2, 3],
[0.01,
0.076,
0.22166666666666668,
0.379,
0.22933333333333333,
0.07766666666666666,
0.006333333333333333])

O para un caso con mayor distancia máxima:

distance_distribution(maxdistance=9, sequence=range(100*1000))

Answer 4

Este es un problema muy difícil, pero resulta que hay una solución en la literatura académica, en un artículo influyente de Mark Jerrum, Alistair Sinclair y Eric Vigoda, un algoritmo de aproximación de tiempo polinómico para el permanente de una matriz con entradas no negativas , Diario de la ACM, vol. 51, No. 4, julio de 2004, págs. 671–697. http://www.cc.gatech.edu/~vigoda/Permanent.pdf .

Aquí está la idea general: primero escriba dos copias de los números en la matriz que desea permutar. Decir

1 1
2 2
3 3
4 4

Ahora conecte un nodo de la izquierda a un nodo de la derecha si las restricciones existentes permiten la asignación desde el número de la izquierda a la posición de la derecha. Entonces, si d = 1 entonces 1 a la izquierda se conecta a 1 y 2 a la derecha, 2 a la izquierda se conecta a 1, 2, 3 a la derecha, 3 a la izquierda se conecta a 2, 3, 4 a la derecha y 4 a la izquierda se conecta a 3, 4 a la derecha.

1 - 1
X
2 - 2
X
3 - 3
X
4 - 4

El gráfico resultante es bipartito. Una permutación válida corresponde a una coincidencia perfecta en el gráfico bipartito. Una coincidencia perfecta, si existe, se puede encontrar en tiempo O (VE) (o algo mejor, para algoritmos más avanzados).

Ahora el problema se convierte en generar una coincidencia perfecta aleatoria distribuida uniformemente. Creo que eso se puede hacer, aproximadamente de todos modos. La uniformidad de la distribución es la parte realmente difícil.

¿Qué tiene esto que ver con los permanentes? Considere una representación matricial de nuestro gráfico bipartito, donde un 1 significa un borde y un 0 significa que no hay borde:

1 1 0 0
1 1 1 0
0 1 1 1
0 0 1 1

El permanent de la matriz es como el determinante, excepto que no hay signos negativos en la definición. Así que tomamos exactamente un elemento de cada fila y columna, los multiplicamos juntos y sumamos todas las elecciones de fila y columna. Los términos de lo permanente corresponden a permutaciones; el término es 0 si cualquier factor es 0, en otras palabras, si la permutación no es válida de acuerdo con la representación de la matriz / gráfico bipartito; el término es 1 si todos los factores son 1, en otras palabras, si la permutación es válida de acuerdo con las restricciones. En resumen, el permanente de la matriz cuenta todas las permutaciones que satisfacen la restricción representada por el gráfico de matriz / bipartito.

Resulta que, a diferencia del cálculo de los determinantes, que se puede lograr en tiempo O (n ^ 3), el cálculo de los permanentes es # P-completo, por lo que no es factible encontrar una respuesta exacta en general. Sin embargo, si podemos estimar el número de permutaciones válidas, podemos estimar el permanente. Jerrum et. Alabama. abordó el problema de contar permutaciones válidas generando permutaciones válidas de manera uniforme (dentro de un cierto error, que puede ser controlado); se puede obtener una estimación del valor del permanente mediante un procedimiento bastante elaborado (sección 5 del documento al que se hace referencia), pero no necesitamos eso para responder la pregunta en cuestión.

El tiempo de ejecución del algoritmo de Jerrum para calcular el permanente es O (n ^ 11) (ignorando los factores logarítmicos). No puedo decir de inmediato en el papel el tiempo de ejecución de la parte del algoritmo que genera emparejamientos bipartitos de manera uniforme, pero parece estar sobre O (n ^ 9). Sin embargo, otro documento reduce el tiempo de ejecución del permanente a O (n ^ 7): http://www.cc.gatech.edu/fac/vigoda/FasterPermanent_SODA.pdf ; en ese documento afirman que ahora es posible obtener una buena estimación de una matriz permanente de 100x100 0-1. Por lo tanto, debería ser posible (casi) uniformemente permutaciones restringidas para listas de 100 elementos.

Puede haber mejoras adicionales, pero me cansé de mirar.

Si desea una implementación, comenzaría con la versión O (n ^ 11) en el documento de Jerrum y luego echaría un vistazo a las mejoras si el algoritmo original no es lo suficientemente rápido.

Hay un pseudocódigo en el documento de Jerrum, pero no lo he probado, así que no puedo decir qué tan lejos está el pseudocódigo de una implementación real. Mi sensación es que no está muy lejos. Tal vez lo intentaré si hay interés.

Answer 5

Esto va a ser largo y seco.

Tengo una solución que produce una distribución uniforme. Requiere O(len(L) * d**d) tiempo y espacio para la precomputación, luego realiza la reproducción aleatoria en O(len(L)*d) tiempo ¹ . Si no se requiere una distribución uniforme, la precomputación no es necesaria y el tiempo de reproducción aleatoria puede reducirse a O(len(L)) debido a elecciones aleatorias más rápidas; No he implementado la distribución no uniforme. Ambos pasos de este algoritmo son sustancialmente más rápidos que la fuerza bruta, pero aún no son tan buenos como me gustaría que fueran. Además, aunque el concepto debería funcionar, no he probado mi implementación tan a fondo como me gustaría.

Supongamos que iteramos sobre L desde el frente, eligiendo una posición para cada elemento cuando lleguemos a él. Defina el retraso como la distancia entre el siguiente elemento a colocar y la primera posición sin llenar. Cada vez que colocamos un elemento, el retraso aumenta a lo sumo uno, ya que el índice del siguiente elemento ahora es uno más alto, pero el índice de la primera posición sin llenar no puede ser más bajo.

Cuando el retraso es d , nos vemos obligados a colocar el siguiente elemento en la primera posición sin llenar, aunque puede haber otros lugares vacíos dentro de una distancia de d . Si lo hacemos, el retraso no puede crecer más allá de d , siempre tendremos un lugar para colocar cada elemento y generaremos una mezcla aleatoria válida de la lista. Por lo tanto, tenemos una idea general de cómo generar shuffles; sin embargo, si tomamos nuestras decisiones de manera uniforme al azar, la distribución general no será uniforme. Por ejemplo, con len(L) == 3 y d == 1 , hay 3 combinaciones aleatorias posibles (una para cada posición del elemento central), pero si elegimos la posición del primer elemento de manera uniforme, una combinación se convierte en el doble de Probablemente como cualquiera de los otros.

Si queremos una distribución uniforme sobre las combinaciones aleatorias válidas, debemos hacer una elección aleatoria ponderada para la posición de cada elemento, donde el peso de una posición se basa en el número de combinaciones aleatorias posibles si elegimos esa posición. Hecho de forma ingenua, esto requeriría que generáramos todos los shuffles posibles para contarlos, lo que llevaría un tiempo de O(d**len(L)) . Sin embargo, el número de posibles shuffles que quedan después de cada paso del algoritmo depende solo de los puntos que hemos llenado, no del orden en que se rellenaron. Para cualquier patrón de puntos llenos o sin llenar, el número de shuffles posibles es la suma de el número de posibles shuffles para cada posible colocación del siguiente elemento. En cualquier paso, hay como máximo d posiciones posibles para colocar el siguiente elemento, y hay O(d**d) posibles patrones de puntos sin rellenar (ya que cualquier punto más alejado que d detrás del elemento actual debe estar lleno, y cualquier punto d o más adelante debe estar vacío). Podemos usar esto para generar una cadena de Markov de tamaño O(len(L) * d**d) , lo que toma O(len(L) * d**d) tiempo para hacerlo, y luego usar esta cadena de Markov para realizar baraja en tiempo O(len(L)*d) .

Código de ejemplo (actualmente no del todo O(len(L)*d) debido a la ineficiente representación de la cadena de Markov):

import random
# states are (k, filled_spots) tuples, where k is the index of the next
# element to place, and filled_spots is a tuple of booleans
# of length 2*d, representing whether each index from k-d to
# k+d-1 has an element in it. We pretend indices outside the array are
# full, for ease of representation.
def _successors(n, d, state):
''''''Yield all legal next filled_spots and the move that takes you there.
Doesn''t handle k=n.''''''
k, filled_spots = state
next_k = k+1
# If k+d is a valid index, this represents the empty spot there.
possible_next_spot = (False,) if k + d < n else (True,)
if not filled_spots[0]:
# Must use that position.
yield k-d, filled_spots[1:] + possible_next_spot
else:
# Can fill any empty spot within a distance d.
shifted_filled_spots = list(filled_spots[1:] + possible_next_spot)
for i, filled in enumerate(shifted_filled_spots):
if not filled:
successor_state = shifted_filled_spots[:]
successor_state[i] = True
yield next_k-d+i, tuple(successor_state)
# next_k instead of k in that index computation, because
# i is indexing relative to shifted_filled_spots instead
# of filled_spots
def _markov_chain(n, d):
''''''Precompute a table of weights for generating shuffles.
_markov_chain(n, d) produces a table that can be fed to
_distance_limited_shuffle to permute lists of length n in such a way that
no list element moves a distance of more than d from its initial spot,
and all permutations satisfying this condition are equally likely.
This is expensive.
''''''
if d >= n - 1:
# We don''t need the table, and generating a table for d >= n
# complicates the indexing a bit. It''s too complicated already.
return None
table = {}
termination_state = (n, (d*2 * (True,)))
table[termination_state] = 1
def possible_shuffles(state):
try:
return table[state]
except KeyError:
k, _ = state
count = table[state] = sum(
possible_shuffles((k+1, next_filled_spots))
for (_, next_filled_spots) in _successors(n, d, state)
)
return count
initial_state = (0, (d*(True,) + d*(False,)))
possible_shuffles(initial_state)
return table
def _distance_limited_shuffle(l, d, table):
# Generate an index into the set of all permutations, then use the
# markov chain to efficiently find which permutation we picked.
n = len(l)
if d >= n - 1:
random.shuffle(l)
return
permutation = [None]*n
state = (0, (d*(True,) + d*(False,)))
permutations_to_skip = random.randrange(table[state])
for i, item in enumerate(l):
for placement_index, new_filled_spots in _successors(n, d, state):
new_state = (i+1, new_filled_spots)
if table[new_state] <= permutations_to_skip:
permutations_to_skip -= table[new_state]
else:
state = new_state
permutation[placement_index] = item
break
return permutation
class Shuffler(object):
def __init__(self, n, d):
self.n = n
self.d = d
self.table = _markov_chain(n, d)
def shuffled(self, l):
if len(l) != self.n:
raise ValueError(''Wrong input size'')
return _distance_limited_shuffle(l, self.d, self.table)
__call__ = shuffled

¹ Podríamos usar un algoritmo de selección aleatoria ponderada basada en árbol para mejorar el tiempo de orden aleatorio a O(len(L)*log(d)) , pero como la tabla se vuelve tan grande incluso para d moderadamente grande, esto no parece valer la pena . Además, los factores de d**d en los límites son sobreestimaciones, pero los factores reales aún son al menos exponenciales en d.

Answer 6

Mi idea es generar permutaciones moviéndose en la mayoría de los pasos d generando permutaciones aleatorias que se mueven como máximo 1 paso y encadenándolas.

Podemos generar permutaciones que se mueven como máximo 1 paso rápidamente mediante el siguiente procedimiento recursivo: considere una permutación de {1,2,3, ..., n}. El último elemento, n, puede mover 0 o 1 lugar. Si mueve 0 lugares, n es fijo, y hemos reducido el problema para generar una permutación de {1,2, ..., n-1} en el que cada elemento se mueve como máximo en un lugar.

Por otro lado, si n se mueve 1 lugar, debe ocupar la posición n-1. Entonces n-1 debe ocupar la posición n (si un número menor ocupa la posición n, se habrá movido más de 1 lugar). En otras palabras, debemos tener un intercambio de n y n-1, y después del intercambio, hemos reducido el problema para encontrar una permutación del resto de la matriz {1, ..., n-2}.

Tales permutaciones se pueden construir en tiempo O (n), claramente.

Esas dos opciones deben seleccionarse con probabilidades ponderadas. Dado que no conozco los pesos (aunque tengo una teoría, ver más abajo) tal vez la elección debería ser 50-50 ... pero ver más abajo.

Una estimación más precisa de los pesos podría ser la siguiente: tenga en cuenta que el número de tales permutaciones sigue una recursión que es la misma que la secuencia de Fibonacci: f (n) = f (n-1) + f (n-2). Tenemos f (1) = 1 y f (2) = 2 ({1,2} va a {1,2} o {2,1}), por lo que los números realmente son los números de Fibonacci. Entonces, mi conjetura sobre la probabilidad de elegir n fijo frente a intercambio n y n-1 sería f (n-1) / f (n) vs. f (n-2) / f (n). Dado que la proporción de números de Fibonacci consecutivos se aproxima rápidamente a la proporción de oro, una aproximación razonable a las probabilidades es dejar n el 61% del tiempo fijo e intercambiar n y n-1 el 39% del tiempo.

Para construir permutaciones donde los elementos se mueven en la mayoría de los lugares d, simplemente repetimos el proceso d veces. El tiempo de ejecución es O (nd).

Aquí hay un esquema de un algoritmo.

arr = {1,2,...,n};
for (i = 0; i < d; i++) {
j = n-1;
while (j > 0) {
u = random uniform in interval (0,1)
if (u < 0.61) { // related to golden ratio phi; more decimals may help
j -= 1;
} else {
swap items at positions j and j-1 of arr // 0-based indexing
j -= 2;
}
}
}

Dado que cada paso mueve los elementos como máximo 1 lugar desde su inicio, los pases d moverán los elementos en la mayoría de los lugares d. La única cuestión es la distribución uniforme de las permutaciones. Probablemente sería una prueba larga, si es cierta, así que sugiero reunir evidencia empírica para varias n''s y d''s. Probablemente para probar la afirmación, tendríamos que cambiar de usar la aproximación de la proporción áurea a f (n-1) / f (n-2) en lugar de 0.61.

Incluso podría haber alguna extraña razón por la cual este procedimiento puede pasar por alto algunas permutaciones, pero estoy bastante seguro de que eso no sucede. Sin embargo, por si acaso, sería útil tener un inventario completo de tales permutaciones para algunos valores de n y d para verificar la corrección de mi algoritmo propuesto.

Actualizar

Encontré un error de apagado por uno en mi "pseudocódigo", y lo corregí. Luego lo implementé en Java para tener una idea de la distribución. El código está abajo. Creo que la distribución dista mucho de ser uniforme, ya que hay muchas formas de obtener permutaciones restringidas con distancias máximas cortas (avanzar, retroceder frente a retroceder, avanzar, por ejemplo) pero hay pocas formas de obtener distancias largas (avanzar) seguir adelante). No puedo pensar en una manera de solucionar el problema de uniformidad con este método.

import java.util.Random;
import java.util.Map;
import java.util.TreeMap;
class RestrictedPermutations {
private static Random rng = new Random();
public static void rPermute(Integer[] a, int d) {
for (int i = 0; i < d; i++) {
int j = a.length-1;
while (j > 0) {
double u = rng.nextDouble();
if (u < 0.61) { // related to golden ratio phi; more decimals may help
j -= 1;
} else {
int t = a[j];
a[j] = a[j-1];
a[j-1] = t;
j -= 2;
}
}
}
}
public static void main(String[] args) {
int numTests = Integer.parseInt(args[0]);
int d = 2;
Map<String,Integer> count = new TreeMap<String,Integer>();
for (int t = 0; t < numTests; t++) {
Integer[] a = {1,2,3,4,5};
rPermute(a,d);
// convert a to String for storage in Map
String s = "(";
for (int i = 0; i < a.length-1; i++) {
s += a[i] + ",";
}
s += a[a.length-1] + ")";
int c = count.containsKey(s) ? count.get(s) : 0;
count.put(s,c+1);
}
for (String k : count.keySet()) {
System.out.println(k + ": " + count.get(k));
}
}
}

Answer 7

No estoy seguro de lo bueno que es, pero tal vez algo como:

• crear una lista de la misma longitud que la lista inicial L; cada elemento de esta lista debe ser una lista de índices de índices iniciales permitidos que se moverán aquí; por ejemplo [[0,1,2],[0,1,2,3],[0,1,2,3],[1,2,3]] si entiendo correctamente su ejemplo;
• tome la sublista más pequeña (o cualquiera de las sublistas más pequeñas si varias listas comparten la misma longitud);
• elija un elemento aleatorio con random.choice , este elemento es el índice del elemento en la lista inicial que se asignará a la ubicación actual (use otra lista para crear su nueva lista);
• eliminar el elemento elegido al azar de todos los sublistas

Por ejemplo:

L = [ "A", "B", "C", "D" ]
i = [[0,1,2],[0,1,2,3],[0,1,2,3],[1,2,3]]
# I take [0,1,2] and pick randomly 1 inside
# I remove the value ''1'' from all sublists and since
# the first sublist has already been handled I set it to None
# (and my result will look as [ "B", None, None, None ]
i = [None,[0,2,3],[0,2,3],[2,3]]
# I take the last sublist and pick randomly 3 inside
# result will be ["B", None, None, "D" ]
i = [None,[0,2], [0,2], None]
etc.

Sin embargo, no lo he probado. Saludos.