我不知道如何解决这个编程问题。
给定两个整数 n 和 m，存在多少个数字，使得所有数字都具有从 0 到 n-1 的所有数字，并且两个相邻数字之间的差恰好为 1，并且数字中的数字数量最多为 'm'。
解决此问题的最佳方法是什么？有没有直接的数学公式？
编辑：数字不能以 0 开头。
示例：对于 n = 3 和 m = 6，有 18 个这样的数字（210、2101、21012、210121 ... 等）
更新（有些人遇到了歧义）： 必须存在从 0 到 n-1 的所有数字。
问问题
331 次
4 回答
2
此 Python 代码通过跟踪以特定数字结尾的数字来计算 O(nm) 中的答案。
不同的数组（A、B、C、D）用于跟踪达到范围最大值或最小值的数字。
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
于 2013-08-20T12:49:38.470 回答
2
在做了更多研究之后，我认为实际上可能有一种数学方法，尽管数学对我来说是高级的。Douglas S. Stones为我指明了 Joseph Myers (2008) 文章BMO 2008-2009 第 1 轮问题 1-泛化的方向，该文章推导了计算矩形板上之字形路径数量的公式。
据我了解，在 Anirudh 的示例中，我们的电路板将有 6 行长度为 3 的行（我相信这意味着n=3和r=6文章的术语）。我们可以这样可视化我们的电路板：
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
由于迈尔斯的公式m(n,r)将生成所有之字形路径的数字，即所有相邻数字都是连续的并且数字选自 (0,1,2) 的所有 6 位数字的数量，我们仍然需要确定并减去以零开头的数字和不包括所有数字的数字。
如果我理解正确，我们可以通过以下方式为我们的示例执行此操作，尽管将概念概括为任意m并且n可能证明更复杂：
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...
于 2013-08-25T08:12:53.273 回答
1
一种方法可能是对其进行递归编程，调用函数来添加和减去最后一位数字。
哈斯克尔代码：
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]
输出：
*Main> f 3 6
["210","1210","1012","2101","12101","10121","21210","21012"
,"21010","121210","121012","121010","101212","101210","101012"
,"212101","210121","210101"]
为了回应 Anirudh Rayabharam 的评论，我希望下面的代码会更像“伪代码”。当总位数达到时，如果解决方案已经散列了所有 [0..n-1]，m则函数g输出 1，否则输出 0。该函数f累积g起始位数 [1..n-1] 和总位数 [n..m] 的结果。
哈斯克尔代码：
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)
输出：
*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)
于 2013-08-20T16:55:13.913 回答
0
将您的问题建模为二维中的 2 个叠加晶格，特别是(i,j)与定向边互连的对，((i0,j0),(i1,j1))其中i1 = i0 + 1, |j1 - j0| = 1，修改如下：
- 丢弃所有对 (i,j)
j > 9及其入射边 - 丢弃所有对 (i,j)
i > m-1及其入射边 - 下降沿
((0,0), (1,1))
这种结构会产生如下图所示的结构：
：
请求的数字映射到从(0,j), j=1..min(n-1,9)包含至少一个粉红色和一个红色元素 ( (i,0), i=1..m-1, (i,n-1), i=0..m-1) 的绿色元素 ( ) 之一开始的点阵中的路径。要看到这一点，请用 point 识别给定数字的i第 - 位。包括粉红色和红色元素（“极值数字”）保证所有可用的数字都在数字中表示。j(i,j)
分析
为方便起见，让 q1, q2 表示位置 1。
让q1是一个数字的第一个数字的位置 要么0要么min(n-1,9)。如果位置的数字是 和vv ，则令q2为数字的第一个位置。0q1min(n-1,9)
案例1：第一个极值数字是0
包含 no 的有效前缀的数量0可以表示为sum_{k=1..min(n-1,9)} (paths_to_0(k,1,q1)，函数paths_to_0被递归定义为
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);
同样我们有
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);
最后
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);
...总共
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)
)
案例2：第一个极值数字是min(n-1,9)
案例2.1：初始数字不是min(n-1,9)
这与案例1对称，所有数字都d替换为min(n,10) - d。由于晶格结构是对称的，这意味着number_count_case_2_1 = number_count_case_1。
案例2.2：第一个数字是注意min(n-1,9)
，第二个数字必须是。因此q11min(n-2,8)
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)
)
所以总和将是
number_count ( n, m ) = 2 * number_count_case_1 (n, m) + number_count_case_2_2 (n, m);
代码
我不知道是否存在封闭表达式number_count，但以下 perl 代码将计算它（代码只是概念证明，因为它不使用记忆技术来避免重新计算已经获得的结果）：
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;
于 2013-08-20T18:19:18.437 回答