Generate all permutations which contains a number at least once given length, and number of digits

First step, know how many of them there are. This is a simple recursive function. The caching layer turns it into a top down dynamic programming algorithm. Which is fancy speak for, "speed up calculations by returning the previous answer if you're asked the same question again."

def count_possibilities (digits, entries, seen, cache={}):
    key = (digits, entries, seen)
    if key not in cache:
        if entries < digits - seen:
            value = 0
        elif entries == 0:
            value = 1
        else:
            value = (digits - seen) * count_possibilities(
                        # See a new digit
                        digits, entries-1, seen+1
                    ) + seen * count_possibilities(
                        # See a digit again
                        digits, entries-1, seen
                    )
        cache[key] = value
    return cache[key]

Now that we know how many there are, we can find any particular possibility by index.

def find_possibility (digits, entries, n):
    if n < 0 or count_possibilities(digits, entries, 0) <= n:
        return None
    answer = []
    seen = set()
    while len(answer) < entries:
        for digit in range(digits):
            if digit in seen:
                count = count_possibilities(digits,
                                            entries-len(answer)-1,
                                            len(seen))
            else:
                count = count_possibilities(digits,
                                            entries-len(answer)-1,
                                            len(seen)+1)
            if count <= n:
                # We are skipping past count possibilities
                # that came before in lexicographic order.
                n -= count
            else:
                # This is our choice
                seen.add(digit)
                answer.append(digit)
                break
    return answer

And now we know how to count how many there are, and how to find individual ones. We just need to combine them as follows:

def enumerate_possibilities(digits, entries):
    max_n = count_possibilities(digits, entries, 0)
    for n in range(max_n):
        yield find_possibility(digits, entries, n)

for possibility in enumerate_possibilities(3, 5):
    print(possibility)

And after running that you will verify that they did indeed come out in lexicographic order.

It was pointed out in the comments that I changed variable names from the question. The following may clarify the connection.

def V (n, k):
    return enumerate_possibilities(k, n)

I also said "possibilities" instead of "permutations" because they are not generally permutations.

(I overlooked the requirement that the results have to be in lexicographical order. If you use the method described below, you will have to sort the results. You could use a merge sort, because the permutations in the last step are generated in order.)

To generate all unique solutions, without duplicates that would have to be weeded out later, you could take these step (using the example of n=7 and k= 3)

• Generate all partitions of n-k with a maximum of k parts:
  [4], [3,1], [2,2], [2,1,1]

• Pad the partitions with zeros to all be size k:
  [4,0,0], [3,1,0], [2,2,0], [2,1,1]

• Add 1 to each number in the partitions:
  [5,1,1], [4,2,1], [3,3,1], [3,2,2]

• Generate all unique permutations of these partitions:
  [5,1,1], [1,5,1], [1,1,5]
[4,2,1], [4,1,2], [2,1,4], [2,4,1], [1,2,4], [1,4,2]
[3,3,1], [3,1,3], [1,3,3]
[3,2,2], [2,3,2], [2,2,3]

• Use these permutations as the number of each digit 0 to k-1 in a solution of size n:
  [5,1,1] = [0,0,0,0,0,1,2]
[1,5,1] = [0,1,1,1,1,1,2]
...
[2,3,2] = [0,0,1,1,1,2,2]
[2,2,3] = [0,0,1,1,2,2,2]

• Generate all unique permutations of these solutions:
  [0,0,0,0,0,1,2], [0,0,0,0,0,2,1], [0,0,0,0,1,0,2], ... [2,1,0,0,0,0,0]
[0,1,1,1,1,1,2], [0,1,1,1,1,2,1], [0,1,1,1,2,1,1], ... [2,1,1,1,1,1,0]
...
[0,0,1,1,1,2,2], [0,0,1,1,2,1,2], [0,0,1,1,2,2,1], ... [2,2,1,1,1,0,0]
[0,0,1,1,2,2,2], [0,0,1,2,1,2,2], [0,0,1,2,2,1,0], ... [2,2,2,1,1,0,0]

Generating partitions and permutations can be done with simple recursive algorithms, but generating unique permutations is less straightforward. Have a look at this question for useful algorithms, e.g.:

• Start with the numbers in ascending order (so no need to sort them in the last step).

• Locate the rightmost digit that is smaller that the digit to the right of it; let's call its index i.

• Locate the rightmost digit after index i that is greater than the digit at index i, call its index j.

• Swap the digits at indexes i and j.

• Reverse the order of all digits to the right of index i.

Let's run through an example from the last step of our algorithm:

[0,0,1,1,2,2,2]
       i     j

The right-most digit that is smaller than the digit after it, is the last 1 before the 2's. The right-most digit after it that is greater than it, is the last 2. We now swap these two digits:

[0,0,1,2,2,2,1]
       i     j

and then reverse the order of the digits after index i:

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

and this is our next permutation. When you get to the point where you can not find a digit that is smaller than the digit to the right of it, you have reached the last permutation:

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

For the fourth step, algorithms to generate partitions often generate them from large to small values, like [4,2,1]. So you will either have to modify the algorithm to generate them in the form [1,2,4], or reverse them afterwards, to prepare them for the next step of generating their unique permutations.