数字のための順序付きペア

Question

与えられた数字については、Nは、xとyがn以下で、xの桁の合計がyの

の桁の和より小さくなるような可能な順序付きペア（x、y）例えば

N = 6：xがyの桁数の合計よりも常に少ないY及びXの桁の和未満であり、xとyの両方がある[(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)]

現在地21可能順序付けられた対が存在します以下は私の素朴なアプローチですが、これはかなり遅く、N = 10000までうまく動作します。

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)) 

つ使用して発電機

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)) 

優れた改良版：この問題に取り組むためのより良い方法が

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)) 

ありますか？

Answer 1

これを試すことができます。

アイデアは範囲を小さなチャンクに分割します（n = 10000の場合、これはかなり短い時間~1.5秒です）。最後にマージします。

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

私は10000より大きいnのためにこれをテストしていません。

sumof(n)の機能は、このpostから部分的に取り込まれています。

Answer 2

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 3

1つの問題は、まだすべての順列を生成してから、xがy以上のエントリを削除することです。もう1つの問題は、これを保存して後で比較できるときに、各繰り返しのyの数字の合計を再計算することです。将来のすべてのxエントリが基準を満たしていないことがわかっている場合は、ネストされたループから本質的に抜け出すことができるより洗練されたソリューションが存在する可能性があります。 0xfff25cdcで

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>時間：0xfff2c09cで233.378999949

<機能CALC2>時間：84.9670000076

質問に関連していない他のいくつかのポイント。リストへのあなたの呼び出しのいくつかは冗長です。マップ関数はすでにリストを返します。Python 3では、rangeはジェネレータを返します。ジェネレータは、繰り返し処理する際に値を返します。それはより効率的なメモリであり、同じように動作します。

Answer 4

コードの仕組み

これはほとんどあなたのメソッドよりもアルゴリズムの改良点です。ジェネレータやリスト内包表記を使用するほうが速いかもしれませんが、チェックするためにプロファイルする必要があります。アルゴリズムは次のように動作します：

1. 事前計算1の桁の合計 - N.
2. グループ番号1 - Nその数字和で。私たちはこのようなオブジェクトを持っています。したがって、2桁の桁数の数値を取得する場合は、3行目以降の数値を数えるだけです。

1：1、10
2：2、11、20
3：3、12、21、30 ...

各行内の数字がソート順であることに注意してください。私たちの番号が12の場合は、12の後の数字だけを調べる必要があります。各行の12文字をバイナリ検索で見つけることができます。

全体的に、これは

コードこれはまた、無効として対を含む

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