Форум сайта python.su
Подскажите как из алфавита, скажем:
alphabet = “abcdef”
создать все комбинаци содержащие хотябы 1 букву.
Я так понимаю это делается через рекурсию? Если можно ткните примером.
Офлайн
По-разному можно. Например вложенными циклами.
Или парой функций. Можно и рекурсией, если получится быстрее…
Я думаю что в данном случае можно просто ленивую функцию написать (не уверен)…
Дайте пример как сами делаете, подскажем - что так, а что - нет.
Отредактировано (Июнь 11, 2008 01:01:45)
Офлайн
tty
я пару лет назад задумался над тем чтобы создавать строки разной длины (4,5,6 и т.д. символов) содержащих все комбинации символов словаря. вложенные циклы это конечно хорошо, но для каждой строки это разное количество вложений. и я сделал вот так.
# -*- coding:cp1251 -*- import time # Будем работать с gzip архивом zip = False # файл для сохранения паролей filename = 'D:/My Program/pass.txt' # минимальная длина пароля start = 1 # максимальная длина пароля end = 6 count = 0 #Считаем количество паролей def _getFile(): """ Возвращает объект типа файл, для записи паролей """ if zip: import gzip f = gzip.GzipFile(filename, 'w') print "Compressed: True" else: f = open(filename, 'w') print "Compressed: False" return f def SetUp(i, max, mas): """ в массиве mas увеличивает i'ый элемент на единицу. Если mas[i] уже максимально тогда рекурсивно идет увеличение i-1 элемента, mas[i] при этом обнуляется. если самый первый элемент массива достиг максимума, возвращает false """ if mas[i] == max: mas[i] = 0 if i != 0: # рекурсивный запуск для предыдущего элемента return SetUp(i-1, max, mas) else: return False else: mas[i] += 1 return True def Pass(l, a, f): """Схема такая. допустим длина пароля 3 символа, создаем вот такой массив _mas = [0,0,0] элементы -- это индексы символов словаря, которые будут подставляться в пароль, т.е. с текущим массивом (словарь a = 'abcdef') создается пароль 'aaa', далее функцией SetUp() массив изменяется так [0,0,1] и пароль уже будет 'aab' и т.д. пока массив не станет таким [5,5,5], т.е.каждый элемент массива будет равен индексу последнего символа словаря тогда SetUp() вернет False """ _mas = [] for x in range(l):# создаем массив длиной равной длине пароля _mas.append(0) flag = True while flag: _pas = '' for x in _mas: _pas += a[x] _pas += '\n' f.write(_pas) flag = SetUp(len(_mas)-1, len(a)-1, _mas) if __name__ == "__main__": print "Saved passwords in '%s'" % filename a = 'abcdef'# Все возможные символы содержащиеся в пароле f = _getFile() print "Count of letters: %d" % len(a) print "Password length from %d to %d" % (start, end) print "\nStart in %s" % time.ctime() for i in range(start,end+1):# Запуск функции составления всевозможных комбинаций для каждой длины пароля print "\tPassword length: %s" % i count += len(a)**i print "\t\tCount: %s" % (len(a)**i) Pass(i, a, f) f.close() print "\nEnd in %s" % time.ctime() print "Full passwords count: %s" % count
Офлайн
Ну я же и говорю, что можно 2-мя функциями :)
Просто пытался выяснить у человека что он сам по-этому поводу думает прежде чем давать какой-либо готовый вариант ;)
Офлайн
Тут еще ничего решение предлагалось:
http://qtfaq.ru/tiki-view_forum_thread.php?comments_parentId=18&topics_offset=1&topics_sort_mode=lastPost_desc&forumId=5
Офлайн
с использованием генератора можно обойтись одной функцией :
def combs_gen(chars_in, len_min, len_max=None):
if len_max == None: len_max = len_min
for len_cur in range(len_min, len_max + 1):
cnts = # create counters array
while True:
yield ''.join(chars_in for c in cnts)
for cnts_cnt in range(len(cnts)): # update counters
cnts += 1
if (cnts >= len(chars_in)) and (cnts_cnt < len(cnts) - 1) :
cnts = 0
else: break
if cnts >= len(chars_in): break
return
for s in combs_gen('0123', 3):
print s
raw_input()
Офлайн