Заменять вложенные циклы For… или нет

Question

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

aaaa
aaab
aaac
aaad

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

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 переменная.Его по-прежнему будет только два fors для любого количества символов, и вам не нужно повторяться.И вполне читабельно..

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.Удаление пустой строки из chars array будет просто генерировать строки из 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 и @Триптих решения дают разные результаты:

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

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

Answer 7

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

#!/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 на каждом уровне рекурсии.Нерекурсивный подход также может иметь смысл.