nombre de chaînes, lorsque chaque caractère doit apparaître même des fois

Je frappe mon crâne à ce problème depuis un certain temps maintenant, et ça commence vraiment à me frustrer. Le problème est:

J'ai un ensemble de caractères, A, B, Cet D. Je dois dire de combien de façons une chaîne peut être construite à partir de ces caractères, quand la longueur est net que chaque caractère doit se produire même des fois.

Par exemple, la réponse n = 2est 4:

AA
BB
CC
DD

La réponse pour n = 4est 40. Certaines de ces chaînes valides sont:

AAAA
AABB
CACA
DAAD
BCCB

Je suis coincé à trouver une logique. J'ai l'impression qu'il pourrait y avoir une solution DP pour cela. Il est hors de question de forcer brutalement mon chemin: le nombre de solutions croît rapidement en très grand nombre.

J'ai essayé de dessiner toutes sortes d'idées sur papier, en vain. Presque toutes ces idées que j'ai dû abandonner car leur complexité était trop grande. La solution doit être efficace pour n = 10^4.

L'une de mes idées était de ne jamais garder une trace des chaînes réelles, mais seulement de savoir si chaque personnage était apparu à des moments pairs ou impairs. Je ne pouvais pas trouver un moyen d'appliquer cette logique.

Quelqu'un peut-il m'aider?

Configuré f(n,d)comme une fonction donnant le nombre de permutations de longueur (paire) en nutilisant ddes caractères distincts (c'est- d=4à- dire dans votre cas).

En clair f(0,d) = 1et f(n,1) = 1comme il n'y a qu'un seul arrangement quand vous n'avez qu'un seul caractère, ou zéro espace.

Maintenant, l'étape d'induction:

Pour créer une chaîne valide à l'aide de dcaractères, prenez une chaîne de longueur paire plus courte à l'aide de d-1caractères et complétez-la en ajoutant un multiple pair de ce nouveau caractère. Le nombre d'arrangements est choose(n,n_newdigits)dû au fait que vous pouvez choisir des n_newdigitemplacements dans la longueur totale de la chaîne pour avoir le nouveau chiffre, et le reste est rempli par la chaîne d'origine dans l'ordre.

Pour implémenter cela en utilisant la récursivité naïve dans R, j'ai fait:

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

Pour le type de nombres qui vous intéresse, j'aurais pensé qu'il serait plus efficace de stocker des nombres dans un tableau à deux dimensions et d'itérer sur l'augmentation de d, mais cela peut dépendre de votre choix de langue.

La réponse de Miff est définitivement élégante. Comme j'avais presque fini le mien, je le fournis quand même. La bonne chose est que j'obtiens le même résultat pour n = 500 :-)

Soit d le nombre de caractères différents autorisés, d = 4 dans votre cas.

Soit n la longueur de la chaîne, en fin de compte, vous regarderez les valeurs paires de n.

Soit u le nombre de caractères non appariés dans une chaîne.

Soit N (n, d, u) le nombre de chaînes de longueur n, construites à partir de d caractères différents et ayant u caractères non appariés. Essayons de calculer N.

Il y a quelques cas d'angle à observer:

u> d ou u> n => N = 0

u <0 => N = 0

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

Lorsque vous passez de n à n + 1, u doit soit augmenter de 1, soit diminuer de 1, nous avons donc une récursion selon

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

Combien de façons existe-t-il de réduire u d'une unité. Celui-ci est facile, car nous devons associer l'un des u caractères non appariés, ce qui le rend juste u. Donc, la 2e partie de f se lira (u + 1) * N (n-1, d, u + 1), avec la mise en garde bien sûr que nous devons observer que N = 0 si u + 1> n-1 ou u +1> d.

Une fois que nous avons compris cela, il est facile de voir quelle est la première partie de f: de combien de façons pouvons-nous augmenter u quand il y a u-1 caractères non appariés. Eh bien, nous devons choisir l'un des (k- (u-1)) caractères qui sont appariés.

Donc, en tenant compte de tous les cas d'angle, la formule récursive pour N est

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

Je ne vais pas lire dans http://en.wikipedia.org/wiki/Concrete_Mathematics comment résoudre la récursivité.

Au lieu de cela, j'ai écrit du code Java. Encore un peu plus maladroit, tout comme Java en raison de sa verbosité. Mais j'ai eu la motivation de ne pas utiliser la récursivité, car elle se casse bien au début, du moins en Java, lorsque la pile déborde à 500 ou 1000 niveaux d'imbrication.

Le résultat pour n = 500, d = 4 et u = 0 est:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

calculé en 0,2 seconde, en raison de la mémorisation des résultats intermédiaires. N (40000,4,0) calcule en moins de 5 secondes. Code également ici: 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); 
  }
}

J'ai essayé de trouver une solution mais j'ai échoué et posé la même question sur Mathematics.StackExchange . Merci à Rus May , voici une solution, en Common Lisp:

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

Ce retour toujours 0 pour les valeurs impaires de n. Pour n = 500, voici la sortie avec 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