Uniform generation of permutation with repetition at most k times?

We have set {1, 2, 3, ...,n} of numbers. We want to generate permutation of length of m created of those numbers with repetition of each number at most $k$ times.

If we assume n=5, k=2, m=3, then we could receive: {3,3,1}, but not {3, 3, 3} as 3 in the second example happens to be three times in output, which is more than k.

Is there a way of uniform generation of such permutation in a fast way?

I tried two different solutions.

First:

1) generate random permutation with repetition, there is n^m different permutations.

2) check if this is a correct permutation (if it does not contain more than k times the same number

3) if yes, then return, else go to 1)

Python snippet:

import numba
import numpy as np


@numba.jit(nopython=True)
def gen_sequence1(n, k, m):
    result = np.random.randint(0, n, (1, m))[0]
    while not is_correct(result, k):
        result = np.random.randint(0, n, (1, m))[0]
    return result


@numba.jit(nopython=True)
def most_frequent(iter):
    return np.bincount(iter).max()


@numba.jit(nopython=True)
def is_correct(pruf, k):
    return most_frequent(pruf) <= k

Second method:

Generate random integer, add it to sequence only if it didn't show up before k times. Optimized version of these words is below presented (written in Python). Python snippet:

def gen_seq(n, d, m):
    choices = list(range(n))
    degrees = [0] * n
    result = []
    k = n - 1
    for i in range(m):
        rand = np.random.randint(0, k)
        result.append(choices[rand])
        degrees[choices[rand]] += 1
        if degrees[choices[rand]] == d:
            choices[rand], choices[k] = choices[k], choices[rand]
            k -= 1
    return result

Problem is that the first method is very slow for n=30, m=28, d=1 it needs 10^9 times to generate sequence, which is pretty obvious.

The second one is not generating uniform permutations (some have bigger probabilities than others).

Do you have any ideas how one could generate such sequence fast and uniformly?