阿姆斯特朗/纳西西斯数字基数16/十六进制

Question

目标是什么

我的目标是找到给定数字量的所有armstrong/narcisstic十六进制数

基本思想

基本思想是，对于一组数字，例如[a，3，F，5]，幂和总是相同的，无论它们出现的顺序如何。这意味着我们不必考虑每一个可能的最大值，这将大大减少运行时间

到目前为止我所拥有的

# Armstrong numbers base 16 for n digits

import time
import itertools
from typing import Counter

pows = [[]]

def genPow(max, base):
    global pows
    pows = [[0]*1 for i in range(base)]
    for i in range(base):
        pows[i][0] = i ** max

def check(a, b):
    c1 = Counter(a)
    c2 = Counter(b)

    diff1 = c1-c2
    diff2 = c2-c1

    # Check if elements in both 'sets' are equal in occurence
    return (diff1 == diff2)

def armstrong(digits):
    results = []
    genPow(digits, 16)
    # Generate all combinations without consideration of order
    for set in itertools.combinations_with_replacement('0123456789abcdef', digits):
        sum = 0
        # Genereate sum for every 'digit' in the set
        for digit in set:
            sum = sum + pows[int(digit, 16)][0] 
        # Convert to hex
        hexsum = format(sum, 'x')
        # No point in comparing if the length isn't the same
        if len(hexsum) == len(set):
            if check(hexsum, set):
                results.append(hexsum)

    return sorted(results)

start_time = time.time()
print(armstrong(10))
print("--- %s seconds ---" % (time.time() - start_time))

我的问题

我的问题是，这仍然相当缓慢。10位数字最多需要60秒。我相信有很多方法可以更有效地做到这一点。有些事情我能想到，但不知道怎么做：生成组合的更快方法，停止求和计算的条件，比较求和和和集合的更好方法，比较后转换为十六进制

有没有办法优化这个

Edit:我尝试以不同的方式进行比较/检查，这样已经快了一点https://gist.github.com/Claypaenguin/d657c4413b510be580c1bbe3e7872624与此同时，我试图理解递归方法，因为它看起来会快得多

Answer 1

您的问题是combinations_with_replacement对于base b和length l返回(b+l choose b)不同的东西。在你的例子中（基数16，长度10）意味着你有5311735个组合

然后对每一个进行重量级计算

您需要做的是在创建组合时过滤所创建的组合。一旦你意识到你不在通往阿姆斯特朗号码的路上，就放弃这条路。计算看起来会更复杂，但当它允许您跳过整个组合块而不必单独生成它们时，这是值得的

以下是该技术核心的伪代码：

# recursive search for Armstrong numbers with:
#
#   base = base of desired number
#   length = length of desired number
#   known_digits = already chosen digits (not in order)
#   max_digit = the largest digit we are allowed to add
#
# The base case is that we are past or at a solution.
#
# The recursive cases are that we lower max_digit, or add max_digit to known_digits.
#
# When we add max_digit we compute min/max sums.  Looking at those we
# stop searching if our min_sum is too big or our max_sum is too small.
# We then look for leading digits in common.  This may let us discover
# more digits that we need.  (And if they are too big, we can't do that.)
def search(base, length, known_digits, max_digit):
    digits = known_digits.copy() # Be sure we do not modify the original.
    answer = []
    if length < len(digits):
        # We can't have any solutions.
        return []
    elif length == len(digits):
        if digits is a solution:
            return [digits]
        else:
            return []
    elif 0 < max_digit:
        answer = search(base, length, digits, max_digit-1)
    digits.append(max_digit)

    # We now have some answers, and known_digits.  Can we find more?
    find min_sum (all remaining digits are 0)
    if min_sum < base**(length-1):
        min_sum = base**(length-1)

    find max_sum (all remaining digits are max_digit)
    if base**length <= max_sum:
        max_sum = base**length - 1
     
    # Is there a possible answer between them?
    if max_sum < base**(length-1) or base**length <= min_sum:
        return answer # can't add more
    else:
        min_sum_digits = base_digits(min_sum, base)
        max_sum_digits = base_digits(max_sum, base)
        common_leading_digits = what digits are in common?
        new_digits = what digits in common_leading_digits can't be found in our known_digits?
        if 0 == len(new_digits):
            return answer + search(base, length, digits, max_digit)
        elif max_digit < max(new_digits):
            # Can't add this digit
            return answer
        else:
            digits.extend(new_digits)
            return answer + search(base, length, digits, max_digit)

---

我有一个小的逻辑错误，但下面是工作代码：

