Combinatorics : Grouping Characters Challenges

Question

I was working on some grouping problems at my work. There are quite a few questions, please bear with me. I find them quite interesting. If anyone here is also interested in combinatorics, please help me out.

Ok so we have a bunch of characters , here i have taken a i d s.

1. What are the ways we can group the elements ? Let us say we have 4 characters a i d s. Valid groups(preserving the order) would be:

   a i d s
   a i ds
   a id s
   ai d s
   ai ds
   a ids
   aid s
   aids

How do you enumerate all the groups? Could you tell me how many combinations are there for any n letters?

2 . Special Cases

• What if the case made a difference like Ai sd and ai sd are two groups?

• How much time would it take you to enumerate all the cases? What would be the time difference between finding the 4 letters and 5 letters case?

• If you take the "blank space" as a character. After all the enumeration, how many characters would you have written?

• If you define a transformation from a word to another word in terms of distance. Say "ai ds" and "a i ds" has 1 distance because you should moved the letter "i" one step. Could you find the words at n distance in either side of any word?

Edit:
"aids" is a single word.
"a ids" "aid s" are two words which are at 1 distance from the original word "aids".
"a id s" is a word which is two distance from the original word "aids".
"a i d s" is a word which is three distance from the word.

This problem seems to be gold mine.

Bonus:What is the smallest distance between two words. Like "aids" is one distance from "a ids" and also two distance. Is there a "midpoint" word from where you can reach any other word in the enumeration with least distance? How many paths are there from a word to another?

Answer 1

Computing the number of combinations is trivial. Basically, you have a character between each two letters. It might be "epsilon" (empty), or space. So, for n letters you have n-1 such separator characters. As each character can only have two values, that's the same as a binary number of n-1 digits. So you can have 2 to the power of n-1 combinations.

aids = 4 characters (n = 4)
n - 1 = 3
2 ** (n-1) = 8 combinations

Now, for the special cases. If each character can be either lowercase or uppercase, that's 2 to the power of n variations for the characters (as long as they are letters). Now, EACH combination above has 2n variations based on capitalization, so the end result is (2(n-1)) * (2**n), which is equal to 2 ** (2*n -1).

For each aditional letter you either double or quadruple (depending on the capitalization thing) the time taken to enumerate them, as can be easily understood from the formula.

The total number of characters is a bit more difficult, but suffice to notice that each "space" is "epsilon" half the time. So we have (2 ** (n-1)) * n (letters) + ((2 ** (n-1)) * (n-1)) / 2 (spaces). In the example:

(2 ** 3) * 4 = 32 characters
(2 ** 3) * 3 / 2 = 12 spaces
Total = 44 characters

Finally, the distance problem is related to the Levenshtein distance. I thought about using a Burkhard-Keller tree, but I see now this is not necessary at all, as the problem is rather simpler.

First, the minimum number of inserts/deletions/changes necessary to make one string equal to another is called the Levenshtein distance. This is directly applicable to the problem: you add spaces, delete spaces, change lowercase/uppercase as needed. Usually, this is best solved with Dynamic Programming, which can be generally thought of as keeping data about the solution to small parts of the problem, which then get reused computing other parts/bigger parts.

But given the particular restrictions of our problem, we can just compare the "binary" numbers representing spaces/epsilon.

Say a function f(word) will return the binary number representing spaces in that word. For example, it will return "010" for "ai ds" and "111" for "a i d s". The number of changes between each combination is given by XORing the results of f (010 xor 111 = 101), and then counting the number of bits equal to 1. Let's write a couple of functions in Scala for that:

def spacesToBinary(s: String) = {
  (s zip s.drop(1)) // transform "ai ds" into ((a,i), (i, ), ( ,d), (d, s))
  .foldLeft(0) { (binary, pair) => pair match {
      case (' ', _) => binary            // A space is always followed by a letter,
                                         // so we ignore it
      case (_, ' ') => (binary << 1) | 1 // If a letter is followed by a space, bit = 1
      case _ => binary << 1              // If not, bit = 0
  }}
}

def numberOfOnes(d: Int) = {
  var bits = 0
  var n = d
  while(n != 0) {
    if ((n & 1) == 1)
      bits += 1
    n >>= 1
  }
  bits
} 

