Помогите мне закончить самопроблему Python 3.x - PullRequest
Новая
       48

Помогите мне закончить самопроблему Python 3.x

8 голосов
/ 16 апреля 2010

Это не домашняя работа.

Я видел эту статью, восхваляющую библиотеку Linq и ее великолепную за работу над комбинаторикой, и подумал про себя: Python может сделать это более читабельным образом.

После получаса работы с Python я потерпел неудачу. Пожалуйста, закончите, где я остановился. Кроме того, сделайте это самым питонским и эффективным способом из всех возможных, пожалуйста. 

from itertools import permutations
from operator import mul
from functools import reduce
glob_lst = []
def divisible(n): return (sum(j*10^i for i,j in enumerate(reversed(glob_lst))) % n == 0)
oneToNine = list(range(1, 10))
twoToNine = oneToNine[1:]
for perm in permutations(oneToNine, 9):
    for n in twoToNine:
        glob_lst = perm[1:n]
        #print(glob_lst)
        if not divisible(n):
            continue
    else:
        # Is invoked if the loop succeeds
        # So, we found the number
        print(perm)

Спасибо!

Ответы [ 4 ]

23 голосов
/ 16 апреля 2010

Вот краткое решение, использующее itertools.permutations : 

from itertools import permutations

def is_solution(seq):
    return all(int(seq[:i]) % i == 0 for i in range(2, 9))

for p in permutations('123456789'):
    seq = ''.join(p)
    if is_solution(seq):
        print(seq)

Я намеренно пропустил проверки делимости на 1 и на 9, поскольку они всегда будут удовлетворены.

3 голосов
/ 01 июля 2011

Вот мое решение. Мне нравятся все вещи снизу вверх ;-). На моей машине он работает примерно в 580 раз быстрее (3,1 мсек против 1,8 с), чем отметки: 

def generate(digits, remaining=set('123456789').difference):
    return (n + m
        for n in generate(digits - 1)
            for m in remaining(n)
                if int(n + m) % digits == 0) if digits > 0 else ['']

for each in generate(9):
    print(int(each))

РЕДАКТИРОВАТЬ: Кроме того, это работает, и в два раза быстрее (1,6 мсек): 

from functools import reduce

def generate():
    def digits(x):
        while x:
            x, y = divmod(x, 10)
            yield y
    remaining = set(range(1, 10)).difference
    def gen(numbers, decimal_place):
        for n in numbers:
            for m in remaining(digits(n)):
                number = 10 * n + m
                if number % decimal_place == 0:
                    yield number
    return reduce(gen, range(2, 10), remaining())

for each in generate():
    print(int(each))
2 голосов
/ 16 апреля 2010

Вот мое решение (не такое элегантное, как у Марка, но оно все еще работает): 

from itertools import permutations

for perm in permutations('123456789'):
    isgood = 1
    for i in xrange(9):
        if(int(''.join(perm[:9-i])) % (9-i)):
            isgood = 0
            break
    if isgood:
        print ''.join(perm)
1 голос
/ 01 июля 2011

это мое решение, оно очень похоже на Маркса, но работает примерно вдвое быстрее 

from itertools import permutations

def is_solution(seq):
    if seq[-1]=='9':
        for i in range(8,1,-1):
            n = -(9-i)
            if eval(seq[:n]+'%'+str(i))==0:
                continue
            else:return False
        return True
    else:return False
for p in permutations('123456789'):
    seq = ''.join(p)
    if is_solution(seq):
        print(seq)
...