Anzahl der Zeichenfolgen, wenn jedes Zeichen gerade vorkommen muss

Ich habe meinen Schädel schon seit einiger Zeit auf dieses Problem geschlagen und es beginnt mich wirklich zu frustrieren. Das Problem ist:

Ich habe eine Reihe von Zeichen, A, B, C, und D. Ich muss sagen, auf wie viele Arten eine Zeichenfolge aus diesen Zeichen erstellt werden kann, wann die Länge ist nund jedes Zeichen gerade mal vorkommen muss.

Zum Beispiel n = 2lautet die Antwort für 4:

AA
BB
CC
DD

Die Antwort für n = 4ist 40. Einige dieser gültigen Zeichenfolgen sind:

AAAA
AABB
CACA
DAAD
BCCB

Ich bin fest entschlossen, eine Logik zu entwickeln. Ich denke, es könnte eine DP-Lösung dafür geben. Es kommt nicht in Frage, mich brutal durchzusetzen: Die Anzahl der Lösungen wächst schnell zu einer großen Anzahl.

Ich habe versucht, alle möglichen Ideen auf Papier zu zeichnen, ohne Erfolg. Fast alle diese Ideen musste ich verwerfen, da ihre Komplexität zu groß war. Die Lösung sollte effizient sein für n = 10^4.

Eine meiner Ideen war es, niemals die tatsächlichen Saiten im Auge zu behalten, sondern nur, ob jeder Charakter gerade oder ungerade Male aufgetaucht ist. Ich konnte mir keine Möglichkeit einfallen lassen, diese Logik anzuwenden.

Kann mir jemand helfen?

Richten Sie dies f(n,d)als Funktion ein, die die Anzahl der Permutationen mit (gerader) Länge unter nVerwendung dunterschiedlicher Zeichen angibt (dh d=4in Ihrem Fall).

Klar f(0,d) = 1und f(n,1) = 1da es nur eine Anordnung gibt, wenn Sie nur ein Zeichen oder keine Leerzeichen haben.

Nun der Induktionsschritt:

Um eine gültige Zeichenfolge mit dZeichen zu erstellen, nehmen Sie eine kürzere Zeichenfolge mit gerader Länge d-1und verwenden Sie die Länge, indem Sie ein gerades Vielfaches dieses neuen Zeichens hinzufügen. Die Anzahl der Arrangements ist darauf zurückzuführen, choose(n,n_newdigits)dass Sie n_newdigitOrte aus der Gesamtlänge der Zeichenfolge auswählen können, um die neue Ziffer zu erhalten, und der Rest wird der Reihe nach mit der ursprünglichen Zeichenfolge gefüllt.

Um dies mit naiver Rekursion in R zu implementieren, habe ich:

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

Für die Art von Zahlen, die Sie interessieren, hätte ich gedacht, dass es effizienter wäre, Zahlen in einem zweidimensionalen Array zu speichern und über das zunehmende d zu iterieren, aber dies kann von Ihrer Wahl der Sprache abhängen.

Miffs Antwort ist definitiv elegant. Da ich meine sowieso fast fertig hatte, stelle ich sie trotzdem zur Verfügung. Das Gute ist, dass ich für n = 500 das gleiche Ergebnis bekomme :-)

Sei d die Anzahl der verschiedenen Zeichen, die erlaubt sind, d = 4 in Ihrem Fall.

Sei n die Länge des Strings, letztendlich sehen Sie gerade Werte von n.

Sei u die Anzahl der ungepaarten Zeichen in einer Zeichenfolge.

Sei N (n, d, u) die Anzahl der Zeichenketten der Länge n, die aus d verschiedenen Zeichen aufgebaut sind und u ungepaarte Zeichen haben. Versuchen wir, N zu berechnen.

Es gibt einige Eckfälle zu beobachten:

u> d oder u> n => N = 0

u <0 => N = 0

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

Wenn Sie von n nach n + 1 gehen, muss u entweder um 1 zunehmen oder um 1 abnehmen, sodass wir eine Rekursion gemäß haben

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

Wie viele Möglichkeiten gibt es, dich um eins zu reduzieren? Dieser ist einfach, weil wir einen der u ungepaarten Charaktere koppeln müssen, was es nur zu u macht. Der 2. Teil von f lautet also (u + 1) * N (n-1, d, u + 1), mit der Einschränkung, dass wir N = 0 beachten müssen, wenn u + 1> n-1 oder u +1> d.

Sobald wir dies verstanden haben, ist es leicht zu erkennen, was der erste Teil von f ist: Auf wie viele Arten können wir u erhöhen, wenn es ungepaarte u-1-Zeichen gibt. Nun, wir müssen eines der (k- (u-1)) Zeichen auswählen, die gepaart sind.

Unter Berücksichtigung aller Eckfälle lautet die rekursive Formel für N.

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

Ich werde in http://en.wikipedia.org/wiki/Concrete_Mathematics nicht nachlesen, wie man die Rekursion löst.

Stattdessen habe ich Java-Code geschrieben. Wieder etwas ungeschickter, da Java aufgrund seiner Ausführlichkeit sowieso ist. Aber ich hatte die Motivation, keine Rekursion zu verwenden, da sie zumindest in Java viel zu früh bricht, wenn der Stapel bei 500 oder 1000 Verschachtelungsebenen überläuft.

Das Ergebnis für n = 500, d = 4 und u = 0 ist:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

berechnet in 0,2 Sekunden aufgrund des Speicherns von Zwischenergebnissen. N (40000,4,0) berechnet in weniger als 5 Sekunden. Code auch hier: 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); 
  }
}

Ich habe versucht, eine Lösung zu finden, bin jedoch gescheitert und habe dieselbe Frage zu Mathematics.StackExchange gestellt . Dank Rus May gibt es hier eine Lösung in Common Lisp:

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

Dies gibt immer 0 für ungerade Werte von zurück n. Denn n = 500hier ist die Ausgabe mit 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