Recursively generate all k-digit numbers whose digit-sum is n

Question

I was working on a problem where I'm finding all k-digit numbers whose digits sum up the given n.

I found how to do this and approach it as Integer Partitioning problem, however I would like to be able to only input n and k numbers (without the max_element) but when I try to delete it from the code it doesn't seem to work anymore.

How can I change that plus reverse it?

def c(n, k, max_element):
    allowed = range(max_element, 0, -1)

    def helper(n, k, t):
        if k == 0:
            if n == 0:
                yield t
        elif k == 1:
            if n in allowed:
                yield t + (n,)
        elif 1 * k <= n <= max_element * k:
            for v in allowed:
                yield from helper(n - v, k - 1, t + (v,))
    return helper(n, k, ())

for p in c(5, 3, 3):
    print(p)

I tried using the reversed method but apparently it doesn't work in the generator.

Result:

(3, 1, 1)
(2, 2, 1)
(2, 1, 2)
(1, 3, 1)
(1, 2, 2)
(1, 1, 3)

Expected result:

113 122 131 212 221 311

@ggorlen oh you are right, I did not notice that. I want to have numbers in an increasing order — Hemal, Dec 05 '19 at 22:44

kaya3 · Accepted Answer · 2019-12-05T22:58:40.957

3

There are a couple of problems here; the first is that you want the numbers in order and this code generates them in reverse order, because of range(max_element, 0, -1). The other problem is that since you're generating digits, the minimum element should be 0 and the maximum element should always be 9. We can fix both by changing that range to range(10).

We still need to be careful not to generate numbers starting with 0, so we'll make allowed a parameter and use range(1, 10) for just the first digit. I've also changed it to return the result as an integer instead of a tuple.

For reference, the code for this generator function comes from my answer to another question.

def c(n, k):
    def helper(n, k, t, allowed):
        if k == 0:
            if n == 0:
                yield t
        elif k == 1:
            if n in allowed:
                yield 10*t + n
        elif 0 <= n <= 9 * k:
            for v in allowed:
                yield from helper(n - v, k - 1, 10*t + v, range(10))

    return helper(n, k, 0, range(1, 10))

Example:

>>> for p in c(5, 3):
...     print(p)
...
104
113
122
131
140
203
212
221
230
302
311
320
401
410
500

edited Dec 05 '19 at 22:58

answered Dec 05 '19 at 22:50

kaya3

47,440
4
68
97

They closed my post so I created a new one with the code you referred me to, but I was trying to delete the max as I only want to input n and k – Hemal Dec 05 '19 at 22:54
Could i then use `" ".join` to have 104 form instead of (1,0,4) ? – Hemal Dec 05 '19 at 22:56
1

The problem is to generate *"all k-digit numbers whose digits sum up the given n"* - there isn't anything to suggest 0 should be excluded, except that the OP's code doesn't include 0. I choose not to infer additional requirements from code which is known not to solve the problem. – kaya3 Dec 05 '19 at 23:29
I agree, plus it's a pretty trivial difference. Good answer--seems like the optimizations for the extra branch and checking the sum offer a major efficiency boost. – ggorlen Dec 05 '19 at 23:30

score 1 · Answer 2 · answered Dec 05 '19 at 22:46

1

This function should do the trick

def c(n, k, max_element):
    allowed = range(max_element, 0, -1)

    def helper(n, k, t):
        if k == 0:
            if n == 0:
                yield t
        elif k == 1:
            if n in allowed:
                yield t + (n,)
        elif 1 * k <= n <= max_element * k:
            for v in allowed:
                yield from helper(n - v, k - 1, t + (v,))
    return helper(n, k, ())

def reversed_iterator(iter):
    return reversed(list(iter))

for p in reversed_iterator(c(5, 3, 3)):
    print(p)

here is the output :

(1, 1, 3)
(1, 2, 2)
(1, 3, 1)
(2, 1, 2)
(2, 2, 1)
(3, 1, 1)

answered Dec 05 '19 at 22:46

Skander HR

580
3
14

This totally defeats the purpose of using an iterator in the first place. `reversed_iterator` doesn't return an iterator as it advertises, it just exhausts the iterator and returns a list. – ggorlen Dec 05 '19 at 22:47
What about deleting the max_element ? Any suggestions? – Hemal Dec 05 '19 at 22:47

Recursively generate all k-digit numbers whose digit-sum is n

2 Answers2