Cómo calcular permutaciones en tiempo lineal, con un giro

Question

Tengo un problema de programación de recursos en Java donde las cosas necesitan ser secuenciadas, pero hay restricciones sobre qué recursos pueden estar uno al lado del otro. Una buena analogía es una cadena de & "; Dígitos &"; Donde solo ciertos dígitos pueden estar uno al lado del otro. Mi solución fue recursiva y funciona bien para cadenas pequeñas, pero el tiempo de ejecución es O (X ^ N), donde X es el número de dígitos posibles (la base) y N es la longitud de la cadena. Rápidamente se vuelve inmanejable.

Usando la matriz de compatibilidad a continuación, aquí hay algunos ejemplos de cadenas permitidas
Longitud de 1: 0, 1, 2, 3, 4
Duración de 2: 02, 03, 14, 20, 30, 41
Longitud de 3: 020, 030, 141, 202, 203, 302, 303, 414

     0  1  2  3  4
   ---------------------
0|  0  0  1  1  0
1|  0  0  0  0  1
2|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

Mi solución para contar todas las cadenas de longitud N fue comenzar con una cadena vacía, permutar el primer dígito y hacer una llamada recursiva para todas las cadenas de longitud N-1. Las llamadas recursivas verifican el último dígito que se agregó y prueban todas las permutaciones que pueden estar al lado de ese dígito. Hay algunas optimizaciones hechas para que no intente permutar 00, 01, 04 cada vez, por ejemplo, solo 02, 03, pero el rendimiento sigue siendo pobre ya que escala desde la base 5 (el ejemplo) a la base 4000.

¿Alguna idea sobre una mejor manera de contar las permutaciones que no sea enumerarlas todas?

Answer 1

Si solo desea el número de cadenas de una determinada longitud, puede multiplicar la matriz de compatibilidad consigo mismo varias veces y sumar sus valores.

  

n = longitud de la cadena
   A = matriz de compatibilidad
   número de cadenas posibles = suma de A^n-1

Algunos ejemplos:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

La matriz original (fila i , columna j ) podría considerarse como el número de cadenas que comienzan con el símbolo i , y cuyo próximo símbolo es el símbolo j . Alternativamente, puede verlo como un número de cadenas de longitud 2 , que comienzan con el símbolo i y terminan con el símbolo j .

La multiplicación matricial conserva esta invariante, por lo que después de la exponenciación, A ^{n -1} contendría el número de cadenas que comienzan con el símbolo i , tiene una longitud n y termina en el símbolo j .

Consulte Wikipedia: Exponenciación por cuadratura para obtener un algoritmo para un cálculo más rápido de las potencias de la matriz.

(Gracias stefan.ciobaca)

Este caso específico se reduce a la fórmula:

  

número de cadenas posibles = f ( n ) = 4 + Σ _{k =1..n} 2 ^{& # 8970; k -1 & # 8260; ₂ & # 8971;} = f ( n -1) + 2 ^{& # 8970; n -1 & # 8260; ₂ & # 8971;}

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66

Answer 2

¿Desea saber cuántas cadenas de una longitud determinada puede construir con las reglas en la matriz dada? Si es así, un enfoque como este debería funcionar:

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))

Answer 3

Su algoritmo parece ser óptimo.

¿Cómo estás usando estas permutaciones? ¿Los está acumulando en una lista, o los está utilizando uno por uno? Dado que hay una gran cantidad de tales permutaciones, el bajo rendimiento puede deberse al uso de una gran memoria (si las está recolectando todas) o simplemente lleva mucho tiempo. Simplemente no puede hacer miles de millones de bucles en tiempo trivial.

Responder al comentario:

Si solo desea contarlos, puede usar la programación dinámica:

Deje que count [n] [m] sea una matriz, donde count [l] [j] es el número de permutaciones cuya longitud es l y finaliza con j,

luego cuenta [l] [i] = cuenta [l-1] [i1] + cuenta [l-1] [i2] + ..., donde i1, i2, ... son los dígitos que pueden preceder i (esto se puede guardar en una matriz calculada previamente).

Cada celda de conteo se puede completar sumando K números (K depende de la matriz compatible), por lo que la complejidad es O (KMN), M es la longitud de la permutación y N es el número total de dígitos.

Answer 4

Tal vez no entiendo esto, pero ¿no se serviría esto teniendo una tabla de listas que para cada dígito tenga una lista de dígitos válidos que puedan seguirla?

Entonces su rutina para generar tomará un resultado acumulado, el número de dígito y el dígito actual. Algo así como:

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

La complejidad aumenta en función del número de dígitos a generar, pero esa función depende del número total de seguimientos válidos para cualquier dígito. Si el número total de seguimientos es el mismo para cada dígito, digamos, k, entonces el tiempo para generar todas las permutaciones posibles será O (k ^ n) donde n es el número de dígitos. Lo siento, no puedo cambiar las matemáticas. El tiempo para generar n dígitos en la base 10 es 10 ^ n.

Answer 5

No estoy exactamente seguro de lo que estás preguntando, ¡pero dado que potencialmente hay n! permutaciones de una cadena de n dígitos, ¡no podrás listarlas más rápido que n !. No estoy exactamente seguro de cómo crees que obtuviste un tiempo de ejecución de O (n ^ 2).