Caculating total combinations

Question

I don't know how to go about this programming problem.

Given two integers n and m, how many numbers exist such that all numbers have all digits from 0 to n-1 and the difference between two adjacent digits is exactly 1 and the number of digits in the number is atmost 'm'.

What is the best way to solve this problem? Is there a direct mathematical formula?

Edit: The number cannot start with 0.

Example: for n = 3 and m = 6 there are 18 such numbers (210, 2101, 21012, 210121 ... etc)

Update (some people have encountered an ambiguity): All digits from 0 to n-1 must be present.

Answer 1

This Python code computes the answer in O(nm) by keeping track of the numbers ending with a particular digit.

Different arrays (A,B,C,D) are used to track numbers that have hit the maximum or minimum of the range.

n=3
m=6
A=[1]*n # Number of ways of being at digit i and never being to min or max
B=[0]*n # number of ways with minimum being observed
C=[0]*n # number of ways with maximum being observed
D=[0]*n # number of ways with both being observed
A[0]=0 # Cannot start with 0
A[n-1]=0 # Have seen max so this 1 moves from A to C
C[n-1]=1 # Have seen max if start with highest digit
t=0
for k in range(m-1):
    A2=[0]*n
    B2=[0]*n
    C2=[0]*n
    D2=[0]*n
    for i in range(1,n-1):
        A2[i]=A[i+1]+A[i-1]
        B2[i]=B[i+1]+B[i-1]
        C2[i]=C[i+1]+C[i-1]
        D2[i]=D[i+1]+D[i-1]
    B2[0]=A[1]+B[1]
    C2[n-1]=A[n-2]+C[n-2]
    D2[0]=C[1]+D[1]
    D2[n-1]=B[n-2]+D[n-2]
    A=A2
    B=B2
    C=C2
    D=D2
    x=sum(d for d in D2)
    t+=x
print t

Answer 2

After doing some more research, I think there may actually be a mathematical approach after all, although the math is advanced for me. Douglas S. Stones pointed me in the direction of Joseph Myers' (2008) article, BMO 2008–2009 Round 1 Problem 1—Generalisation, which derives formulas for calculating the number of zig-zag paths across a rectangular board.

As I understand it, in Anirudh's example, our board would have 6 rows of length 3 (I believe this would mean n=3 and r=6 in the article's terms). We can visualize our board so:

0 1 2   example zig-zag path:  0
0 1 2                            1
0 1 2                          0
0 1 2                            1
0 1 2                              2
0 1 2                            1

Since Myers' formula m(n,r) would generate the number for all the zig-zag paths, that is, the number of all 6-digit numbers where all adjacent digits are consecutive and digits are chosen from (0,1,2), we would still need to determine and subtract those that begin with zero and those that do not include all digits.

If I understand correctly, we may do this in the following way for our example, although generalizing the concept to arbitrary m and n may prove more complicated:

Let m(3,6) equal the number of 6-digit numbers where all adjacent digits  
are consecutive and digits are chosen from (0,1,2). According to Myers,
m(3,r) is given by formula and also equals OEIS sequence A029744 at 
index r+2, so we have 

m(3,6) = 16

How many of these numbers start with zero? Myers describes c(n,r) as the
number of zig-zag paths whose colour is that of the square in the top 
right corner of the board. In our case, c(3,6) would include the total 
for starting-digit 0 as well as starting-digit 2. He gives c(3,2r) as 2^r, 
so we have

c(3,6) = 8. For starting-digit 0 only, we divide by two to get 4.

Now we need to obtain only those numbers that include all the digits in 
the range, but how? We can do this be subtracting m(n-1,r) from m(n,r).
In our case, we have all the m(2,6) that would include only 0's and 1's,
and all the m(2,6) that would include 1's and 2's. Myers gives 
m(2,anything) as 2, so we have

2*m(2,6) = 2*2 = 4

But we must remember that one of the zero-starting numbers is included 
in our total for 2*m(2,6), namely 010101. So all together we have

m(3,6) - c(3,6)/2 - 4 + 1 
= 16 - 4 - 4 + 1 
= 9

To complete our example, we must follow a similar process for m(3,5), 
m(3,4) and m(3,3). Since it's late here, I might follow up tomorrow...

Answer 3

One approach could be to program it recursively, calling the function to add as well as subtract from the last digit.

Haskell code:

import Data.List (sort,nub)

f n m = concatMap (combs n) [n..m]