def spaceDistance(s1: String, s2: String) = 
  numberOfOnes(spacesToBinary(s1) ^ spacesToBinary(s2))

Now, comparing lowercase/uppercase is quite easy, once we discard spaces:

def caseDistance(s1: String, s2: String) = {
  val ns1 = s1 filter (_ != ' ')
  val ns2 = s2 filter (_ != ' ')
  (ns1 zip ns2).foldLeft(0){(acc, pair) => acc + (if (pair._1 == pair._2) 0 else 1)}
}

So, the Levenshtein distance is:

def levenshtein(s1: String, s2: String) = spaceDistance(s1, s2) + caseDistance(s1, s2)

We also know the following properties about the Levenshtein distance. Say d(x,y) is the Levenshtein distance between x and y. Then we know:

d(x, y) = 0 if, and only if, x = y
d(x, y) = d(y, x)
d(x, y) + d(y, z) >= d(x, z)

The last criteria i known as the triange inequality. Simply put, the path from x to z is at least as small as the path from x to y plus the path from y to z (think a triangle with vertices x, y and z).

Ok, so let's think about the bonus questions.

How many paths there are between two words? Well, if the Levenshtein distance is n, that means you have "n" unique modifications, a1, a2, ..., an. For each different ordering of these modifications you have a path. The number of permutations of "n" elements is the factorial of "n" (or n!):

def factorial(n: Int): Int = n match {
  case 0 => 1
  case _ => n * factorial(n-1)
}

2! = 2
3! = 6
4! = 24
5! = 120
etc

Is there a "central" combination? Actually, no. If we go back and think of combinations as pairs of binary numbers representing the spaces/no-spaces and lower/uppercases, then it should be obvious that you can simply invert the bits to produce a new combination whose distance to the one chosen is the maximum possible.

Or, in other words, for every combination of n letters, there is one, and only one, corresponding combination, so that the Levenshtein distance between the two combinations is 2*n - 1, the maximum possible distance between any two combinations.

I see I forgot to compute all combinations whose (minimum) distance to s is n. Well, we know each combination can be represented as two binary numbers, representing the spaces and the capitalization of each letter, the first being n-1 digits long, and the second n digits long.

We also know that we can simply invert any of these "digits" to get a difference. So, if we get one big binary number 2*n - 1 digits long, and we enumerate all its digits, the combinations at a minimum distance d from it are given by the combination of the 2*n-1 digits in groups of size "d" with no repetitions. For N=2*n-1, the number of such combination is N!/((N-d)! * d!).

For example, for distance 2 and "aids", n=4, d=2, N=2*4-1=7, and the number of combinations is 7!/(5!*2!) = 7 * 6 / 2 = 21.

We can compose the combinations this way:

def computeCombinations(n: Int, d: Int): List[List[Int]] = {
  def gen(d: Int, l: List[Int]): List[List[Int]] = d match {
    case 0 => List(List())
    case _ => for(el <- l;
                  sl <- gen(d-1, l.dropWhile(_ != el).tail))
              yield el :: sl
  }

  gen(d, (0 until n).toList)
}

This will return lists of lists of letter/spaces to change. We indicate which letter or space needs changing through the number of the bit we want to toggle. To simplify things, we assume the binary number for the capitalization and the binary number for the space/no-space are concatenated in a single binary number.

Next, we have to find a way to produce the variations from this information. The upper/lowercase is simple, assuming we receive the word without spaces:

def toggleCharCase(c: Char) = (c ^ ('A' ^ 'a')).toChar
def toggleCases(s: String, bits: List[Int]) = (
  s.zipWithIndex
  map (t => if (Set(bits: _*) contains t._2) (toggleCharCase(t._1), t._2) else t)
  map (_._1)
)

Toggling spaces is more difficult. We'll use spacesToBinary, defined above, convert that into a list of bit numbers which are set, toggle the requested bits and return that. Afterwards, we use a different function to insert the spaces in the proper places:

