Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Python: Общие вопросы > Создание генератора списка

Автор: nerezus 14.11.2006, 10:29

Есть класс. У него есть метод getItem() Надо, чтобы при каждом вызове метода он выдавал некоторое значение. Теперь про значение: есть 2 числа-границы. Например 1 и 6. Есть строка типа "abcdefghklmnopqrstuvwxyz" Т.е. значения должны быть такие: Код a b c d ... y z aa ab ac ... ay az ba bb .... zz aaa aab ..... zzzzzy zzzzzz Вместо точек - пропуски. Вот как такое организовать? хотел рекурсией, но тогда придется создавать список, куда добавлять эти значения, а так делать нельзя, ибо трата оперативы.

Автор: albertn 14.11.2006, 11:37

Помучился, но получилось: Код def getitem(x1=1,x2=3):     alfavit = "abcdefghklmnopqrstuvwxyz"     for n in range(x1,x2+1):         state = [0 for x in range(n)]         memo = 0         while memo==0:             yield ''.join(map(alfavit.__getitem__,state))             memo = 1             for i in range(n):                 state[n-i-1] += memo                 if state[n-i-1]==len(alfavit):                     state[n-i-1]=0                     memo = 1                 else:                     memo = 0 for x in getitem(x1=1,x2=3):     print x

Автор: Artemios 14.11.2006, 11:40

Код class chr_iter_l:   def __init__(self,max_length):     self.max_len = max_length     self.curr_l = [ord('a')-1]   def __iter__(self):         return self   def inc_char(self,i):     if self.curr_l[i]==ord('z'):       self.curr_l[i] = ord('a')       return 1     else:       self.curr_l[i] +=  1       return 0   def next(self):     i=0     n=len(self.curr_l)     while i<n and self.inc_char(i):       i+=1     if i==n:       if n==self.max_len:         raise StopIteration       else:         self.curr_l.append(ord('a'))     return ''.join(reversed(map(chr,self.curr_l))) for a in chr_iter_l(2):   print a Только вместо 2-ки 6-кой инициализировать не советую, все-таки 36^6 строк выводить будет

Автор: ser_gen 14.11.2006, 11:41

Выдавать по одному из функции можно с помощью yield  Что-то вроде return  толко при следующем вызове продолжит выполнение со следующей строки  функции (после yield)  Код def func(n):     for i in range(n):           yield i for k in func(10000):      print k А алгоритм ищи в книгах по дискретной математики  (кажись эта генерация всех возможных комбинаций там должна быть)

Автор: nerezus 14.11.2006, 11:47

есть вариант об использовании новой системы счисления, база которой равна длине строки. Вот сейчас про него думаю. ser_gen, т.е. просто состояние переменных метода сохранится? будет ли это работать в классах? Добавлено @ 11:47  Artemios, спасибо, сейчас посмотрим Добавлено @ 11:48  albertn, спасибо. Что у меня за плохая привычка смотреть темы снизу )

Автор: albertn 14.11.2006, 11:49

Цитата(nerezus @  14.11.2006,  11:47 ) ser_gen, т.е. просто состояние переменных метода сохранится? будет ли это работать в классах? Посмотри мой пример, там должно быть все понятно. В классах работает аналогично

Автор: nerezus 14.11.2006, 11:58

А вот такой вопрос: имеется функция-генератор(из примера albertn). Как снять с нее 1 значение?

Автор: albertn 14.11.2006, 12:04

Цитата(nerezus @  14.11.2006,  11:58 ) А вот такой вопрос: имеется функция-генератор(из примера albertn). Как снять с нее 1 значение?  Используя метод next Код def getitem(x1=1,x2=3):     alfavit = "abcdefghklmnopqrstuvwxyz"     for n in range(x1,x2+1):         state = [0 for x in range(n)]         memo = 0         while memo==0:             yield ''.join(map(alfavit.__getitem__,state))             memo = 1             for i in range(n):                 state[n-i-1] += memo                 if state[n-i-1]==len(alfavit):                     state[n-i-1]=0                     memo = 1                 else:                     memo = 0 z = getitem(x1=1,x2=3) print z.next() print z.next() Но только по окончанию он вызывает экскепшон

Автор: nerezus 14.11.2006, 12:14

спасибо Добавлено @ 12:23  получилось все. Код def getItem(self):         try:             return self.gen.next()         except:             self.empty = True             return '' где  Код self.gen = self.generator(self.start, self.finish, self.symbols) еще раз спасибо )

Автор: slav0nic 14.11.2006, 12:32

