查找所有位数按降序排列的数字

Question

给定一个基数 b 和一个长度 n，我想找到基数 b 中的所有整数，前导零达到长度 n ，满足：

对于数字 i 和 j，如果 i < j 则 i 的计数 >= j 的计数。

例如，基数 3，长度 4：

0000, 0001, 0010, 0011, 0012, 0021, 0100, 
0101, 0102, 0110, 0120, 0201, 0210  1000, 
1001, 1002, 1010, 1020, 1100, 1200, 2001, 
2010, 2100

我目前的方法是以 10 为基数递增范围内的所有整数，转换为基数 b，计算数字，如果数字计数不符合我们的标准，则拒绝。这很慢。

我认为我使用的语言无关紧要，但如果重要的话，那就是 Rust。

Answer 1

这道题可以用动态规划求解。这是一种方法（使用 Python）：

from functools import lru_cache
from collections import Counter
from itertools import product

def naive(base, length):
  result = 0
  for tup in product(range(base), repeat=length):
    ctr = Counter(tup)
    is_valid = all(ctr[i] >= ctr[i+1] for i in range(base))
    if is_valid:
      result += 1
  return result

@lru_cache(None)
def binom(n, k):
  # compute binomial coefficient
  if n == 0:
    if k == 0:
      return 1
    else:
      return 0
  return binom(n - 1, k) + binom(n - 1, k - 1)
  
def count_seq(base, length):
  @lru_cache(None)
  def count_helper(base, length, max_repeats):
    if base < 0 or length < 0:
      return 0
    elif length == 0:
      return 1
    return sum(binom(length, k) * count_helper(base - 1, length - k, k) 
      for k in range(max_repeats+1))

  return count_helper(base, length, length)

assert all(count_seq(base, length) == naive(base, length)
        for base in range(7) for length in range(7))
print(count_seq(100, 60))
#21047749425803338154212116084613212619618570995864645505458031212645031666717071397

关键函数是count_helper(base, length, max_repeats)，统计有效序列的数量s.t。最常见的数字重复不超过 max_repeats 次。忽略基本情况，此函数满足递推关系：

count_helper(base, length, max_repeats) = sum(
      binom(length, k) * count_helper(base - 1, length - k, k) 
      for k in range(max_repeats+1))

此时，我们正在决定将多少个数字 base 插入到序列中。我们可以选择 0 和 max_repeats 之间的任意数字 k（含）。对于给定的值 k，有 length choose k 种方法来插入我们要添加的数字。 k 的每个选择都会导致对子问题的递归调用，其中基数减少 1，长度减少 k 并且 max_repeats 设置为 k .

Answer 2

当base = 3 和length = 4 时，答案是

['0000', '0001', '0010', '0011', '0012', '0021', '0100', '0101', '0102', '0110', '0120', '0201', '0210', '1000', '1001', '1002', '1010', '1020', '1100', '1111', '1112', '1121', '1122', '1200 ', '1211', '1212', '1221', '2001', '2010', '2100', '2111', '2112', '2121', '2211', '2222']

我们可以观察到答案中的所有数字都是 ['0000', '0001', '0011', '0012', '1111', '1112', '1122', '2222 '].让我们称他们为 unique_numbers.

因此，我们的解决方案简单易行。生成所有 unique_numbers 并将它们的排列添加到 result.

from itertools import permutations

base = 3
length = 4
unique_numbers = []

def getUniqueNumbers(curr_digit, curr_count, max_count, curr_num):
    
    #Add the curr_num to unique_numbers 
    if len(curr_num) == length:
        unique_numbers.append(curr_num)
        return
    
    #Try to include the curr_digit again
    if curr_count + 1 <= max_count:
        getUniqueNumbers(curr_digit, curr_count + 1, max_count, curr_num + str(curr_digit))
    
    #Try to include the next digit
    if curr_digit + 1 < base:
        getUniqueNumbers(curr_digit+1, 1, curr_count, curr_num + str(curr_digit+1))

#Try generating unique numbers starting with every digit
for i in range(base):
    getUniqueNumbers(i, 0, length, "")

result = set()
for num in unique_numbers:
    permList = permutations(num) 
    for perm in list(permList):
        result.add(''.join(perm))

print(result)

Answer 3

这个问题相当于将值 n 的整数分区生成为 b 部分，然后使用每个分区元素作为数字计数并应用排列（最后阶段类似于 Shridhar R Kulkarni 方法，但是使用了另一个组合对象)

对于n=7和b=4，7到4部分的一些中间分割是[3, 2, 2, 0]，表示数字组合[0, 0, 0, 1, 1, 2, 2]，然后我们按字典顺序排列最后一个。 partitions函数提供了非递增零件订单，所以if i < j then the count of i's is >= the count of j's.条件满足。

Ideone code一起玩

def next_permutation(arr):
    #https://www.nayuki.io/page/next-lexicographical-permutation-algorithm
    i = len(arr) - 1
    while i > 0 and arr[i - 1] >= arr[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(arr) - 1
    while arr[j] <= arr[i - 1]:
        j -= 1
    arr[i - 1], arr[j] = arr[j], arr[i - 1]
    arr[i : ] = arr[len(arr) - 1 : i - 1 : -1]
    return True

def partitions(Sum, K, lst, Minn = 0):
    if K == 0:
        if Sum == 0:
            #print(lst)   [3, 1, 0] denotes three zeros and one 1
            arr = []
            for i in range(len(lst)):
                if lst[i]:
                    arr.extend([i]*lst[i])
                     #transform [3, 1, 0] to [0,0,0,1]

            print(arr)
            while next_permutation(arr):
                print(arr)
        return
    for i in range(Minn, min(Sum + 1, Sum + 1)):
        partitions(Sum - i, K - 1, [i] + lst, i)

b = 3
n = 4
partitions(n, b, [])

结果

[0, 0, 0, 0]    [0, 0, 0, 1]    [0, 0, 1, 0]    [0, 1, 0, 0]
[1, 0, 0, 0]    [0, 0, 1, 1]    [0, 1, 0, 1]    [0, 1, 1, 0]
[1, 0, 0, 1]    [1, 0, 1, 0]    [1, 1, 0, 0]    [0, 0, 1, 2]
[0, 0, 2, 1]    [0, 1, 0, 2]    [0, 1, 2, 0]    [0, 2, 0, 1]
[0, 2, 1, 0]    [1, 0, 0, 2]    [1, 0, 2, 0]    [1, 2, 0, 0]
[2, 0, 0, 1]    [2, 0, 1, 0]    [2, 1, 0, 0]

查找所有位数按降序排列的数字

Find all numbers whose digit counts are in descending order

algorithm

math

permutation