If I understand the specifications correctly, you wish to randomly generate restricted integer compositions such that each possible composition has an equal likelihood of being chosen.
We can adapt this answer to the problem of uniformly generating a random integer partition to solve this problem exactly for small input values. We simply need a way to count restricted k-compositions. There's a recursive formulation in this answer on Mathematics to a related problem, but it turns out that there is a more explicit formula mentioned as part of this answer that uses binomial coefficients. Here's a implementation in pure Python:
import functools
import random
@functools.lru_cache(1 << 10)
def C1(n, k, a, b):
"Counts the compositions of `n` into `k` parts bounded by `a` and `b`"
return C2(n - k*(a - 1), k, b - (a - 1))
def C2(n, k, b):
"Computes C(n, k, 1, b) using binomial coefficients"
total = 0
sign = +1
for i in range(0, k + 1):
total += sign * choose(k, i) * choose(n - i*b - 1, k - 1)
sign = -sign
return total
def choose(n, k):
"Computes the binomial coefficient of (n, k)"
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
k = min(k, n - k)
c = 1
for i in range(k):
c = c * (n - i) // (i + 1)
return c
def check_pre_and_post_conditions(f):
def wrapper(n, k, a, b):
assert 1 <= k <= n, (n, k)
assert 1 <= a <= b <= n, (n, a, b)
assert k*a <= n <= k*b, (n, k, a, b)
comp = f(n, k, a, b)
assert len(comp) == k, (len(comp), k, comp)
assert sum(comp) == n, (sum(comp), n, comp)
assert all(a <= x <= b for x in comp), (a, b, comp)
return comp
return functools.wraps(f)(wrapper)
@check_pre_and_post_conditions
def random_restricted_composition(n, k, a, b):
"Produces a random composition of `n` into `k` parts bounded by `a` and `b`"
total = C1(n, k, a, b)
which = random.randrange(total)
comp = []
while k:
for x in range(a, min(b, n) + 1):
count = C1(n - x, k - 1, a, b)
if count > which:
break
which -= count
comp.append(x)
n -= x
k -= 1
return comp
To select a random composition, we simply generate a random index smaller than the total number of possible compositions, and then construct the i-th lexicographic composition (see the linked questions for explanations of the recurrence relations used). This should produce all possible outcomes with equal probability.
However, because C1(n, k, a, b) grows exponentially, this method is pretty slow for large values of n and k. For large values, an approximate solution will serve you better.
