如何在一定范围内找到不同数字集合的数字？涉及IT技术。

Question

假设我有一个无符号整数，称之为low，另一个称之为high，使得high>low。 问题是在此范围内找到不同的数字集合。 例如，假设low是1，high是20，那么答案是20，因为在这个范围内的所有数字都具有不同的数字集合。如果假设low是1，high是21，则答案是20，因为12和21具有相同的数字集合，即1、2。我不是在寻找暴力算法，如果有人有比通常的暴力方法更好的解决方案，请告诉我...

- evil.coder

---

你究竟在寻找什么？在区间[low,n]中所有数字都具有不同位数的情况下，最大的n<=high？还是你想要[low,high]的任意子集具有这种性质的最大大小？或者是其他什么？ - Doc Brown

我希望在低位和高位之间精确地计算这些数字的数量。 - evil.coder

你是想要算法还是代码来完成这个任务？ - ChrisBD

也许再举一个例子会更清楚。拿一个例子，low=121，high=321。暴力方法是从121开始，并消除在low和high之间具有相同数字集（仅211）的数字。下一个是122，可能的淘汰者是221、212。接下来是123，然后是132、213、231、312、321不被计算。显然，12和122是不同的集合，因为一个包含2个数字，另一个包含3个数字。 - evil.coder

答案是这些数字的数量。 - evil.coder

Answer 1

显然，对于这个问题有一个数学答案，虽然我承认我还没有算出来。

简单地说，如果low = 1且high = 99，则我们有以下情况：

0 - 9 = 10 unique numbers
10-19 = 10 unique numbers
20-29 = 9 unique numbers
30-31 = 8 unique numbers
40-49 = 7 unique numbers
50-59 = 6 unique numbers
60-69 = 5 unique numbers
70-79 = 4 unique numbers
80-89 = 3 unique numbers
90-99 = 2 unique numbers

也许我们可以假设所有数字都必须具有相同的位数，需要时补0以保持一致。例如，用01、02、03、04代替1、2、3、4。这意味着01和10将匹配。 然后，我们的数字分布就变成了：

0 - 9 = 10 unique numbers
10-19 = 9 unique numbers
20-29 = 8 unique numbers
30-31 = 7 unique numbers
40-49 = 6 unique numbers
50-59 = 5 unique numbers
60-69 = 4 unique numbers
70-79 = 3 unique numbers
80-89 = 2 unique numbers
90-99 = 1 unique numbers

你可以看到，使用10的因子确定可能存在多少个唯一数字，应该可以基于此建立一个递归公式。困难在于如何处理起始和结束点是可变的，例如低=25和高=87。不过这是一个开端，我会进一步思考。

- ChrisBD

---

你的例子很奇怪。我认为你搞错了范围。 10-19 = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19}，这给出了10个独特的数字。你是不是想说 0-19 只比 0-9 多了 9 个数字？ - Matthieu M.

@Matthieu - 在第二个例子中，我建议我们包括一个前导零。因此，01和10是相同的。 - ChrisBD

Answer 2

我想我终于理解了这个问题。

让我们取范围 [low,high] 并根据它们的数字将这个范围内的数字放入集合中，如下所示：

• "121" --> 集合 "112"
• "122" --> 集合 "122"
• "211" --> 集合 "112"

我们想知道包含唯一元素的集合数量。

我建议最简单的方法是...像这样做。

def rangeCount(low, high):
  sets = defaultdict(list)
  for i in range(low, high+1):
    key = `i`.sort()            # obtain digits and sort them
    sets[key].append(i)

  count = 0
  for v in sets.values():
    if len(v) == 1: count = count + 1
  return count

好的，这是暴力破解，但至少现在每个人都应该在同一页上了 :)

- Matthieu M.

---

我已经实现了这个，但是如果范围是1到10亿怎么办？有多少个集合？我期望有人能发现其中的任何数学序列。 - evil.coder

他们可以这样做，我只是把它写下来，这样任何试图测试其结果的其他人都会更容易。 - Matthieu M.

谢谢Matthieu，现在我更好地理解问题了（但到目前为止我还不知道如何将复杂度降至O（高—低））。 - Doc Brown

Answer 3

也许这会帮助你入门： 数学组合

http://www.codeguru.com/cpp/cpp/algorithms/combinations/article.php/c5117

- Tom

---

我不认为这会有帮助。如果它走在正确的路上，我想知道怎么做？ - evil.coder

你是在寻找算法还是代码来完成这个任务？哎呀抱歉，我评论错地方了。 - ChrisBD