мм, документацию читать не модно нынче=) в туториале есть пример интересный, для генерации всех комбинаций, думаю переписать его не сложно Код #generate all combinations ################## symbols = "123456anb" import string i = 0 def gen(l):    if len(l) <= 1:                  return [l]    r = []        for i in xrange(len(l)):             s = l[:i] + l[i+1:]             for x in gen[s](s):                  r.append(l[i:i+1] + x)    return r combinations =  gen(symbols) ################### f = open("passwords.txt", "w+") print "gen..." for cur_pass in combinations:        f.write(cur_pass+"\n")        i+=1 f.close() print "generated %i passwords" %i

Автор: nerezus 14.11.2006, 12:34

slav0nic, это откуда?

Автор: slav0nic 14.11.2006, 12:37

nerezus, ну ген из оффициальной доки вроде бы брался)  2.1.8 Indentation

Автор: Artemios 14.11.2006, 12:46

Цитата(nerezus @  14.11.2006,  11:47 ) есть вариант об использовании новой системы счисления, база которой равна длине строки. Мне тоже стало интересно, попробовал: Код def getitem(max_length):   alf = map(chr,range(ord('a'),ord('z')+1))   base = len(alf)   max_num = base**max_length   for i in xrange(max_num):     lst = []     a=i     while a:       a,r = divmod(a,base)       lst.append(alf[r])     yield ''.join(reversed(lst)) for x in getitem(2):   print x только здесь вычислений больше производится

Автор: slav0nic 14.11.2006, 12:56

nerezus, короче профилировщик в зубы и тести что быстрее

Автор: albertn 14.11.2006, 13:00

Цитата(nerezus @  14.11.2006,  11:47 ) есть вариант об использовании новой системы счисления, база которой равна длине строки. Вот сейчас про него думаю. Что-то подобное у меня получилось: Код def convert(n,alfavit):     start = n     res = ''     while 1:         res=alfavit[start%len(alfavit)]+res         start = start/len(alfavit)         if start==0:             return res alfavit = "abcdefghklmnopqrstuvwxyz" for x in range(100):     print convert(x,alfavit) Но только есть одна загвоздка. Ни в какой системе счисления нельзя задать число начинающееся с нуля (кроме самого нуля). Тогда надо будет уже указывать количество используемых единиц.

Автор: Artemios 14.11.2006, 13:04

Цитата(slav0nic @  14.11.2006,  12:32 ) для генерации всех комбинаций Цитата(slav0nic @  14.11.2006,  12:32 ) gen[s](s) сие интерпретатор не понимает, меняем на gen(s) -- имеем рекурсию. А вообще -- генерит всего лишь перестановки.

Автор: Artemios 14.11.2006, 13:37

Цитата(albertn @  14.11.2006,  13:00 ) Но только есть одна загвоздка. Ни в какой системе счисления нельзя задать число начинающееся с нуля (кроме самого нуля). Тогда надо будет уже указывать количество используемых единиц. Вот новый вариант позиционной системы, так вроде все замечательно: Код def getitem(max_length):   alf = map(chr,range(ord('a')-1,ord('z')+1))   base = len(alf)   max_num = base**max_length   for i in xrange(max_num):     if i%base:       lst = []       a=i       while a:         a,r = divmod(a,base)         lst.append(alf[r])       yield ''.join(reversed(lst)) for x in getitem(2):   print x

Автор: albertn 15.11.2006, 11:35

Цитата(Artemios @  14.11.2006,  13:37 ) Вот новый вариант позиционной системы, так вроде все замечательно: nerezus по-моему имел ввиду другое. Ему нужен был не способ генерации, основанный на системе счисления, а способ преобразования из десятичной системы (или шестнадцатиричной) в ту, которая задана текущим алфавитом. А твой вариант мало чем отличаеся от всех предыдущих, разве что алгоритмом.

Автор: nerezus 15.11.2006, 11:45

albertn, да нет, мне нужно было просто составить все возможные комбинации(с повторениями и т.д.) Это уже сделано. Просто переход на новую систему счисления - это один из способов решения ) Кстати еще способ придумали: на вход идет предудущее "число"(или просто лежит как self.prev), а по нему составляется следующее. ИМХО наиболее простой способ ;)

Автор: Artemios 15.11.2006, 12:42

Цитата(nerezus @  15.11.2006,  11:45 ) Кстати еще способ придумали: на вход идет предудущее "число"(или просто лежит как self.prev), а по нему составляется следующее. ИМХО наиболее простой способ ;) Именно это и было в моем самом первом примере  (в self.curr_l на каждой итерации - предыдущее, метод next() генерит следующее) И в более красивом примере albertn (первом) - то же, каждое следующее  генерится в цикле на основе предыдущего (в state), с выбросом текущего по yield. Цитата(albertn @  15.11.2006,  11:35 ) А твой вариант мало чем отличаеся от всех предыдущих, разве что алгоритмом.  Скажем так, меня просто заинтересовала позиционная система с произвольным алфавитом и базой, а извращения над ней - для подгонки к генерации требуемых комбинаций   Оправдался?

