9

I've been bashing my skull at this problem for some time now, and its really starting to frustrate me. The problem is:

I have a set of characters, A, B, C, and D. I have to tell in how many ways a string can be built from those characters, when the length is n and each character must occur even times.

For example, the answer for n = 2 is 4:

AA
BB
CC
DD

The answer for n = 4 is 40. Some of those valid strings are:

AAAA
AABB
CACA
DAAD
BCCB

I'm stuck at coming up with a logic. I feel like there could be a DP solution for this. Brute-forcing my way through this is out of the question: the number of solutions rapidly grow into huge numbers.

I've tried drawing all kinds of ideas on paper, to no avail. Almost all of those ideas I had to discard as their complexity was too big. The solution should be efficient for n = 10^4.

One of my ideas was to never keep track of the actual strings, but only whether each character has appeared even or odd times. I couldn't come up with a way to apply this logic.

Can anyone help me?

  • 3
    Do you need to enumerate the strings, or calculate the number of strings? If you only need the number of strings, you can likely use combinatorics to calculate the quantity directly. – user22815 Feb 9 '15 at 22:40
  • @Snowman Only the number of possible strings is needed. However I find it unlikely that I could use combinatorics here. Even if there was a way, I'm sure the problem isn't supposed to be solved with pure mathematics, and for that reason do not want to. Or what did you mean? – Olavi Mustanoja Feb 9 '15 at 22:46
  • 2
    Sure you can use combinatorics. For a string of length N, get all combinations of {AA,BB,CC,DD}. For each combination, get the unique permutations. Then combine the results for each combination into one set of unique permutations. I am not sure how to do this, primarily because of the uniqueness constraint, but I am sure there is a way. – user22815 Feb 9 '15 at 22:53
  • @Snowman I see what you mean. But wouldn't that require storing at least the combinations? Getting the number of unique permutations require this, and the number of combinations grow very quickly into proportions I couldn't possibly store. – Olavi Mustanoja Feb 9 '15 at 23:03
  • 1
    Possibly. I am not well-versed enough with combinatorics to know for sure. Maybe Mathematics.SE has a question similar to this? I do not have the time to dig into it right now, but this is an interesting problem. I'll think about it and check back. – user22815 Feb 9 '15 at 23:16
5

Set up f(n,d) as a function giving the number of permutations of (even) length n using d distinct characters (i.e d=4 in your case).

Clearly f(0,d) = 1 and f(n,1) = 1 as there's only one arrangement when you have only one character, or zero spaces.

Now the induction step:

To make a valid string using d characters, take any shorter even-length string using d-1 characters and make it up to length by adding in an even multiple of this new character. The number of arrangements is choose(n,n_newdigits) because you can choose n_newdigit places out of the total string length to have the new digit, and the rest are filled by the original string in order.

To implement this using naive recursion in R, I did:

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

for the sort of numbers you're interested I'd have thought that it'd be more efficient to store numbers in a two dimensional array, and iterate over increasing d, but this may depend on your choice of language.

4

Miff's answer is definitely elegant. Since I had mine nearly finished anyway I provide it nevertheless. The good thing is that I get the same result for n=500 :-)

Let d be the number of different characters that are allowed, d=4 in your case.

Let n be the length of the string, ultimately you will be looking at even values of n.

Let u be the number of unpaired characters in a string.

Let N(n,d,u) be the number of strings of length n, built from d different characters and having u unpaired characters. Lets try to compute N.

There are quite a few corner cases to observe:

u>d or u>n => N=0

u<0 => N=0

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

When stepping from n to n+1, u must either increase by 1 or decrease by 1, so we have a recursion according to

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

How many ways are there to reduce u by one. This one is easy, because we have to pair one of the u unpaired characters, which makes it just u. So the 2nd part of f will read (u+1)*N(n-1,d,u+1), with the caveat of course that we must observe that N=0 if u+1>n-1 or u+1>d.

Once we have understood this, it is easy to see what the first part of f is: in how many ways can we increase u when there are u-1 unpaired characters. Well, we have to pick one of the (k-(u-1)) characters which are paired.

So taking into account all corner cases, the recursive formula for N is

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

I am not going to read up in http://en.wikipedia.org/wiki/Concrete_Mathematics how to solve the recursion.

Instead I wrote some Java code. Again a little bit more clumsy, as is Java anyway due to its verbosity. But I had the motivation not to use recursion, since it breaks far to early, at least in Java, when the stack overflows at 500 or 1000 nesting levels.

The result for n=500, d=4 and u=0 is:

N(500, 4, 0) = 1339385758982834151185531311325002263201756014631917009304687985462938813906170153116497973519619822659493341146941433531483931607115392554498072196838958545795769042788035468026048125208904713757765805163872455056995809556627183222337328039422584942896842901774597806462162357229520744881314972303360

computed in 0.2 seconds, due to memorizing intermediate results. N(40000,4,0) computes in less than 5 seconds. Code also here: 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); 
  }
}
2

I tried to come up with a solution but failed and asked the same question on Mathematics.StackExchange. Thanks to Rus May, here is a solution, in Common Lisp:

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

This always return 0 for odd values of n. For n = 500, here is the output with 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.