Número de cadenas, cuando cada carácter debe aparecer incluso veces

He estado golpeando mi cráneo por este problema desde hace un tiempo, y realmente está empezando a frustrarme. El problema es:

Tengo un conjunto de caracteres, A, B, C, y D. Tengo que decir de cuántas maneras se puede construir una cadena a partir de esos caracteres, cuándo es la longitud ny cada carácter debe ocurrir incluso en ocasiones.

Por ejemplo, la respuesta para n = 2es 4:

AA
BB
CC
DD

La respuesta n = 4es 40. Algunas de esas cadenas válidas son:

AAAA
AABB
CACA
DAAD
BCCB

Estoy atrapado en llegar a una lógica. Siento que podría haber una solución DP para esto. La fuerza bruta en mi camino a través de esto está fuera de discusión: la cantidad de soluciones crece rápidamente en grandes cantidades.

He intentado dibujar todo tipo de ideas en papel, sin éxito. Casi todas esas ideas las tuve que descartar porque su complejidad era demasiado grande. La solución debe ser eficiente para n = 10^4.

Una de mis ideas fue no hacer un seguimiento de las cadenas reales, sino solo si cada personaje ha aparecido en momentos pares o impares. No pude encontrar una manera de aplicar esta lógica.

¿Alguien puede ayudarme?

Configure f(n,d)como una función que proporcione el número de permutaciones de longitud (par) nutilizando dcaracteres distintos (es decir, d=4en su caso).

Claramente f(0,d) = 1y f(n,1) = 1como solo hay un arreglo cuando solo tienes un personaje, o cero espacios.

Ahora el paso de inducción:

Para hacer una cadena válida usando dcaracteres, tome cualquier cadena más corta de longitud par usando d-1caracteres y agréguela agregando un múltiplo par de este nuevo carácter. El número de arreglos se choose(n,n_newdigits)debe a que puede elegir n_newdigitlugares fuera de la longitud total de la cadena para tener el nuevo dígito, y el resto se llena con la cadena original en orden.

Para implementar esto usando la recursión ingenua en R, hice:

f <- function(n,d)
{
  if(n==0) return(1)
  if(d==1) return(1)
  retval=0
  for (i in seq(from=0, to=n, by=2)) retval=retval+f(n-i,d-1)*choose(n,i)
  return(retval)
}

f(4,4)
# 40    

f(500,4)
# 1.339386e+300 takes about 10 secs

para el tipo de números que le interese, hubiera pensado que sería más eficiente almacenar números en una matriz bidimensional e iterar sobre d creciente, pero esto puede depender de su elección del idioma.

La respuesta de Miff es definitivamente elegante. Como de todos modos tuve el mío casi terminado, lo proporciono sin embargo. Lo bueno es que obtengo el mismo resultado para n = 500 :-)

Sea d el número de caracteres diferentes que están permitidos, d = 4 en su caso.

Sea n la longitud de la cadena, en última instancia, verá valores pares de n.

Sea el número de caracteres no apareados en una cadena.

Sea N (n, d, u) el número de cadenas de longitud n, construidas a partir de d caracteres diferentes y que tengan caracteres no apareados. Intentemos calcular N.

Hay bastantes casos de esquina para observar:

u> do u> n => N = 0

u <0 => N = 0

n% 2! = u% 2 => N = 0.

Al pasar de n a n + 1, debe aumentar en 1 o disminuir en 1, por lo que tenemos una recursión de acuerdo con

N (n, d, u) = f (N (n-1, d, u-1), N (n-1, d, u + 1))

¿Cuántas maneras hay de reducirlo en uno? Este es fácil, porque tenemos que emparejar uno de los caracteres u no apareados, lo que lo convierte en u Entonces, la segunda parte de f leerá (u + 1) * N (n-1, d, u + 1), con la advertencia, por supuesto, de que debemos observar que N = 0 si u + 1> n-1 o u +1> d.

Una vez que hemos entendido esto, es fácil ver cuál es la primera parte de f: de cuántas maneras podemos aumentar u cuando hay caracteres u-1 no apareados. Bueno, tenemos que elegir uno de los caracteres (k- (u-1)) que están emparejados.

Teniendo en cuenta todos los casos de esquina, la fórmula recursiva para N es

N (n, d, u) = (d- (u-1)) * N (n-1, d, u-1) + (u + 1) * N (n-1, d, u + 1)

