количество строк, когда каждый символ должен встречаться даже раз

Я уже давно бьюсь над этой проблемой, и это действительно начинает меня расстраивать. Проблема в:

У меня есть набор символов, A, B, C, и D. Я должен сказать, сколько способов строка может быть построена из этих символов, когда длина nи каждый символ должен встречаться даже раз.

Например, ответ для n = 24:

AA
BB
CC
DD

Ответ для n = 440. Некоторые из этих допустимых строк:

AAAA
AABB
CACA
DAAD
BCCB

Я застрял при разработке логики. Я чувствую, что для этого может быть решение DP. Грубое форсирование моего пути не может быть и речи: число решений быстро возрастает до огромных.

Я пытался нарисовать все виды идей на бумаге, но безрезультатно. Почти все эти идеи мне пришлось отбросить, поскольку их сложность была слишком большой. Решение должно быть эффективным для n = 10^4.

Одна из моих идей состояла в том, чтобы никогда не отслеживать реальные строки, а только то, появлялись ли каждый символ четные или нечетные времена. Я не мог придумать способ применить эту логику.

Может кто-нибудь мне помочь?

Установите f(n,d)как функцию, дающую количество перестановок (четной) длины nс использованием dразличных символов (т.е. d=4в вашем случае).

Понятно f(0,d) = 1и так, f(n,1) = 1как есть только одно расположение, когда у вас есть только один символ, или ноль пробелов.

Теперь шаг индукции:

Чтобы создать правильную строку с использованием dсимволов, возьмите любую более короткую строку четной длины, используя d-1символы, и увеличьте ее, добавив четное число, кратное этому новому символу. Количество аранжировок choose(n,n_newdigits)обусловлено тем, что вы можете выбирать n_newdigitместа из общей длины строки, чтобы иметь новую цифру, а остальные заполняются по порядку исходной строкой.

Чтобы реализовать это, используя наивную рекурсию в R, я сделал:

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

для интересующих вас типов чисел я бы подумал, что было бы более эффективно хранить числа в двумерном массиве и выполнять итерации по увеличению d, но это может зависеть от вашего выбора языка.

Ответ Миффа определенно элегантен. Так как я все равно почти закончил, я все же предоставляю его. Хорошо, что я получаю тот же результат для n = 500 :-)

Пусть d будет количеством допустимых символов, d = 4 в вашем случае.

Пусть n будет длиной строки, в конечном итоге вы будете смотреть на четные значения n.

Пусть u будет количеством непарных символов в строке.

Пусть N (n, d, u) будет числом строк длины n, построенных из d различных символов и имеющих u непарных символов. Давайте попробуем вычислить N.

Есть немало угловых случаев для наблюдения:

u> d или u> n => N = 0

и <0 => N = 0

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

При переходе от n к n + 1 значение u должно увеличиваться на 1 или уменьшаться на 1, поэтому мы имеем рекурсию в соответствии с

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

Сколько существует способов уменьшить тебя на одного. Это легко, потому что мы должны соединить один из непарных символов, что делает его просто u. Таким образом, вторая часть f будет читать (u + 1) * N (n-1, d, u + 1), с оговоркой, конечно, что мы должны заметить, что N = 0, если u + 1> n-1 или u +1> d.

Как только мы поняли это, легко увидеть, что является первой частью f: во сколько раз мы можем увеличить u, когда есть непарные символы u-1. Ну, мы должны выбрать один из (k- (u-1)) символов, которые являются парными.

Таким образом, принимая во внимание все угловые случаи, рекурсивная формула для N

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

Я не собираюсь читать в http://en.wikipedia.org/wiki/Concrete_Matmatics, как решить рекурсию.

Вместо этого я написал немного кода Java. Опять же, немного более неуклюже, как и Java в любом случае из-за его многословия. Но у меня была мотивация не использовать рекурсию, так как она ломается слишком рано, по крайней мере, в Java, когда стек переполняется на 500 или 1000 уровнях вложенности.

Результат для n = 500, d = 4 и u = 0:

N (500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

вычисляется за 0,2 секунды, благодаря запоминанию промежуточных результатов. N (40000,4,0) вычисляется менее чем за 5 секунд. Код также здесь: 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); 
  }
}

Я попытался найти решение, но потерпел неудачу и задал тот же вопрос на Mathematics.StackExchange . Благодаря Rus May , вот решение для Common Lisp:

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

Это всегда возвращает 0 для нечетных значений n. Для n = 500, вот вывод с 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