combs n m = concatMap (\x -> combs' 1 [x]) [1..n - 1] where
  combs' count result
    | count == m = if test then [concatMap show result] else []
    | otherwise  = combs' (count + 1) (result ++ [r + 1])
                ++ combs' (count + 1) (result ++ [r - 1])
   where r = last result
         test = (nub . sort $ result) == [0..n - 1]

Output:

*Main> f 3 6
["210","1210","1012","2101","12101","10121","21210","21012"
,"21010","121210","121012","121010","101212","101210","101012"
,"212101","210121","210101"]

In response to Anirudh Rayabharam's comment, I hope the following code will be more 'pseudocode' like. When the total number of digits reaches m, the function g outputs 1 if the solution has hashed all [0..n-1], and 0 if not. The function f accumulates the results for g for starting digits [1..n-1] and total number of digits [n..m].

Haskell code:

import qualified Data.Set as S

g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> Int
g n m digitCount lastDigit (hash,hashCount)
  | digitCount == m = if test then 1 else 0
  | otherwise       =
      if lastDigit == 0
         then g n m d' (lastDigit + 1) (hash'',hashCount')
         else if lastDigit == n - 1
                 then g n m d' (lastDigit - 1) (hash'',hashCount')
                 else g n m d' (lastDigit + 1) (hash'',hashCount') 
                    + g n m d' (lastDigit - 1) (hash'',hashCount') 
 where test = hashCount' == n
       d' = digitCount + 1
       hash'' = if test then S.empty else hash'
       (hash',hashCount')
         | hashCount == n          = (S.empty,hashCount)
         | S.member lastDigit hash = (hash,hashCount)
         | otherwise               = (S.insert lastDigit hash,hashCount + 1)

f n m = foldr forEachNumDigits 0 [n..m] where
  forEachNumDigits numDigits accumulator = 
    accumulator + foldr forEachStartingDigit 0 [1..n - 1] where 
      forEachStartingDigit startingDigit accumulator' =
        accumulator' + g n numDigits 1 startingDigit (S.empty,0)

Output:

*Main> f 3 6
18
(0.01 secs, 571980 bytes)

*Main> f 4 20
62784
(1.23 secs, 97795656 bytes)

*Main> f 4 25
762465
(11.73 secs, 1068373268 bytes)

Answer 4

model your problem as 2 superimposed lattices in 2 dimensions, specifically as pairs (i,j) interconnected with oriented edges ((i0,j0),(i1,j1)) where i1 = i0 + 1, |j1 - j0| = 1, modified as follows:

• dropping all pairs (i,j) with j > 9 and its incident edges
• dropping all pairs (i,j) with i > m-1 and its incident edges
• dropping edge ((0,0), (1,1))

this construction results in a structure like in this diagram:

:

the requested numbers map to paths in the lattice starting at one of the green elements ((0,j), j=1..min(n-1,9)) that contain at least one pink and one red element ((i,0), i=1..m-1, (i,n-1), i=0..m-1 ). to see this, identify the i-th digit j of a given number with point (i,j). including pink and red elements ('extremal digits') guarantee that all available diguts are represented in the number.

Analysis

for convenience, let q1, q2 denote the position-1.

let q1 be the position of a number's first digit being either 0 or min(n-1,9). let q2 be the position of a number's first 0 if the digit at position q1 is min(n-1,9) and vv.

case 1: first extremal digit is 0

