按词汇顺序查找总和为给定数字的数千组
Find groups of thousands which sum to a given number, in lexical order
大量数字可以采用逗号格式，以便更轻松地分成三个一组来阅读。例如。 1050 = 1,050 和 10200 = 10,200.
每组三人的总和为：
1050=1,050 给出：1+50=51
10200=10,200 给出：10+200=210
我需要在三人组的总和中搜索匹配项。
也就是说，如果我正在搜索 1234，那么我正在寻找其三和为 = 1234.
的数字
自 235+999=1234 以来，最小匹配是 235,999。没有其他小于 235,999 的整数给出等于 1234 的三和。
自 236+998=1234 以来，下一个最小匹配项是 236,998。
每次都可以加999，但是加到999后就失败了，因为999溢出，多了一个数字1。
More generally, I am asking for the solutions (smallest to highest) to:
a+b+c+d… = x
where a,b,c,d… is an arbitrary number of integers between 0-999 and x
is a fixed integer
请注意，对于任何正整数 x，此问题都有无限解。
如何从最小数量的解决方案开始解决这个问题（对于 y 数量的解决方案，其中 y 可以是任意大的数字）？
有没有一种方法可以做到这一点，而无需一个一个地强制循环？我正在处理可能非常大的数字，这可能需要数年才能直接循环。理想情况下，应该在没有失败尝试的情况下执行此操作。
如果您一次只考虑 1 位数字而不是 3 位数字组，那么问题更容易思考。
一个算法：
首先用x填充0位数字组。
创建一个循环，每次打印下一个解决方案。
- "Normalize" 通过将所有太大的值从右边移到左边来分组，只在右边留下最大值。
- 输出解
- 重复：
- 倒数第二组加1
- 如果组太大（例如 999+1 太大），这可以向左进位
- 检查结果是否没有太大（a[0]应该可以吸收添加的内容）
- 如果结果太大，将组设置为零并继续递增前面的组
- 计算最后一组吸收剩余（可正可负）
部分Python代码说明：
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 ...
大量数字可以采用逗号格式，以便更轻松地分成三个一组来阅读。例如。 1050 = 1,050 和 10200 = 10,200.
每组三人的总和为：
1050=1,050 给出：1+50=51
10200=10,200 给出：10+200=210
我需要在三人组的总和中搜索匹配项。
也就是说，如果我正在搜索 1234，那么我正在寻找其三和为 = 1234.
自 235+999=1234 以来，最小匹配是 235,999。没有其他小于 235,999 的整数给出等于 1234 的三和。
自 236+998=1234 以来，下一个最小匹配项是 236,998。
每次都可以加999，但是加到999后就失败了，因为999溢出，多了一个数字1。
More generally, I am asking for the solutions (smallest to highest) to:
a+b+c+d… = x
where a,b,c,d… is an arbitrary number of integers between 0-999 and x is a fixed integer
请注意，对于任何正整数 x，此问题都有无限解。
如何从最小数量的解决方案开始解决这个问题（对于 y 数量的解决方案，其中 y 可以是任意大的数字）？
有没有一种方法可以做到这一点，而无需一个一个地强制循环？我正在处理可能非常大的数字，这可能需要数年才能直接循环。理想情况下，应该在没有失败尝试的情况下执行此操作。
如果您一次只考虑 1 位数字而不是 3 位数字组，那么问题更容易思考。
一个算法：
首先用x填充0位数字组。
创建一个循环，每次打印下一个解决方案。
- "Normalize" 通过将所有太大的值从右边移到左边来分组，只在右边留下最大值。
- 输出解
- 重复：
- 倒数第二组加1
- 如果组太大（例如 999+1 太大），这可以向左进位
- 检查结果是否没有太大（a[0]应该可以吸收添加的内容）
- 如果结果太大，将组设置为零并继续递增前面的组
- 计算最后一组吸收剩余（可正可负）
部分Python代码说明：
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 ...