def in_base (n, b):
    answer = []
    while 0 < n:
        answer.append(n % b)
        n = n // b
    return answer


def powers (b, length, cached={}):
    if (b, length) not in cached:
        answer = []
        for i in range(b):
            answer.append(i**length)
        cached[(b, length)] = answer
    return cached[(b, length)]

def multiset_minus (a, b):
    count_a = {}
    for x in a:
        if x not in count_a:
            count_a[x] = 1
        else:
            count_a[x] += 1
    minus_b = []
    for x in b:
        if x in count_a:
            if 1 == count_a[x]:
                count_a.pop(x)
            else:
                count_a[x] -= 1
        else:
            minus_b.append(x)
    return minus_b


def armstrong_search (length, b, max_digit=None, known=None):
    if max_digit is None:
        max_digit = b-1
    elif max_digit < 0:
        return []

    if known is None:
        known = []
    else:
        known = known.copy() # Be sure not to accidentally share

    if len(known) == length:
        base_rep = in_base(sum([powers(b,length)[x] for x in known]), b)
        if 0 == len(multiset_minus(known, base_rep)):
            return [(base_rep)]
        else:
            return []
    elif length < len(known):
        return []
    else:
        min_sum = sum([powers(b,length)[x] for x in known])
        max_sum = min_sum + (length - len(known)) * powers(b,length)[max_digit]

        if min_sum < b**(length-1):
            min_sum = b**(length-1)
        elif b**length < min_sum:
            return []

        if b**length < max_sum:
            max_sum = b**length - 1
        elif max_sum < b**(length-1):
            return []

        min_sum_rep = in_base(min_sum, b)
        max_sum_rep = in_base(max_sum, b)

        common_digits = []
        for i in range(length-1, -1, -1):
            if min_sum_rep[i] == max_sum_rep[i]:
                common_digits.append(min_sum_rep[i])
            else:
                break

        new_digits = multiset_minus(known, common_digits)
        if 0 == len(new_digits):
            answers = armstrong_search(length, b, max_digit-1, known)
            known.append(max_digit)
            answers.extend(armstrong_search(length, b, max_digit, known))
            return answers
        else:
            known.extend(new_digits)
            return armstrong_search(length, b, max_digit, known)

举个简单的例子：

digits = list('0123456789abcdef')
print([''.join(reversed([digits[i] for i in x])) for x in armstrong_search(10, len(digits))])

需要2秒钟多一点的时间才能找到唯一的答案是bcc6926afe

Answer 2

由于itertools的组合将以升序返回数字，因此使用其数字的排序列表比较幂和将更有效：

这是一个通用的自恋数字生成器，它使用这种比较模式：

import string
import itertools
def narcissic(base=10,startSize=1,endSize=None):
    baseDigits = string.digits+string.ascii_uppercase+string.ascii_lowercase
    if not endSize:
        endSize  = 1
        while (base/(base-1))**(endSize+1) < base*(endSize+1): endSize += 1

    def getDigits(N):
        result = []
        while N:
            N,digit = divmod(N,base)
            result.append(digit)
        return result[::-1]

    yield (0,"0")
    allDigits = [*range(base)]
    for size in range(startSize,endSize):
        powers = [i**size for i in range(base)]
        for digits in itertools.combinations_with_replacement(allDigits, size):
            number    = sum(powers[d] for d in digits)
            numDigits = getDigits(number)
            if digits == tuple(sorted(numDigits)):
                baseNumber = "".join(baseDigits[d] for d in numDigits)
                yield number, baseNumber

输出：

for i,(n,bn) in enumerate(narcissic(5)): print(i+1,":",n," >",bn)    

1 : 0  > 0
2 : 1  > 1
3 : 2  > 2
4 : 3  > 3
5 : 4  > 4
6 : 13  > 23
7 : 18  > 33
8 : 28  > 103
9 : 118  > 433
10 : 353  > 2403
11 : 289  > 2124
12 : 419  > 3134
13 : 4890  > 124030
14 : 4891  > 124031
15 : 9113  > 242423
16 : 1874374  > 434434444
17 : 338749352  > 1143204434402
18 : 2415951874  > 14421440424444    

使用timeit来比较性能，我们的速度提高了3.5倍：

from timeit import timeit        

t = timeit(lambda:list(narcissic(16,10,11)),number=1)
print("narcissic",t) # 11.006802322999999

t = timeit(lambda:armstrong(10),number=1)
print("armstrong:",t) # 40.324530023

请注意，处理时间随着每个新大小呈指数增长，因此仅3.5倍的速度提升将没有意义，因为它只会将问题推到下一个大小