Antecedentes
Sea
El número de permutaciones distintas de
Pregunta
¿Existe un algoritmo eficiente para generar dos permutaciones difusas y desordenadas
Una permutación
P es difusa si para cada elemento distintoi deP , las instancias dei están espaciados a cabo más o menos uniformemente enP .Por ejemplo, supongamos que
S=(1424)={1,1,1,1,2,2,2,2} .{1,1,1,2,2,2,2,1} no es difuso{1,2,1,2,1,2,1,2} es difuso
Más rigurosamente:
- Si , solo hay una instancia de para “espaciar” en , así que dejemos .
ni=1 i P Δ(i)=0 - De lo contrario, y mucho ser la distancia entre instancia y la instancia de en . Reste de ella la distancia esperada entre las instancias de , definiendo lo siguiente:
Si está espaciada de manera uniforme en , entonces debe ser cero, o muy cerca de cero si .
d(i,j) j j+1 i P i i P Δ ( i ) n i ∤ nδ(i,j)=d(i,j)−nniΔ(i)=∑j=1ni−1δ(i,j)2 i P Δ(i) ni∤n
Ahora definir la estadística de para medir la cantidad de cada está espaciada de manera uniforme en . Llamamos difuso si está cerca de cero, o aproximadamente . (Se puede elegir un umbral específico para para que sea difuso si )i P P s ( P ) s ( P ) ≪ n 2 k ≪ 1 S P s ( P ) < k n 2
s(P)=∑ci=1Δ(i) i P P s(P) s(P)≪n2 k≪1 S P s(P)<kn2 Esta restricción recuerda un problema de programación en tiempo real más estricto llamado problema del molinete con multiset (de modo que ) y densidad . El objetivo es programar una secuencia infinita cíclica manera que cualquier subsecuencia de longitud contenga al menos una instancia de . En otras palabras, un programa factible requiere todo ; si es denso ( ), entonces y . El problema del molinete parece ser NP-completo.
A=n/S ai=n/ni ρ=∑ci=1ni/n=1 P ai i d(i,j)≤ai A ρ=1 d(i,j)=ai s(P)=0 Dos permutaciones y se alteran si es un trastorno de ; es decir, para cada índice .
P Q P Q Pi≠Qi i∈[n] Por ejemplo, supongamos que .
S=(1222)={1,1,2,2} {1,2,1,2} y no están alterados{1,1,2,2} {1,2,1,2} y están alterados{2,1,2,1}
Análisis exploratorio
Estoy interesado en la familia de multisets con y para . En particular, dejemos .
La probabilidad de que dos permutaciones aleatorias y de están trastornados es de aproximadamente 3%.
P Q D Esto se puede calcular de la siguiente manera, donde es el polinomio th Laguerre: Vea aquí para una explicación.
Lk k |DD||SD|p=∫∞0dte−t∏i=1cLni(t)=∫∞0dte−t(L4(t))3(L3(t))(L2(t))(L1(t))3=4.5×1011=n!∏i=1c1ni!=20!(4!)3(3!)(2!)(1!)3=1.5×1013=|DD|/|SD|≈0.03 La probabilidad de que una permutación aleatoria de sea difusa es de aproximadamente 0.01%, estableciendo el umbral arbitrario en aproximadamente .
P D s(P)<25 A continuación se muestra una gráfica de probabilidad empírica de 100,000 muestras de donde es una permutación aleatoria de .
s(P) P D En tamaños de muestra medios, .
s(P)∼Gamma(α≈8,β≈18) P{1,8,2,3,4,1,5,2,3,6,1,4,2,3,7,1,5,2,4,3}{8,2,3,4,1,6,5,2,3,4,1,7,1,2,3,5,4,1,2,3}{3,6,5,1,3,4,2,1,2,7,8,5,2,4,1,3,3,2,1,4}{3,1,3,4,8,2,2,1,1,5,3,3,2,6,4,4,2,1,7,5}{4,1,1,4,5,5,1,3,3,7,1,2,2,4,3,3,8,2,2,6}s(P)119≈11409≈166509≈7212239≈13616979≈189cdf(s(P))<10−5<10−4<10.05<10.45<10.80
La probabilidad de que dos permutaciones aleatorias sean válidas (difusas y desordenadas) es de alrededor de
.
Algoritmos ineficientes
Un algoritmo común "rápido" para generar un desorden aleatorio de un conjunto se basa en el rechazo:
hacer P ← aleatorio_permutación ( D ) hasta que is_derangement ( D , P ) volver P
lo que requiere aproximadamente iteraciones, ya que existen aproximadamente posibles alteraciones. Sin embargo, un algoritmo aleatorio basado en rechazo no sería eficiente para este problema, ya que tomaría el orden de iteraciones.
En el algoritmo utilizado por Sage , un desorden aleatorio de un conjunto múltiple "se forma al elegir un elemento al azar de la lista de todos los desordenes posibles". Sin embargo, esto también es ineficiente, ya que hay permutaciones válidas para enumerar, y además, uno necesitaría un algoritmo para hacerlo de todos modos.
Mas preguntas
¿Cuál es la complejidad de este problema? ¿Se puede reducir a cualquier paradigma familiar, como el flujo de red, la coloración de gráficos o la programación lineal?
Respuestas:
Un enfoque: puede reducir esto al siguiente problema: Dada una fórmula booleana , elija una asignación uniformemente al azar entre todas las asignaciones satisfactorias de . Este problema es NP-hard, pero existen algoritmos estándar para generar una que se distribuye de manera aproximadamente uniforme, tomando prestados métodos de los algoritmos #SAT. Por ejemplo, una técnica es elegir una función hashφ(x) x φ(x) x h cuyo rango tenga un tamaño cuidadosamente elegido (aproximadamente el mismo tamaño que el número de asignaciones satisfactorias de ), elegir uniformemente al azar un valor dentro del rango deφ y h , y luego use un solucionador SAT para encontrar una asignación satisfactoria a la fórmula . Para hacerlo eficiente, puede elegir como un mapa lineal disperso.φ(x)∧(h(x)=y) h
Esto podría ser disparar una pulga con un cañón, pero si no tiene otros enfoques que parezcan factibles, este es uno que podría probar.
fuente
en el chat de cs se inició una discusión / análisis extendido de este problema con antecedentes adicionales que descubrieron cierta subjetividad en los complejos requisitos del problema pero no encontraron errores o descuidos directos. 1
Aquí hay un código probado / analizado que, en comparación con la otra solución basada en SAT, es relativamente "rápido y sucio", pero no fue trivial / difícil de depurar. se basa libremente en un esquema local de optimización pseudoaleatorio / codicioso algo similar a, por ejemplo, 2-OPT para TSP . la idea básica es comenzar con una solución aleatoria que se ajuste a alguna restricción, y luego perturbarla localmente para buscar mejoras, buscar codiciosamente las mejoras e iterar a través de ellas, y finalizar cuando se hayan agotado todas las mejoras locales. Un criterio de diseño fue que el algoritmo debería ser tan eficiente / evitar el rechazo tanto como sea posible.
Hay algunas investigaciones sobre algoritmos de trastorno [4], por ejemplo, utilizados en SAGE [5], pero no están orientados a múltiples conjuntos.
la perturbación simple es solo "intercambios" de dos posiciones en la tupla (s). La implementación es en rubí. A continuación se presenta una descripción general / notas con referencias a números de línea.
qb2.rb ( gist -github)
El enfoque aquí es comenzar con dos tuplas trastornadas (# 106) y luego mejorar localmente / con avidez la dispersión (# 107), combinada en un concepto llamado
derangesperse
(# 97), preservando el desorden. tenga en cuenta que intercambiar dos mismas posiciones en el par de tuplas preserva el desorden y puede mejorar la dispersión y ese es (parte de) el método / estrategia de dispersión.el
derange
subrutina funciona de izquierda a derecha en la matriz (multiset) y se intercambia con elementos más adelante en la matriz donde el intercambio no es con el mismo elemento (# 10). el algoritmo tiene éxito si, sin más intercambios en la última posición, las dos tuplas todavía están alteradas (# 16).Hay 3 enfoques diferentes para alterar las tuplas iniciales. la segunda tupla
p2
siempre se baraja. se puede comenzar con la tupla 1 (p1
) ordenada pora.
"potencias más altas de primer orden" (# 128),b.
orden aleatorio (# 127)c.
y "potencias más bajas de primer orden" ("potencias más altas de último orden") (# 126).La rutina de dispersión
disperse
es más complicada pero conceptualmente no es tan difícil. nuevamente usa swaps. en lugar de tratar de optimizar la dispersión en general sobre todos los elementos, simplemente trata de aliviar de manera iterativa el peor de los casos actuales. la idea es encontrar los primeros elementos menos dispersos, de izquierda a derecha. la perturbación es intercambiar los elementos izquierdos o derechos (x, y
índices) del par menos disperso con otros elementos pero nunca ninguno entre el par (lo que siempre disminuiría la dispersión), y también omitir el intento de intercambiar con los mismos elementos (select
en # 71) .m
es el índice del punto medio del par (# 65).sin embargo, la dispersión se mide / optimiza sobre ambas tuplas en el par (# 40) usando la dispersión "menor / más a la izquierda" en cada par (# 25, # 44).
el algoritmo intenta intercambiar los elementos "más lejanos" 1 ° (
sort_by / reverse
# 71).existen dos estrategias diferentes
true, false
para decidir si se intercambia el elemento izquierdo o derecho del par menos disperso (# 80), ya sea el elemento izquierdo para la posición de intercambio al elemento izquierdo / derecho al lado derecho, o el elemento más alejado a la izquierda o derecha en el par disperso del elemento de intercambio.el algoritmo termina (# 91) cuando ya no puede mejorar la dispersión (ya sea moviendo la peor ubicación de dispersión hacia la derecha o aumentando la dispersión máxima en todo el par de tuplas (# 85)).
se generan estadísticas para rechazos superiores a
c
= 1000 desordenes en los 3 enfoques (# 116) yc
= 1000 desordenadores (# 97), observando los 2 algoritmos dispersos para un par trastornado del rechazo (# 19, # 106). el último rastrea la dispersión promedio total (después del desorden garantizado). un ejemplo de ejecución es el siguienteesto muestra que el
a-true
algoritmo proporciona mejores resultados con ~ 92% de no rechazo y una distancia de dispersión peor promedio de ~ 2.6, y un mínimo garantizado de 2 sobre 1000 ensayos, es decir, al menos 1 elemento intermedio no igual entre todos los pares del mismo elemento. Encontró soluciones tan altas como 3 elementos intermedios no iguales.el algoritmo de desorden es el rechazo de tiempo lineal, y el algoritmo de dispersión (que se ejecuta en una entrada desordenada) parece ser posiblemente ~ .O(nlogn)
1 el problema es encontrar arreglos de paquetes quizbowl que satisfagan el llamado "feng shui" [1] o un ordenamiento aleatorio "agradable" donde "agradable" es algo subjetivo y aún no cuantificado "oficialmente"; el autor del problema lo analizó / redujo a los criterios de desorden / dispersión basados en investigaciones realizadas por la comunidad de preguntas y "expertos en feng shui". [2] Hay diferentes ideas sobre las "reglas del feng shui". se ha realizado alguna investigación "publicada" sobre algoritmos, pero aparece en etapas tempranas. [3]
[1] Paquete feng shui / QBWiki
[2] Paquetes de Quizbowl y feng shui / Lifshitz
[3] Colocación de preguntas , foro del centro de recursos HSQuizbowl
[4] Generando desordenes al azar / Martinez, Panholzer, Prodinger
[5] Algoritmo de trastorno de salvia (python) / McAndrew
fuente