以下是一个通用解决方案,可以生成与
*(pat)*
匹配且长度不超过固定大小的数字,其中
pat
是任意数字序列。
它按递增顺序生成数字,没有重复项。由于它是一个生成器,因此可以轻松地使用它来生成前几个结果,而不必生成整个列表。(请参见下面的最后一个示例)。
def numbers(pat, k, matched=1):
if (matched >> len(pat)) & 1:
for x in xrange(10 ** k):
yield x
return
if not ((matched << k) >> len(pat)):
return
for d in xrange(10):
nm = 1
for i, pd in enumerate(pat):
if pd == str(d) and (matched >> i) & 1:
nm |= 1 << (i+1)
for n in numbers(pat, k - 1, nm):
yield 10 ** (k - 1) * d + n
它的工作原理是记录到目前为止已匹配了多少个“pat”。为了避免在部分匹配“pat”且下一个数字不匹配时回溯,它保持了到目前为止所有可能部分匹配的位图,这与(非回溯)正则表达式匹配器的方式相同。
以下是一些测试代码,可将其与缓慢但明显正确的实现进行比较。
def numbers_slow(pat, k):
for i in xrange(10 ** k):
if pat in str(i):
yield i
test_cases = [
('9', 3),
('9', 4),
('123', 4),
('22', 4),
]
for pat, k in test_cases:
got = list(numbers(pat, k))
want = list(numbers_slow(pat, k))
if got != want:
print 'numbers(%s, %d) = %s, want %s' % (pat, k, got, want)
以下是问题中提供的示例:
print list(numbers('9', 3))
[9, 19, 29, 39, 49, 59, 69, 79, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 109,
119, 129, 139, 149, 159, 169, 179, 189, 190, 191, 192, 193, 194, 195, 196, 197,
198, 199, 209, 219, 229, 239, 249, 259, 269, 279, 289, 290, 291, 292, 293, 294,
295, 296, 297, 298, 299, 309, 319, 329, 339, 349, 359, 369, 379, 389, 390, 391,
392, 393, 394, 395, 396, 397, 398, 399, 409, 419, 429, 439, 449, 459, 469, 479,
489, 490, 491, 492, 493, 494, 495, 496, 497, 498, 499, 509, 519, 529, 539, 549,
559, 569, 579, 589, 590, 591, 592, 593, 594, 595, 596, 597, 598, 599, 609, 619,
629, 639, 649, 659, 669, 679, 689, 690, 691, 692, 693, 694, 695, 696, 697, 698,
699, 709, 719, 729, 739, 749, 759, 769, 779, 789, 790, 791, 792, 793, 794, 795,
796, 797, 798, 799, 809, 819, 829, 839, 849, 859, 869, 879, 889, 890, 891, 892,
893, 894, 895, 896, 897, 898, 899, 900, 901, 902, 903, 904, 905, 906, 907, 908,
909, 910, 911, 912, 913, 914, 915, 916, 917, 918, 919, 920, 921, 922, 923, 924,
925, 926, 927, 928, 929, 930, 931, 932, 933, 934, 935, 936, 937, 938, 939, 940,
941, 942, 943, 944, 945, 946, 947, 948, 949, 950, 951, 952, 953, 954, 955, 956,
957, 958, 959, 960, 961, 962, 963, 964, 965, 966, 967, 968, 969, 970, 971, 972,
973, 974, 975, 976, 977, 978, 979, 980, 981, 982, 983, 984, 985, 986, 987, 988,
989, 990, 991, 992, 993, 994, 995, 996, 997, 998, 999]
这是一个较为复杂的案例:
print list(numbers('11', 3))
[11, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 211, 311, 411, 511, 611,
711, 811, 911]
以下案例显示该方法即使对于大量数字也非常有效:
print list(numbers('121212121', 10))
[121212121, 1121212121, 1212121210, 1212121211, 1212121212, 1212121213,
1212121214, 1212121215, 1212121216, 1212121217, 1212121218, 1212121219,
2121212121, 3121212121, 4121212121, 5121212121, 6121212121, 7121212121,
8121212121, 9121212121]
为了展示限制生成结果的能力,这里是前21个包含“100000”的20位数。
print itertools.islice(numbers('100000', 20), 21)
[100000, 1000000, 1000001, 1000002, 1000003, 1000004, 1000005, 1000006, 1000007,
1000008, 1000009, 1100000, 2100000, 3100000, 4100000, 5100000, 6100000, 7100000,
8100000, 9100000, 10000000]