def toggleSpaces(s: String, bits: List[Int]): List[Int] = {
  val before = spacesToBinary(s)
  val beforeBits = Set() ++ 
                   (for(i <- 0 to 30; // Assuming 32 bits, 1 for sign
                        if (scala.Math.pow(2, i).toInt & before) != 0)
                    yield i)
  val afterBits = (beforeBits union Set(bits: _*)) diff 
                  (beforeBits intersect Set(bits : _*))
  afterBits.toList
}

def addSpaces(s: String, bits: List[Int]): String = (
  s.filter(_ != ' ').zipWithIndex 
  map (t => t._1.toString + (if (bits contains t._2) " " else ""))
  mkString
)

Now we have to compute the space difference, remove the spaces, toggle cases, and then add the spaces back. Let's see:

def changeCombination(s: String, n: Int, bits: List[Int]) = {
  // Split the binary number with all changes into case changes and space changes
  val spaceBits = bits filter (_ >= n) map (_ - n)
  val caseBits = bits filter (_ < n)

  // Compute the set of spaces after changing them
  val newSpaces = toggleSpaces(s, spaceBits)

  // Remove spaces and toggle case
  val noSpaces = s filter (_ != ' ')
  val caseChanged = toggleCases(noSpaces, caseBits).mkString

  // Now add the spaces as computed before
  val spacesAdded = addSpaces(caseChanged, newSpaces).mkString
  spacesAdded
}

Finally, we compute all combinations, and then produce a modified string for each one:

def makeCombinations(s: String, d: Int) = {
  val n = (s filter (_ != ' ')).length
  for(combination <- computeCombinations(n*2-1, d))
  yield changeCombination(s, n, combination)
}

This code has all been tested on Scala 2.8 (except for some renaming I just made). Here is the result of a run:

scala> makeCombinations("ai ds", 2) foreach println
AI ds
Ai Ds
Ai dS
A i ds
Aids
Ai d s
aI Ds
aI dS
a I ds
aIds
aI d s
ai DS
a i Ds
aiDs
ai D s
a i dS
aidS
ai d S
a ids
a i d s
aid s

Answer 2

As the other answers already said, there are 2^(n-1) possiblities for point 1. About some of the special cases (point 2):

• What if the case made a difference like Ai sd and ai sd are two groups?

Well, in that case you had 2^n different case combinations, so you had 2^n * 2^(n-1) = 2^(2 * n - 1) possibilities at all.

• If you take the "blank space" as a character. After all the enumeration, how many characters would you have written?

That's a more interesting question. You have 1 possibility to place no space, 3 possibilities to place 1 space, 3 possibilites to place 2 spaces and 1 possibility to place 3 spaces. This is a binomial distribution, if I recall correctly, and there are formulas to calculate the numbers. You can also use Pascal's triangle for this:

   1
  1 1
 1 2 1
1 3 3 1 <- your case (4th row)
  ...

After you got these numbers, calculate the total character count like this:

1*4 + 3*5 + 3*6 + 1*7 = 44 

Answer 3

http://www-cs-faculty.stanford.edu/~knuth/fasc3b.ps.gz (download Ghostscript/Ghostview if you can't view postscript) discusses partitions in detail.

For a sequence of length n, there are 2^(n-1) partitions. Think of a bit between each pair of consecutive items. If the bit is set, then they're separated (by a space, as you listed them). "aids" (length 4) has 2^3 possible partitions.

In reply to your other questions:

Time to enumerate: O(n*2^n) - constant in the length of the output. Not only does the number of items increase with input length, but the number of characters in each item increases as well.

Number of characters written: let's not count newlines (if you do, add another 2^(n-1) characters). Then you have n*2^(n-1) nonspace characters, plus the number of 1s in all the unique n-1 digit bit strings. The k digit bit strings, when written out, have k*2^k bits, and half of those are 1. So the total number of characters is [n+(n-1)/2]*2^(n-1)), not counting newlines. In your list of the 8 variations on "aids", there are 32 nonspace characters, and 12 spaces - 4*2^3, and (3/2)*2^3 respectively.

Edit distance: you'll have to be more precise about the transformations and their cost. By "word" I assume you mean a single partition (one of your 8 example lines). If an edit is the removal or addition of a single space, then you're talking about Hamming distance on n-1 digit bit strings.