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