Ordered pair for row

Question

For a given number, Nfind the total possible ordered pair (x, y) such that x and y are less than or equal to n, and the sum of digits x is less than the sum of digits y

e.g. n = 6: there 21is a possible ordered pair that[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6), (4, 5), (4, 6), (5, 6)]

here x is always less than y, and the sum of the digits x is also less than the sum of the digits y, and x and y are equal to or less than N. Here is my naive approach, but it is rather slow and works fine to N = 10000 after that it does not work well.

from itertools import permutations
n=100
lis=list(range(n+1))
y=list(i for i in permutations(lis,2) if i[0]<i[1] and sum(list(map(int,
(list(str(i[0]))))))<sum(list(map(int,(list(str(i[1])))))))
print(len(y))

One of the generators

from itertools import permutations
for _ in range(int(input())):
    n=1000
    lis=range(n+1)
    y=(i for i in permutations(lis,2) if i[0]<i[1] and sum(list(map(int,
     (list(str(i[0]))))))<sum(list(map(int,(list(str(i[1])))))))
    print (sum(1 for _ in y))

Enhanced Version:

from itertools import permutations
for _ in range(int(input())):
    n=1000
    lis=range(n+1)
    y=(i for i in permutations(lis,2) if i[0]<i[1] and sum(map(int,(str(i[0]))))<sum(map(int,(list(str(i[1]))))))
    print (sum(1 for _ in y))

Is there a better approach to solving this problem?

Answer 1

How the code works

. , , . :

• 1 - N.
• 1 - N . , . , sum > 2, .

1:1, 10
2: 2, 11, 20
3: 3, 12, 21, 30...

3. , . 12, 12. 12s .

, 20% , O (N)

import time
import bisect
import itertools

N = 6

def sum_digits(n):
    # stolen from here: https://stackoverflow.com/questions/14939953/sum-the-digits-of-a-number-python
    # there may be a faster way of doing this based on the fact that you're doing this over 1 .. N
    r = 0
    while n:
        r, n = r + n % 10, n // 10
    return r        

t = time.time()
# trick 1: precompute all of the digit sums. This cuts the time to ~0.3s on N = 1000
digit_sums = [sum_digits(i) for i in range(N+1)]
digit_sum_map = {}

# trick 2: group the numbers by the digit sum, so we can iterate over all the numbers with a given digit sum very quickly
for i, key in enumerate(digit_sums):
    try:
        digit_sum_map[key].append(i)
    except KeyError:
        digit_sum_map[key] = [i]
max_digit_sum = max(digit_sum_map.keys())

# trick 3: note that we insert elements into the digit_sum_map in order. thus we can binary search within the map to find
# where to start counting from. 
result = []
for i in range(N):
    for ds in range(digit_sums[i] + 1, max_digit_sum + 1):
        result.extend(zip(itertools.repeat(i), digit_sum_map[ds][bisect.bisect_left(digit_sum_map[ds], i):]))

print('took {} s, answer is {} for N = {}'.format(time.time() - t, len(result), N))
# took 0.0 s, answer is 21 for N = 6
# took 0.11658287048339844 s, answer is 348658 for N = 1000
# took 8.137377977371216 s, answer is 33289081 for N = 10000

# for reference, your last method takes 2.45 s on N = 1000 on my machine

Answer 2

.

, ( ~ 1,5 n= 10000) .

import time
from itertools import combinations

t = time.process_time()

def sumof(n):
    r = 0
    while n > 0:
        r, n = r + n % 10, n // 10
    if r > 9:
        r = sumof(r) 
    return r

def check(x,y):
    if x < y:
        if sumof(x) < sumof(y):
            return True
        return False
    return False

l=[]
n0=100
# to get the first 10000, iterating over ranges of n0=100
for i in range(0,n0):
    n1 = n0 * i
    n2 = n0 * (i+1)
    l+= [ (a,b) for a,b in list(combinations(list(range(n1,n2)),2)) if check(a,b) ]

print(l)

elapsed_time = time.process_time() - t
print(elapsed_time)

[.... (9987, 9999), (9988, 9989), (9988, 9990), (9988, 9998), (9988, 9999), (9989, 9990), (9989, 9999), (9991, 9992), (9991, 9993), (9991, 9994), (9991, 9995), (9991, 9996), (9991, 9997), (9991, 9998), (9991, 9999), (9992, 9993), (9992, 9994), (9992, 9995), (9992, 9996), (9992, 9997), (9992, 9998), (9992, 9999), (9993, 9994), (9993, 9995), (9993, 9996), (9993, 9997), (9993, 9998), (9993, 9999), (9994, 9995), (9994, 9996), (9994, 9997), (9994, 9998), (9994, 9999), (9995, 9996), (9995, 9997), (9995, 9998), (9995, 9999), (9996, 9997), (9996, 9998), (9996, 9999), (9997, 9998), (9997, 9999), (9998, 9999)]

:

~ 1,5 n = 10000

n , 10000.

sumof(n) .

Answer 3

def find_total_possible(n):
    x = [i for i in range(n + 1)]
    y = [i + 1 for i in range(n + 1)
    z = list(zip(x,y))
    return z

?

.

Answer 4

, , x y. , y , . , , , x- .

from itertools import permutations
from time import time

def time_profile(f):

    def time_func(*args, **kwargs):
        start_time = time()
        r = f(*args, **kwargs)
        end_time = time()
        print "{} Time: {}".format(f, end_time - start_time)
        return r

    return time_func

@time_profile
def calc1(n):
    lis=list(range(n+1))
    y=list(i for i in permutations(lis,2) if i[0]<i[1] and sum(list(map(int,
    (list(str(i[0]))))))<sum(list(map(int,(list(str(i[1])))))))
    return y

@time_profile
def calc2(n):
    l = []
    for y in xrange(n+1):
        y_sum = sum(map(int, str(y)))
        for x in xrange(y):
            # May be possible to use x_digits to break
            x_digits = map(int, str(x))
            if sum(x_digits) >= y_sum: continue
            l.append((x, y))

    return l

if __name__ == '__main__':
    N = 10000
    if len(calc1(N)) != len(calc2(N)): print 'fail'

< calc1 0xfff25cdc > : 233.378999949

< calc2 0xfff2c09c > : 84.9670000076

, . . . Python 3 , . .