Заменить Nested For Loops ... или нет

Question

У меня есть скрипт, который перебирает последовательность из четырех (или менее) строк символов. Например:

aaaa
aaab
aaac
aaad

Если бы удалось реализовать его с помощью вложенных циклов, например:

chars = string.digits + string.uppercase + string.lowercase

for a in chars:
    print '%s' % a   
    for b in chars:
        print '%s%s' % (a, b)
        for c in chars:
            print '%s%s%s' % (a, b, c)
            for d in chars:
                print '%s%s%s%s' % (a, b, c, d)

Является ли этот цикл вложением плохой вещи, и если это так, что может быть лучшим способом выполнения того, что я делаю?

Answer 1

import string
import itertools

chars = string.digits + string.letters
MAX_CHARS = 4
for nletters in range(MAX_CHARS):
    for word in itertools.product(chars, repeat=nletters + 1):
        print (''.join(word))

Это напечатает все 15018570 слова, которые вы ищете. Если вы хотите больше / меньше слов, просто измените переменную MAX_CHARS. У него все еще будет всего два for с для любого количества символов, и вам не нужно повторяться. И довольно читабелен. .

Answer 2

Я собираюсь представить свой ответ как наиболее читаемый и наименее масштабируемый:)

import string
chars = [''] + list(string.lowercase)

strings = (a+b+c+d for a in chars
                   for b in chars
                   for c in chars
                   for d in chars)

for string in strings:
    print string

РЕДАКТИРОВАТЬ: На самом деле, это неверно, поскольку он будет производить дубликаты всех строк длиной <4. Удаление пустой строки из массива <code>chars приведет к получению строк из 4 символов.

Обычно я удаляю этот ответ, но мне все равно нравится, если вам нужно генерировать строки одинаковой длины.

Answer 3

Напиши для программиста первое - компьютер второго.
Если это ясно и понятно для понимания, тогда это правильно.

Если скорость имеет значение И компилятор все равно ее не оптимизирует И если вы измеряете ее И это проблема - тогда подумайте о более быстром и умном способе!

Answer 4

Я не думаю, что это плохо, если вы понимаете (и документально :-) это. Я не сомневаюсь, что может быть более питонический способ или умное решение (с лямбдами или еще чем-нибудь), но я всегда предпочитал удобочитаемость, а не хитрость.

Поскольку вы должны генерировать все возможности из 1-, 2-, 3- и 4-символьных "слов", этот метод так же хорош, как и любой другой. Я не уверен, сколько времени это займет, так как вы эффективно генерируете (очень приблизительно) 14 миллионов строк вывода (но, вероятно, у каждого решения будет такая проблема).

Предварительный расчет общих префиксов может обеспечить увеличение скорости, но вам лучше измерить его для проверки ( всегда проверка, никогда предположим):

chars = string.digits + string.uppercase + string.lowercase
for a in chars:
    print a
    for b in chars:
        ab = '%s%s' % (a, b)
        print ab
        for c in chars:
            abc = '%s%s' % (ab, c)
            print abc
            for d in chars:
                print '%s%s' % (abc, d)

РЕДАКТИРОВАТЬ: Я на самом деле сделал несколько тестов (с Windows-Python 2.6.1) - эта версия занимает около 2,25 единиц времени по сравнению с исходными 2,84, поэтому она на 26% быстрее. Я думаю, что это может послужить основанием для его использования (опять же, если четко задокументировано, чего он пытается достичь).

Answer 5

@ nosklo's и @ Triptych's дают разные результаты:

>>> list(map(''.join, itertools.chain.from_iterable(itertools.product("ab", 
...     repeat=r) for r in range(4)))) # @nosklo's 

['', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', 'aab', 'aba', 'abb', 'baa', 
 'bab', 'bba', 'bbb']

>>> ab = ['']+list("ab")
>>> list(map(''.join, (a+b+c for a in ab for b in ab for c in ab)))  

['', 'a', 'b', 'a', 'aa', 'ab', 'b', 'ba', 'bb', 'a', 'aa', 'ab', 'aa', 
 'aaa', 'aab', 'ab', 'aba', 'abb', 'b', 'ba', 'bb', 'ba', 'baa', 'bab', 
 'bb',  'bba', 'bbb']

Вот модифицированное решение @ Triptych, которое выдает тот же результат, что и @ nosklo:

>>> ab = "ab"
>>> list(map(''.join, itertools.chain([''], ab, (a+b for a in ab for b in ab),
...     (a+b+c for a in ab for b in ab for c in ab))))

['', 'a', 'b', 'aa', 'ab', 'ba', 'bb', 'aaa', 'aab', 'aba', 'abb', 'baa', 
 'bab', 'bba', 'bbb']

Answer 6

Это не совсем ответ на вопрос, но это вернет n th комбинацию для заданной максимальной длины и символов в алфавите для использования:

#!/usr/bin/python

def nth_combination(n, maxlen=4, alphabet='abc'):
    """
    >>> print ','.join(nth_combination(n, 1, 'abc') for n in range(3))
    a,b,c
    >>> print ','.join(nth_combination(n, 2, 'abc') for n in range(12))
    a,aa,ab,ac,b,ba,bb,bc,c,ca,cb,cc
    >>> import string ; alphabet = string.ascii_letters + string.digits
    >>> print ','.join(nth_combination(n, 4, alphabet) for n in range(16))
    a,aa,aaa,aaaa,aaab,aaac,aaad,aaae,aaaf,aaag,aaah,aaai,aaaj,aaak,aaal,aaam
    >>> print ','.join(nth_combination(n, 4, alphabet)
    ...                for n in range(0, 14000000, 10**6))
    a,emiL,iyro,mKz2,qWIF,u8Ri,zk0U,Dxav,HJi9,LVrM,P7Ap,UjJ1,YvSE,2H1h
    """
    if maxlen == 1:
        return alphabet[n]
    offset, next_n = divmod(n, 1 + len(alphabet)**(maxlen-1))
    if next_n == 0:
        return alphabet[offset]
    return alphabet[offset] + nth_combination(next_n-1, maxlen-1, alphabet)

if __name__ == '__main__':
    from doctest import testmod
    testmod()

Это, конечно, имеет смысл, только если вам нужен произвольный доступ к набору комбинаций вместо того, чтобы всегда повторять их все.

Если maxlen высокий, можно достичь некоторой оптимизации скорости, например, избавившись от конкатенации строк и пересчитав длину alphabet и maxlen-1 на каждом уровне рекурсии. Нерекурсивный подход также может иметь смысл.

Answer 7

Существует множество алгоритмов для генерации каждой перестановки множества. То, что вы хотите здесь, является связанной проблемой, но не прямо анагональной. Рекомендуемое чтение