Calculation of total combinations

Question

I do not know how to solve this programming problem.

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

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

Edit: The number cannot begin with 0.

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

Update (some people are faced with ambiguity): All numbers must be present from 0 to n-1.

Answer 1

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

Different arrays (A, B, C, D) are used to track numbers that have reached 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 that in fact there can be a mathematical approach, although mathematics is developed for me. Douglas S. Stones pointed me toward an article by Joseph Myers (2008), BMO 2008-2009 Round 1 Problem 1-Generalization , which derives formulas for calculating the number of zigzag paths on a rectangular board.

As I understand it, in the Anirud example, our board will have 6 lines of length 3 (I believe that this means n=3 and r=6 in terms of the article). We can visualize our board like this:

 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 the Myers formula m(n,r) will generate a number for all zigzag paths, i.e. the number of all six-digit numbers, where all adjacent digits are consecutive, and the numbers are selected from (0,1,2), we still need to determine and subtract those that start from zero and those that do not contain all the numbers.

If I understand correctly, we can do this as follows for our example, although generalizing the concept to arbitrary m and n may be 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 and 1's, and all the m(2,6) that would include 1 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 late here, I might follow up tomorrow... 

Answer 3

One approach may be to program it recursively by calling a function to add and subtract from the last digit.

Haskell Code:

 import Data.List (sort,nub) fnm = concatMap (combs n) [n..m] combs nm = 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 "pseudo-code." When the total number of digits reaches m , the function g outputs 1 if the solution has has has all [0..n-1], and 0 if not. The function f accumulates the results for g for the beginning of the digits [1..n-1] and the total number of digits [n..m].

Haskell Code:

 import qualified Data.Set as S g :: Int -> Int -> Int -> Int -> (S.Set Int, Int) -> Int gnm digitCount lastDigit (hash,hashCount) | digitCount == m = if test then 1 else 0 | otherwise = if lastDigit == 0 then gnmd' (lastDigit + 1) (hash'',hashCount') else if lastDigit == n - 1 then gnmd' (lastDigit - 1) (hash'',hashCount') else gnmd' (lastDigit + 1) (hash'',hashCount') + gnmd' (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) fnm = foldr forEachNumDigits 0 [n..m] where forEachNumDigits numDigits accumulator = accumulator + foldr forEachStartingDigit 0 [1..n - 1] where forEachStartingDigit startingDigit accumulator' = accumulator' + gn 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 combined lattices in 2 dimensions, in particular, as pairs (i,j) connected with oriented edges ((i0,j0),(i1,j1)) , where i1 = i0 + 1, |j1 - j0| = 1 i1 = i0 + 1, |j1 - j0| = 1 , modified as follows:

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

this design leads to a structure, as in this diagram:

:

the requested numbers are displayed on the path in the lattice, starting with one of the green elements ( (0,j), j=1..min(n-1,9) ), which 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 digit i -th j given number with the dot (i,j) . including pink and red elements ("extreme numbers") ensure that all available numbers are represented in a number.

Analysis

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

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

case 1 : the first extreme digit is 0

the number of valid prefixes that do not contain 0 can be expressed as sum_{k=1..min(n-1,9)} (paths_to_0(k,1,q1) , and the function paths_to_0 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 total cost

 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 : the first extreme digit is min(n-1,9)

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

Case 2.2 : The initial digit is min(n-1,9) note that q1 is 1 , and the second digit should 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 overall result will be

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

the code

I don’t know if there is a closed expression for number_count , but the following Perl code will calculate it (the code is just a confirmation of the concept, since it does not use storage methods to avoid recounting the 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;