Функция генератора на Python, что дает сочетания элементов в последовательности, отсортированный по порядку подмножество


В Python, модуле itertools.комбинации дает сочетания элементов в последовательности, отсортированный по лексикографическом порядке. В ходе решения некоторых математических задач, я нашел это полезно, чтобы написать функцию, combinations_by_subset, что доходность этих комбинаций отсортированный по подгруппе порядка (за отсутствием лучшего названия).

Например, в списке всех 3-длина комбинации АБВГД строки'':

>>> [''.join(c) for c in itertools.combinations('abcde', 3)]
['abc', 'abd', 'abe', 'acd', 'ace', 'ade', 'bcd', 'bce', 'bde', 'cde']

>>> [''.join(c) for c in combinations_by_subset('abcde', 3)]
['abc', 'abd', 'acd', 'bcd', 'abe', 'ace', 'bce', 'ade', 'bde', 'cde']

Формально, для последовательности длины \ФП\$, то есть \$\бином{п}{р}\$ комбинаций длины \$Р\$, где$\бином{п}{р} = \фрац{п!}{Р! (н - р)!}\$

Функция combinations_by_subset дает комбинации в таком порядке, что первая \$\бином{к}{р}\$ из них-р-длина комбинации из первых k элементов последовательности.

В нашем примере выше, первый \$\бином{3}{3} = 1\$ комбинация-это 3-длина комбинации 'азбука' (это просто 'азбука'); первый \$\бином{4}{3} = 4\$ комбинации 3-длина комбинации 'АБВГД' (который 'Азбука', 'Абд', 'ДСА', 'кор'); и т. д.

Моя первая реализация является простой функцией генератора:

def combinations_by_subset(seq, r):
    if r:
        for i in xrange(r - 1, len(seq)):
            for cl in (list(c) for c in combinations_by_subset(seq[:i], r - 1)):
                cl.append(seq[i])
                yield tuple(cl)
    else:
        yield tuple()

Для начала, я решил написать вторую реализацию в качестве генератора выражений и придумали следующее:

def combinations_by_subset(seq, r):
    return (tuple(itertools.chain(c, (seq[i], ))) for i in xrange(r - 1, len(seq)) for c in combinations_by_subset(seq[:i], r - 1)) if r else (() for i in xrange(1))

Мои вопросы:

  1. Какое определение функции предпочтительнее? (Я предпочитаю функцию генератора за выражение генератор из-за удобочитаемости.)
  2. Какие усовершенствования можно сделать с описанным выше алгоритмом/реализации?
  3. Вы можете предложить лучшее название для этой функции?


Комментарии
2 ответа

Вместо преобразования кортежа в список и обратно, создать новый Кортеж, добавляя к нему.

def combinations_by_subset(seq, r):
if r:
for i in xrange(r - 1, len(seq)):
for cl in combinations_by_subset(seq[:i], r - 1):
yield cl + (seq[i],)
else:
yield tuple()

7
ответ дан 24 марта 2011 в 02:03 Источник Поделиться

Я начала с того, что я не знаю питон. Вполне вероятно, что я сделал очень четкий ошибка в моей следующие изменения. Вообще, хотя я предпочитаю вашу вторую функцию в свой первый. Если Python позволяет, я бы разбить его немного для удобства чтения. Почему мне это нравится? Он не нуждается в доходности сайта, а это меньше вложенной.

# I like using verbs for functions, perhaps combine_by_subset()
# or generate_subset_list() ?
def combinations_by_subset(seq, r):
return (

# I don't know what chain does - I'm making a wild guess that
# the extra parentheses and comma are unnecessary
# Could this be reduced to just itertools.chain(c, seq[i]) ?

tuple(itertools.chain(c, (seq[i], )))
for i in xrange(r - 1, len(seq))
for c in combinations_by_subset(seq[:i], r - 1)

) if r

else ( () for i in xrange(1) )

Я просто ждал этого ответа было помечено как не быть полезным. Служит мне право положить свои пять копеек, когда я даже не знаю языка. ;)

0
ответ дан 24 марта 2011 в 10:03 Источник Поделиться