找到滿足特定條件的數字的優化方式

我在某處看到了這個問題。有一個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

找到滿足特定條件的數字的優化方式

回答

相關問題