Автор: albertn 16.11.2006, 16:56

Цитата(Artemios @  15.11.2006,  12:42 ) Скажем так, меня просто заинтересовала позиционная система с произвольным алфавитом и базой, а извращения над ней - для подгонки к генерации требуемых комбинаций smile  Оправдался? smile   В принципе, то все предложенные варианты в той или иной мере основываются на системе счисления. А вариантов я сходу бы штук пять бы сделал. Ведь не в этом суть, а в том, чтоб все это работало как можно быстрее. PS. Невиновным невчем оправдываться

Автор: nerezus 16.11.2006, 17:41

Цитата а в том, чтоб все это работало как можно быстрее. УУ, а вот твой пример то, хоть и выглядит самым красивым, а глючит нещадно    Например, если поставить x1=3 x2=3, то....

Автор: nerezus 16.11.2006, 18:38

еще раз дам код:  Код class WQueueGen:     def __init__(self, filename):         import re, sys         fh = open(filename, 'r')         try:             len_str      = fh.readline().strip()             self.symbols = fh.readline().strip()         except:             print 'Cannot read config file'             sys.exit(1)         brd =  re.findall('\d+', len_str)         self.start  = int(brd[0]) # нижняя длина строки         self.finish = int(brd[1]) # верхняя длина строки         self.empty  = False         if (not self.symbols) or (self.start >= self.finish):             self.empty = True         self.len = self.start # текущая длина строки         self.pos = 0          # текущая позиция         self.gen = self.generator(self.start, self.finish, self.symbols)     def generator(self, x1, x2, alfavit):         for n in range(x1,x2+1):             state = [0 for x in range(n)]             memo = 0             while memo==0:                 yield ''.join(map(alfavit.__getitem__,state))                 memo = 1                 for i in range(n):                     state[n-i-1] += memo                     if state[n-i-1]==len(alfavit):                         state[n-i-1]=0                         memo = 1                     else:                         memo = 0     def isEmpty(self):         return self.empty     def getItem(self):         try:             return self.gen.next()         except:             self.empty = True             return '' q = WQueueGen('c:\\1.txt') while not q.isEmpty():     print q.getItem() c:\\1.txt Код 3-3 abc

Автор: nerezus 17.11.2006, 09:04

Для примера, если написать в 1.txt Код 2-3 abc то работает, как надо.

Автор: albertn 17.11.2006, 14:46

nerezus, self.start >= self.finish в строке 15 замени на self.start > self.finish, тогда все заработает

Автор: nerezus 17.11.2006, 19:34

А как сделать, чтобы повторяющихся символов не было? Можно конечно в список символы загнать и проверять, но... не изящно )

Автор: albertn 20.11.2006, 14:02

Цитата(nerezus @  17.11.2006,  19:34 ) А как сделать, чтобы повторяющихся символов не было? Можно конечно в список символы загнать и проверять, но... не изящно )  А изящно и я немогу придумать че-то, разве что есть мысль полсе каждой выборки одного элемента уменьшать алфавит, и выбирать уже из нового.

Автор: nerezus 20.11.2006, 20:00

Хм, а такой способ как будет выглядеть? Ибо у меня тупо проверкой в генерированной строке производится )

Автор: albertn 21.11.2006, 09:44

Цитата(nerezus @  20.11.2006,  20:00 ) Хм, а такой способ как будет выглядеть? Ибо у меня тупо проверкой в генерированной строке производится )  Код class WQueueGen:     def __init__(self, filename):         import re, sys         fh = open(filename, 'r')         try:             len_str      = fh.readline().strip()             self.symbols = fh.readline().strip()         except:             print 'Cannot read config file'             sys.exit(1)         brd =  re.findall('\d+', len_str)         self.start  = int(brd[0]) # нижняя длина строки         self.finish = int(brd[1]) # верхняя длина строки         self.empty  = False         if (not self.symbols) or (self.start > self.finish):             self.empty = True         self.len = self.start # текущая длина строки         self.pos = 0          # текущая позиция         self.gen = self.generator(self.start, self.finish, self.symbols)     def generator(self, x1, x2, alfavit):         for n in range(x1,x2+1):             state = [0 for x in range(n)]             memo = 0             while memo==0:                 temp_alfavit = list(alfavit)                 res = ''                 for i in state:                     res+=temp_alfavit[i]                     del temp_alfavit[i]                 yield res                 memo = 1                 for i in range(n):                     state[n-i-1] += memo                     if state[n-i-1]==len(alfavit)-n+i+1:                         state[n-i-1]=0                         memo = 1                     else:                         memo = 0     def isEmpty(self):         return self.empty     def getItem(self):         try:             return self.gen.next()         except:             self.empty = True             return '' q = WQueueGen('1.txt') while not q.isEmpty():     print q.getItem()

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)