找到满足特定条件的数字的优化方式

我在某处看到了这个问题。有一个8位数字。从左到右的第一个数字表示数字中有多少个零。第二位数字告诉你号码中有多少个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

来源

2015-04-22 Ani

完成，工作是你有意改善自己所属的代码审查代码，而不是堆栈溢出。 – TigerhawkT3

我很乐意学习不同的解决方案。我不只是寻找解决方案来改进我的解决方案。 – Ani

即使您遍历所有8位数字，其中没有8或9，也没有多少可能（实际上，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)生成全部数字小于8的所有n-数字元组，其总和为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

来源

2015-04-23 04:58:28

即使我检查我的代码上的“总和”条件，但需要一分多钟才能找到。也许是因为条件在循环内。但这很酷。 – Ani

你可以走得更远，而不是单纯的没有更好的办法说是8或9位数字是不可能的。

最后一位数字是否可以大于0？答案是不。如果最后一位数字是1，这意味着在其他地方有一个7。但是，如果有7个，则意味着相同的数字发生了7次。这显然是不可能的。因此最后一位必须是0.

所以我们有xxxxxxx0。

倒数第二位数字怎么样？

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

所以我们有xxxxxx00。

如果为xxxxx100，则必须至少有一个5，表示同一个数字出现5次。让我们从51000100开始。几乎，现在有2个1。所以它应该是52000100.但是等等，现在有一个1.和一个2.所以我们尝试52100100.但是现在我们只有4个0。我们不能有xxxxx200，因为这意味着有2个5s，这是不可能的，如上所述。

所以我们有xxxxx000。

如果xxxx1000，我们可以尝试40001000，不，41001000，不，42101000.

啊它就在那里。 42101000.

来源

2015-04-23 04:17:04 wookie919

找到满足特定条件的数字的优化方式

回答

相关问题