寻找符合特定条件的数字的最优方法

Question

我在某处看到了这个问题。给定一个8位数字，从左到右第一位表示数字中有多少个0，第二位表示数字中有多少个1，第三位表示数字中有多少个2，以此类推，直到第8位表示数字中有多少个7。请找出这个数字。我用Python写了一段代码来查找数字。除了上述条件之外，我还增加了一些额外的检查，例如“数字各位数之和应为8”和“数字中不应包含8或9”。以下是我粘贴的代码。这只是暴力搜索，因为我要检查每个数字是否符合条件。我很好奇是否有更好的解决方法

def returnStat(number, digit, count):
    number = str(number)    
    digit = str(digit)
    print "Analysing for ",digit," to see if it appears ",count, " times in ",number,"."        
    actCnt = number.count(digit)
    count = str(count)
    actCnt = str(actCnt)
    if (actCnt == count):
        return 1
    else:
        return 0

def validateNum(number):
    numList = str(number)
    if '8' in numList:
        print "Skipping ",number, " since it has 8 in it"
        return (-1)
    elif '9' in numList:
        print "Skipping ",number, " since it has 9 in it"
        return (-1)
    elif (sum(int(digit) for digit in numList) != 8):
        print "Skipping ",number, " since its sum is not equal to 8"
        return (-1)
    index = 0
    flag = 0
    for num in numList:
        if (returnStat(number,index,num)) :
            index = index+1
            continue
        else:
            flag = 1
            break 
if (flag == 1):
    return (-1)
else:
    return number

for num in range(0,80000000):
number = '{number:0{width}d}'.format(width=8,number=num)

desiredNum = "-1"
desiredNum = validateNum(number)
if (desiredNum == -1):
    print number," does not satisfy all "
    continue
else:
    print "The number that satisfies all contition is ",number
    break

- Ani

---

完整、可运行的代码如果您有兴趣改进，应该发布在 Code Review 而不是 Stack Overflow 上。 - TigerhawkT3

我也很愿意学习不同的解决方案。我并不只是寻求答案来改进我的解决方案。 - Ani

Answer 1

你不仅仅可以说8或9的数字是不可能的。

最后一位数字会比0更大吗？答案是否定的。如果最后一位数字是1，这意味着其他位置上至少有一个7。然而，如果有一个7，那就意味着同样的数字出现了7次。显然这是不可能的。因此，最后一位数字必须是0。

所以我们有xxxxxxx0。

那么倒数第二个数字呢？

如果是xxxxxx10，则必须至少有一个6，这意味着同样的数字出现了6次。我们可以尝试60000010，但这是错误的，因为有一个1，在第二位应该反映出来。倒数第二位数字不能高于1，因为2表示有2个六，这又意味着一个数字出现了6次，而另一个数字也出现了6次，这是不可能的。

所以我们有xxxxxx00。

如果是xxxxx100，则必须至少有一个5，这意味着同样的数字出现了5次。让我们从51000100开始尝试。几乎没错，但现在有两个1。所以应该是52000100。但等等，现在只有一个1和一个2。所以我们尝试52100100。但现在我们只有4个0。我们不能有xxxxx200，因为这意味着有2个5，正如上面解释的那样是不可能的。

所以我们有xxxxx000。

如果是xxxx1000，我们可以尝试40001000，错了；41001000，也错了；42101000。

啊哈，就是它。42101000。

- wookie919

Answer 2

即使您遍历所有不包含8或9的8位数字，可选项也不多（实际上，8^8 = 1<<24 ~= 1700万）。

以下是一个尝试这些数字的天真程序：

import itertools

for digs in itertools.product(range(8), repeat=8):
    counts = [0] * 8
    for d in digs:
        counts[d] += 1
    if counts == list(digs):
        print digs

这段代码在我的机器上完成（恰好一个解）需要15秒。

为了加快速度，您可以只考虑数字位数为8且各位数字之和为8的情况。以下是与之前相同的代码，但现在使用sum_k生成可能性。（sum_k（n，k）生成所有数字位数为n且所有数字小于8且它们的和为k的元组）

def sum_k(n, k):
    if k < 0 or n * 7 < k: return
    if n == 1:
        yield k,
        return
    for d in xrange(8):
        for s in sum_k(n-1, k-d):
            yield (d,) + s

for digs in sum_k(8, 8):
    counts = [0] * 8
    for d in digs:
        counts[d] += 1
    if counts == list(digs):
        print digs

这段代码在我的机器上完成时间为0.022秒。

将代码适应于解决一般情况会产生以下解决方案：

1210
2020
21200
3211000
42101000
521001000
6210001000
72100001000
821000001000
9210000001000

- Paul Hankin

---

即使我在代码中检查了“sum”条件，但需要超过一分钟才能找到。可能是因为条件在循环内部。但这很酷。 - Ani