liczba ciągów, w których każdy znak musi wystąpić nawet razy

Od jakiegoś czasu waliłem moją czaszkę w ten problem, który zaczyna mnie naprawdę frustrować. Problemem jest:

Mam zestaw znaków, A, B, C, i D. Muszę powiedzieć, na ile sposobów można zbudować ciąg z tych znaków, kiedy długość jest ni każdy znak musi występować nawet razy.

Na przykład odpowiedź na n = 2to 4:

AA
BB
CC
DD

Odpowiedź na n = 4to 40. Niektóre z tych poprawnych ciągów to:

AAAA
AABB
CACA
DAAD
BCCB

Utknąłem przy wymyślaniu logiki. Wydaje mi się, że mogłoby to być rozwiązanie DP. Brutalne forsowanie mojej drogi przez to nie wchodzi w rachubę: liczba rozwiązań szybko rośnie do ogromnej liczby.

Próbowałem rysować różne pomysły na papierze, ale bezskutecznie. Prawie wszystkie te pomysły musiałem odrzucić, ponieważ ich złożoność była zbyt duża. Rozwiązanie powinno być skuteczne n = 10^4.

Jednym z moich pomysłów było, aby nigdy nie śledzić rzeczywistych ciągów, a jedynie czy każda postać pojawiła się parzysta czy nieparzysta. Nie mogłem znaleźć sposobu na zastosowanie tej logiki.

Czy ktoś może mi pomóc?

Skonfigurowany f(n,d)jako funkcja podająca liczbę permutacji (parzystych) długości nza pomocą dróżnych znaków (tj. d=4W twoim przypadku).

Wyraźnie f(0,d) = 1i f(n,1) = 1ponieważ istnieje tylko jedno ustawienie, gdy masz tylko jedną postać lub zero spacji.

Teraz krok indukcyjny:

Aby utworzyć prawidłowy ciąg znaków przy użyciu dznaków, weź dowolny krótszy ciąg parzystej długości przy użyciu d-1znaków i uzupełnij go, dodając nawet wielokrotność tego nowego znaku. Liczba aranżacji polega na tym, choose(n,n_newdigits)że możesz wybrać n_newdigitmiejsca z całkowitej długości łańcucha, aby mieć nową cyfrę, a pozostałe są wypełniane oryginalnym łańcuchem w kolejności.

Aby zaimplementować to za pomocą naiwnej rekurencji w R, zrobiłem:

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

dla tego rodzaju liczb, które są zainteresowane, pomyślałem, że bardziej efektywne byłoby przechowywanie liczb w tablicy dwuwymiarowej i iteracja po zwiększeniu d, ale może to zależeć od twojego wyboru języka.

Odpowiedź Miffa jest zdecydowanie elegancka. Ponieważ i tak mój prawie już skończył, zapewniam go jednak. Dobrą rzeczą jest to, że otrzymuję ten sam wynik dla n = 500 :-)

Niech d będzie liczbą różnych dozwolonych znaków, d = 4 w twoim przypadku.

Niech n będzie długością łańcucha, ostatecznie będziesz patrzył na parzyste wartości n.

Niech u będzie liczbą niesparowanych znaków w ciągu.

Niech N (n, d, u) będzie liczbą ciągów o długości n, zbudowanych z d różnych znaków i mających nieparowane znaki. Spróbujmy obliczyć N.

Istnieje kilka przypadków narożnych do zaobserwowania:

u> d lub u> n => N = 0

u <0 => N = 0

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

Przechodząc od n do n + 1, musisz albo zwiększyć o 1, albo zmniejszyć o 1, więc mamy rekurencję zgodnie z

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

Ile jest sposobów na zmniejszenie cię o jeden. Ten jest łatwy, ponieważ musimy sparować jedną z niesparowanych postaci, co sprawia, że ​​jest to po prostu ty. Więc druga część f będzie czytać (u + 1) * N (n-1, d, u + 1), z zastrzeżeniem oczywiście, że musimy zauważyć, że N = 0, jeśli u + 1> n-1 lub u +1> d.

Po zrozumieniu tego łatwo jest zobaczyć, jaka jest pierwsza część f: na ile sposobów możemy zwiększyć u, gdy występują u niesparowane znaki u-1. Cóż, musimy wybrać jeden ze sparowanych znaków (k- (u-1)).

Biorąc pod uwagę wszystkie przypadki narożne, formuła rekurencyjna dla N jest następująca

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

Nie zamierzam czytać na http://en.wikipedia.org/wiki/Concrete_Mathematics, jak rozwiązać rekurencję.

Zamiast tego napisałem trochę kodu Java. Znowu trochę bardziej niezręczny, podobnie jak Java, z powodu jej gadatliwości. Miałem jednak motywację, aby nie używać rekurencji, ponieważ łamie się ona zbyt wcześnie, przynajmniej w Javie, gdy stos przepełnia się na 500 lub 1000 poziomach zagnieżdżenia.

Wynik dla n = 500, d = 4 iu = 0 to:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

obliczany w 0,2 sekundy, z powodu zapamiętywania wyników pośrednich. N (40000, 4,0) oblicza w czasie krótszym niż 5 sekund. Kod również tutaj: 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); 
  }
}

Próbowałem znaleźć rozwiązanie, ale nie udało mi się i zadałem to samo pytanie na Mathematics.StackExchange . Dzięki Rus May , oto rozwiązanie w Common Lisp:

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

To zawsze zwraca 0 dla nieparzystych wartości n. Dla n = 500tutaj jest wyjście z 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