No voy a leer en http://en.wikipedia.org/wiki/Concrete_Mathematics cómo resolver la recursividad.

En cambio, escribí un código Java. De nuevo, un poco más torpe, como lo es Java de todos modos debido a su verbosidad. Pero tuve la motivación de no usar la recursión, ya que se rompe muy temprano, al menos en Java, cuando la pila se desborda en 500 o 1000 niveles de anidamiento.

El resultado para n = 500, d = 4 yu = 0 es:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

calculado en 0.2 segundos, debido a la memorización de resultados intermedios. N (40000,4,0) calcula en menos de 5 segundos. Código también aquí: http://ideone.com/KvB5Jv

import java.math.BigInteger;

public class EvenPairedString2 {
  private final int nChars;  // d above, number of different chars to use
  private int count = 0;
  private Map<Task,BigInteger> memo = new HashMap<>();

  public EvenPairedString2(int nChars) {
    this.nChars = nChars;
  }
  /*+******************************************************************/
  // encodes for a fixed d the task to compute N(strlen,d,unpaired).  
  private static class Task {
    public final int strlen;
    public final int unpaired;

    Task(int strlen, int unpaired) {
      this.strlen = strlen;
      this.unpaired = unpaired;
    }
    @Override
    public int hashCode() {
      return strlen*117 ^ unpaired;
    }
    @Override
    public boolean equals(Object other) {
      if (!(other instanceof Task)) {
        return false;
      }
      Task t2 = (Task)other;
      return strlen==t2.strlen && unpaired==t2.unpaired;
    }
    @Override
    public String toString() {
      return "("+strlen+","+unpaired+")";
    }
  }
  /*+******************************************************************/
  // return corner case or memorized result or null  
  private BigInteger getMemoed(Task t) {
    if (t.strlen==0 || t.unpaired<0 || t.unpaired>t.strlen || t.unpaired>nChars
        || t.strlen%2 != t.unpaired%2) {
      return BigInteger.valueOf(0);
    }

    if (t.strlen==1) {
      return BigInteger.valueOf(nChars);
    }
    return memo.get(t);
  }

  public int getCount() {
    return count;
  }

  public BigInteger computeNDeep(Task t) {
    List<Task> stack = new ArrayList<Task>();
    BigInteger result = null;
    stack.add(t);

    while (stack.size()>0) {
      count += 1;
      t = stack.remove(stack.size()-1);
      result = getMemoed(t);
      if (result!=null) {
        continue;
      }

      Task t1 = new Task(t.strlen-1, t.unpaired+1);
      BigInteger r1 = getMemoed(t1);
      Task t2 = new Task(t.strlen-1, t.unpaired-1);
      BigInteger r2 = getMemoed(t2);
      if (r1==null) {
        stack.add(t);
        stack.add(t1);
        if (r2==null) {
          stack.add(t2);
        }
        continue;
      }
      if (r2==null) {
        stack.add(t);
        stack.add(t2);
        continue;
      }
      result = compute(t1.unpaired, r1, nChars-t2.unpaired, r2);
      memo.put(t,  result);
    }
    return result;
  }
  private BigInteger compute(int u1, BigInteger r1, int u2, BigInteger r2) {
    r1 = r1.multiply(BigInteger.valueOf(u1));
    r2 = r2.multiply(BigInteger.valueOf(u2));
    return r1.add(r2);
  }
  public static void main(String[] argv) {
    int strlen = Integer.parseInt(argv[0]);
    int nChars = Integer.parseInt(argv[1]);

    EvenPairedString2 eps = new EvenPairedString2(nChars);

    BigInteger result = eps.computeNDeep(new Task(strlen, 0));
    System.out.printf("%d: N(%d, %d, 0) = %d%n", 
                      eps.getCount(), strlen, nChars, 
                      result); 
  }
}

Traté de encontrar una solución, pero fallé y formulé la misma pregunta en Mathematics.StackExchange . Gracias a Rus May , aquí hay una solución, en Common Lisp:

(defun solve (n)
  (if (evenp n)
      (/ (+ (expt 4 n) (* 4 (expt 2 n))) 8)
      0))

Esto siempre devuelve 0 para valores impares de n. Para n = 500, aquí está la salida con SBCL :

* (time (solve 500))

    Evaluation took:
      0.000 seconds of real time
      0.000000 seconds of total run time (0.000000 user, 0.000000 system)
      100.00% CPU
      51,100 processor cycles
      0 bytes consed

    1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360