the number of valid prefixes containing no 0 can be expressed as sum_{k=1..min(n-1,9)} (paths_to_0(k,1,q1), the function paths_to_0 being recursively defined as

paths_to_0(0,q1-1,q1)   = 0;
paths_to_0(1,q1-1,q1)   = 1;
paths_to_0(digit,i,q1)  = 0; if q1-i < digit;
paths_to_0(x,_,_)       = 0; if x >= min(n-1,9)
                               // x=min(n-1,9) mustn't occur before position q2,
                               // x > min(n-1,9) not at all
paths_to_0(x,_,_)       = 0; if x <= 0;         
                               // x=0 mustn't occur before position q1,
                               // x < 0 not at all

and else  paths_to_0(digit,i,q1) =
             paths_to_0(digit+1,i+1,q1) + paths_to_0(digit-1,i+1,q1);

similarly we have

paths_to_max(min(n-1,9),q2-1,q2) = 0;
paths_to_max(min(n-2,8),q2-1,q2) = 1;
paths_to_max(digit,i,q2)         = 0  if q2-i < n-1;
paths_to_max(x,_,_)              = 0; if x >= min(n-1,9)
                                       // x=min(n-1,9) mustn't occur before
                                       // position q2,
                                       // x > min(n-1,9) not at all
paths_to_max(x,_,_)              = 0; if x < 0;

and else  paths_to_max(digit,q1,q2) =
              paths_max(digit+1,q1+1,q2) + paths_to_max(digit-1,q1+1,q2);

and finally

paths_suffix(digit,length-1,length) = 2;  if digit > 0 and digit < min(n-1,9)
paths_suffix(digit,length-1,length) = 1;  if digit = 0 or  digit = min(n-1,9)
paths_suffix(digit,k,length)        = 0;  if    length > m-1
                                             or length < q2
                                             or k > length
paths_suffix(digit,k,0)             = 1;  // the empty path

and else  paths_suffix(digit,k,length) = 
             paths_suffix(digit+1,k+1,length) + paths_suffix(digit-1,k+1,length);

... for a grand total of

number_count_case_1(n, m) =
    sum_{first=1..min(n-1,9), q1=1..m-1-(n-1), q2=q1..m-1, l_suffix=0..m-1-q2} (
          paths_to_0(first,1,q1)
        + paths_to_max(0,q1,q2)
        + paths_suffix(min(n-1,9),q2,l_suffix+q2)
    )   

case 2: first extremal digit is min(n-1,9)

case 2.1: initial digit is not min(n-1,9) this is symmetrical to case 1 with all digits d replaced by min(n,10) - d. as the lattice structure is symmetrical, this means number_count_case_2_1 = number_count_case_1.

case 2.2: initial digit is min(n-1,9) note that q1 is 1 and the second digit must be min(n-2,8). thus

number_count_case_2_2 (n, m) = 
    sum_{q2=1..m-2, l_suffix=0..m-2-q2} (
          paths_to_max(1,1,q2)
        + paths_suffix(min(n-1,9),q2,l_suffix+q2)
    )   

so the grand grand total will be

number_count ( n, m ) = 2 * number_count_case_1 (n, m) + number_count_case_2_2 (n, m);

Code

i don't know whether a closed expression for number_count exists, but the following perl code will compute it (the code is but a proof of concept as it does not use memoization techniques to avoid recomputing results already obtained):

use strict;
use warnings;

my ($n, $m) = ( 5, 7 ); # for example

$n = ($n > 10) ? 10 : $n; # cutoff 

sub min
sub paths_to_0 ($$$) {
    my (
          $d
        , $at
        , $until
            ) = @_;
    #
    if (($d == 0) && ($at == $until - 1))   { return 0; }
    if (($d == 1) && ($at == $until - 1))   { return 1; }
    if ($until - $at < $d)                  { return 0; }
    if (($d <= 0) || ($d >= $n)))           { return 0; }

    return paths_to_0($d+1, $at+1, $until) + paths_to_0($d-1, $at+1, $until);    
} # paths_to_0

sub paths_to_max ($$$) {
    my (
          $d
        , $at
        , $until
            ) = @_;
    #
    if (($d == $n-1) && ($at == $until - 1))    { return 0; }
    if (($d == $n-2) && ($at == $until - 1))    { return 1; }
    if ($until - $at < $n-1)                    { return 0; }
    if (($d < 0) || ($d >= $n-1))               { return 0; }

    return paths_to_max($d+1, $at+1, $until) + paths_to_max($d-1, $at+1, $until);    
} # paths_to_max

sub paths_suffix ($$$) {
    my (
          $d
        , $at
        , $until
            ) = @_;
    #
    if (($d < $n-1) && ($d > 0)     && ($at == $until - 1))     { return 2; }
    if ((($d == $n-1) && ($d == 0)) && ($at == $until - 1))     { return 1; }
    if (($until > $m-1) || ($at > $until))                      { return 0; }
    if ($until == 0)                                            { return 1; }

    return paths_suffix($d+1, $at+1, $until) + paths_suffix($d-1, $at+1, $until);    
} # paths_suffix

#
# main
#
    number_count =
        sum_{first=1..min(n-1,9), q1=1..m-1-(n-1), q2=q1..m-1, l_suffix=0..m-1-q2} (
              paths_to_0(first,1,q1)
            + paths_to_max(0,q1,q2)
            + paths_suffix(min(n-1,9),q2,l_suffix+q2)
        )   

my ($number_count, $number_count_2_2) = (0, 0);
my ($first, $q1, i, $l_suffix);

for ($first = 1; $first <= $n-1; $first++) {
    for ($q1 = 1; $q1 <= $m-1 - ($n-1); $q1++) {
        for ($q2 = $q1; $q2 <= $m-1; $q2++) {
            for ($l_suffix = 0; $l_suffix <= $m-1 - $q2; $l_suffix++) {
                $number_count =
                      $number_count
                    + paths_to_0($first,1,$q1)
                    + paths_to_max(0,$q1,$q2)
                    + paths_suffix($n-1,$q2,$l_suffix+$q2)
                ;
            }
        }
    }
}

#
#  case 2.2
#
for ($q2 = 1; $q2 <= $m-2; $q2++) {
    for ($l_suffix = 0; $l_suffix <= $m-2 - $q2; $l_suffix++) {
        $number_count_2_2 =
              $number_count_2_2
            + paths_to_max(1,1,$q2)
            + paths_suffix($n-1,$q2,$l_suffix+$q2)
        ;
    }
}

$number_count = 2 * $number_count + number_count_2_2;