Find all numbers whose digit counts are in descending order

Question

Give a base b and a length n, I'd like to find through all integers in base b, with leading zeroes to reach length n, that satisfy:

For digits i and j, if i < j then the count of i's is >= the count of j's.

E.g., base 3, length 4:

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

My current approach is to increment through all integers in the range in base 10, convert to base b, count digits, and reject if the digit counts fail our criterion. This is slow.

I think the language I'm using is irrelevant but if it matters, it's Rust.

Answer 1

This problem is equivalent to generating integer partitions of value n into b parts, then using every partition elements as counts of digits and applying permutations (last stage alike Shridhar R Kulkarni approach, but another combinatorial object is used)

For n=7 and b=4 some intermediate parition of 7 into 4 parts is [3, 2, 2, 0] that denotes digit combination [0, 0, 0, 1, 1, 2, 2], then we permute the last one in lexicographic order. partitions function provides non-increasing parts order, so if i < j then the count of i's is >= the count of j's. condition is fulfilled.

Ideone code to play with.

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, [])

result

[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]

Answer 2

When base = 3 and length = 4, the answer would be

['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']

We can observe that all the numbers in the answer would be permutations of ['0000', '0001', '0011', '0012', '1111', '1112', '1122', '2222']. Let us call them unique_numbers.

So, our solution is easy and simple. Generate all the unique_numbers and add their permutations to the 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

This problem can be solved with dynamic programming. Here is one approach (using 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

   

The key function is count_helper(base, length, max_repeats) that counts the number of valid sequences s.t. the most common digit does not repeat more than max_repeats times. Ignoring the base case, this function satisfies a recurrence relation:

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

At this point, we are deciding how many copies of digit base to insert into the sequence. We can choose any number k between 0 and max_repeats inclusive. For a given, value of k, there are length choose k ways to insert the digit we are adding. Each choice of k leads to a recursive call to a subproblem where base is reduced by 1, length is reduced by k and max_repeats is set to k.