以词法顺序查找成千上万个合计为给定数字的组 [英] Find groups of thousands which sum to a given number, in lexical order
问题描述
可以将大量逗号格式化，以便更容易地将其分为三组.例如. 1050 = 1,050和10200 = 10,200.
A large number can be comma formatted to read more easily into groups of three. E.g. 1050 = 1,050 and 10200 = 10,200.
这三组中每组的总和为:
The sum of each of these groups of three would be:
1050=1,050给出:1+50=51
10200=10,200给出:10+200=210
我需要搜索三分之和的匹配项.
即，如果我要搜索1234，那么我正在寻找其三分之和为= 1234的数字.
I need to search for matches in the sum of the groups of threes.
Namely, if I am searching for 1234, then I am looking for numbers whose sum of threes = 1234.
自235+999=1234以来，最小的匹配项是235,999.没有其他小于235,999的整数给出的三分之和等于1234.
The smallest match is 235,999 since 235+999=1234. No other integer less than 235,999 gives a sum of threes equal to 1234.
自236+998=1234起，下一个最小的匹配项是236,998.
每次可以加999，但是在达到999后失败，因为由于999溢出而在数字上加了1.
The next smallest match is 236,998 since 236+998=1234.
One can add 999 each time, but this fails after reaching 999 since an extra digit of 1 is added to the number due to overflow in the 999.
更一般地说，我正在寻求以下解决方案(从最小到最大):
More generally, I am asking for the solutions (smallest to highest) to:
a + b + c + d…= x
a+b+c+d… = x
其中a，b，c，d ...是介于0-999和x之间的任意整数 是一个固定的整数
where a,b,c,d… is an arbitrary number of integers between 0-999 and x is a fixed integer
请注意，对于任何正整数x，都有无限的解决方案.
Note there are infinite solutions to this for any positive integer x.
从最小数目的解(对于y个解，其中y可以是任意大的数)开始，如何获得解决方案?
How would one get the solutions to this beginning with the smallest number solutions (for y number of solutions where y can be an arbitrarily large number)?
有没有一种方法可以做到这一点而又不用蛮力一遍又一遍地循环?我正在处理可能非常大的数字，这可能需要数年时间才能直通.理想情况下，应该做到这一点而不会失败.
Is there a way to do this without brute force looping one by one? I'm dealing with potentially very large numbers, which could take years to loop through in a straight loop. Ideally, one should do this without failed attempts.
推荐答案
如果不考虑由3位数字组成的组，而一次只考虑1位数字，则更容易考虑该问题.
The problem is easier to think about if instead of groups of 3 digits, you just consider 1 digit at a time.
一种算法:
-
首先用x填充0位数字组.
Start by filling the 0 digit group with x.
创建一个循环，每次打印下一个解决方案.
Create a loop that each time prints the next solution.
- 通过将所有太大的对象从右移到左侧来标准化"组，在右侧仅保留最大值.
- 输出解决方案
- 重复:
- 将1加到倒数第二组
- 如果组太大(例如999 + 1太大)，则该值可以移到左侧
- 检查结果是否没有太大(a [0]应该能够吸收添加的内容)
- 如果结果太大，则将组设置为零，然后继续递增较早的组
- "Normalize" the groups by moving all that is too large from the right to the left, leaving only the maximum value at the right.
- Output the solution
- Repeat:
- Add 1 to the penultimate group
- This can carry to the left if a group gets too large (e.g.999+1 is too large)
- Check whether the result didn't get too large (a[0] should be able to absorb what was added)
- If the result got too large, set the group to zero and continue incrementing the earlier groups
一些用于说明的Python代码:
Some Python code for illustration:
x = 1234 grouping = 3 max_iterations = 200 max_in_group = 10**grouping - 1 a = [x] while max_iterations > 0: #step 1: while a[0] is too large: redistribute to the left i = 0 while a[i] > max_in_group: if i == len(a) - 1: a.append(0) a[i + 1] += a[i] - max_in_group a[i] = max_in_group i += 1 num = sum(10**(grouping*i) * a[i] for i, n in enumerate(a)) print(f"{num} {num:,}") # print("".join([str(t) for t in a[::-1]]), ",".join([str(t) for t in a[::-1]])) # step 2: add one to the penultimate group, while group already full: set to 0 and increment the # group left of it; # while the surplus is too large (because a[0] is too small) repeat the incrementing i0 = 1 surplus = 0 while True: # needs to be executed at least once, and repeated if the surplus became too large i = i0 while True: # increment a[i] by 1, which can carry to the left if i == len(a): a.append(1) surplus += 1 break else: if a[i] == max_in_group: a[i] = 0 surplus -= max_in_group i += 1 else: a[i] += 1 surplus += 1 break if a[0] >= surplus: break else: surplus -= a[i0] a[i0] = 0 i0 += 1 #step 3: a[0] should absorb the surplus created in step 1, although a[0] can get out of bounds a[0] -= surplus surplus = 0 max_iterations -= 1缩写输出:
235,999 236,998 ... 998,236 999,235 ... 1,234,999 1,235,998 ... 1,998,235 1,999,234 2,233,999 2,234,998 ...grouping=3和x=3456的输出:459,999,999,999 460,998,999,999 460,999,998,999 460,999,999,998 461,997,999,999 461,998,998,999 461,998,999,998 461,999,997,999 461,999,998,998 461,999,999,997 462,996,999,999 ...grouping=1和x=16的输出:79 88 97 169 178 187 196 259 268 277 286 295 349 358 367 376 385 394 439 448 457 466 475 484 493 529 538 547 556 565 574 583 592 619 628 637 646 655 664 673 682 691 709 718 727 736 745 754 763 772 781 790 808 817 826 835 844 853 862 871 880 907 916 925 934 943 952 961 970 1069 1078 1087 1096 1159 1168 1177 1186 1195 1249 1258 1267 1276 1285 1294 1339 1348 1357 1366 1375 1384 1393 1429 1438 1447 1456 1465 1474 1483 1492 1519 1528 1537 1546 1555 1564 1573 1582 1591 1609 1618 1627 1636 1645 1654 1663 1672 1681 1690 1708 1717 1726 1735 1744 1753 1762 1771 1780 1807 1816 1825 1834 1843 1852 1861 1870 1906 1915 1924 1933 1942 1951 1960 2059 2068 2077 2086 2095 2149 2158 2167 2176 2185 2194 2239 2248 2257 2266 2275 2284 2293 2329 2338 2347 2356 2365 2374 2383 2392 2419 2428 2437 2446 2455 2464 2473 2482 2491 2509 2518 2527 2536 2545 2554 2563 2572 2581 2590 2608 2617 2626 2635 2644 2653 2662 2671 2680 2707 2716 2725 2734 ...这篇关于以词法顺序查找成千上万个合计为给定数字的组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
