python - 基数为 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 秒。我很确定有办法更有效地做到这一点。我能想到但不知道该怎么做的一些事情是:生成组合的更快方法，停止计算的条件。总和，比较总和和集合的更好方法，比较后转换为十六进制
任何想法如何优化这个？
编辑: 我试图比较/检查有点不同，它已经有点快了 https://gist.github.com/Claypaenguin/d657c4413b510be580c1bbe3e7872624 同时我试图理解递归方法，因为它看起来会快很多。

Answer 1

您的问题是基本 combinations_with_replacement 和长度 b 的 l 返回 (b+l choose b) 不同的东西。在您的情况下(基数为 16，长度为 10)意味着您有 5,311,735 个组合。
然后您对每个进行重量级计算。
您需要做的是在创建组合时过滤您正在创建的组合。一旦你意识到你不是在通往阿姆斯特朗数字的路上，就放弃这条路。计算看起来更复杂，但当它让您跳过整个组合块而不必单独生成它们时，它是值得的。
这是该技术核心的伪代码:

# 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 。