Форум программистов [Powered by Invision Power Board]

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

Форум программистов > Центр помощи > [Python] Сортировка слов по длине

Автор: Paranorma 4.2.2007, 00:35

У меня просто уже ни одной умной мысли в голове, как это правильно составить. Суть такова, что сперва в список помещаются строки, а затем сортируются в словаре по длине строки. Строки длинной в 5 символов в одной группе, строки в 10 символов в другой группе (на самом деле кол-во знаков в строке может быть любым). Мне честно говоря, не совсем понятен алгоритм, но ответ в калькуляторе Питон дожен быть таким:

{'h': 5, 'j': 10, 'v': 20}

То есть значением будет длина строки...

Я написала пока так:

Код


a = []
dict = {}
while True:
    s = raw_input(">>>")
    if not s:
        break
    a.append(s)
i = 0
while i < len(a):
    s = a[i]
    j = 0
    while j < len(s):
        c = s[j]

Что дальше делать?

Автор: V.A.KeRneL 4.2.2007, 12:05

Меня вот лично такое описание задачи чё-то тока запутало!.. (Препод Paranorma'ы, притча во языцах, очевидно, постарался smile

Цитата(Paranorma @ 4.2.2007, 00:35

)

{'h': 5, 'j': 10, 'v': 20}

То есть значением будет длина строки...

Это понятно, но вот что означают 'h', 'j' и 'v'? Первые символы строк, самые частые симолы в строках, что-то другое?..

==========================================================================================

Могу написать сортировку слов по длине без использования словаря, с использованием стандартной функции sort():

Код


# -*- coding: windows-1251 -*-

# 
# Сравнивает две строки по их длинам.
# 
def len_compare(str1, str2): 
    return (len(str1) - len(str2))

a = []

while True: 
    s = raw_input(">>>")
    if (not s): 
        break
    a.append(s)
#print a



#"""
# Преобразовываем список введённых строк в список слов.
b = " ".join(a).split()
#print b

# Собственно, сортируем список слов.
b.sort(len_compare)
print b
#"""



"""
tmp = [[str, len(str)] for str in " ".join(a).split()]
#print tmp
tmp.sort(lambda t1, t2: (t1[1] - t2[1]))
#print tmp
b = [tt[0] for tt in tmp]
print b
"""

Закомментарен ("""...""") способ более эффективный для сортировки больших списков, для сортировки которых требуется большое количество сравнений. Его экономичность заключается в однократном вычислении длины для каждого из слов.

==========================================================================================

Можно и самому сортировку написать, реализующую один из стандартных методов (пузырьком, вставками, слиянием, выбором, пирамидальная, быстрая)... В принципе, можно и гномьей, она прикольная! smile

==========================================================================================

Но если надо именно при помощи словаря, то необходимо более подробно и, главное, понятно расписать задание.

Автор: Paranorma 4.2.2007, 14:49

Спасибо большое, меня препод малость ввел в заблуждение. Препод просто не так давно занялся преподаванием, а потому, не имея опыта, иногда нечетко формулирует мысли. Я сегодня у него уточнила.

Должно выглядеть так:

Введенный список: ["123", "45" "abcd", "xy", "klm"]
Результат: { 2:["45", "xy"], 3:["123", "klm"], 4:["abcd"] }

Ключ - длинна строки, значение - список слов данной длинны.

Автор: V.A.KeRneL 4.2.2007, 17:37

Нда, твоего бы препода...

Код


# -*- coding: windows-1251 -*-

a = []

while True: 
    s = raw_input(">>>")
    if (not s): 
        break
    a.append(s)
#print a

# Преобразовываем список введённых строк в список слов.
b = " ".join(a).split()
#print b

# Создание словаря.
d = dict()
for word in b: 
    key = len(word)
    if (not d.__contains__(key)):  # if (not key in d): 
        d[key] = [word]
    else: 
        d[key] += [word]

# Вывод результата (словаря) на экран.
print d

З.Ы. Paranorma, если ты таки хочешь когда-нибудь как-нибудь научиться хотя бы кодить (программирование — это не только кодинг), то учись юзать встроенную справку и google.com, а если нет, то так держать.

Автор: Strannik 4.2.2007, 18:14

Цитата

В принципе, можно и гномьей, она прикольная!

Это что за сортировка такая? Я тоже знаю прикольную сортировку, за О(N!).

Автор: Void 4.2.2007, 18:45

Код

def len_compare(str1, str2): 
    return (len(str1) - len(str2))

b.sort(len_compare)

Код

b.sort(key = len)

Автор: V.A.KeRneL 4.2.2007, 18:45

Цитата(Strannik @ 4.2.2007, 18:14

)

Цитата

В принципе, можно и гномьей, она прикольная!

Это что за сортировка такая? Я тоже знаю прикольную сортировку, за О(N!).

Не, гномья не крэйзи, она нормальная. Довольно новая просто, не классическая. Она работает за время O(n^2), на практике обычно немного медленнее, чем пузырьковая, хотя это уже зависит от особенностей архитектуры системы и реализации алгоритма. Отличается исключительной простотой и лаконичностью кода:

Код


void gnomesort(int n, int ar[]) {
    int i = 0;
    
    while (i < n) {
        if (i == 0 || ar[i-1] <= ar[i]) i++;
        else {int tmp = ar[i]; ar[i] = ar[i-1]; ar[--i] = tmp;}
    }
}

Автор небезосновательно называет своё творение самым простым алгоритмом сортировки.

http://www.google.com/search?hl=en&q=Gnome+Sort&btnG=Google+Search
http://en.wikipedia.org/wiki/Gnome_sort
http://www.cs.vu.nl/~dick/gnomesort.html (она же была первой ссылкой в Гугле)
http://www.nist.gov/dads/HTML/gnomeSort.html
http://keithdevens.com/wiki/n-squared-sort-comparison

Цитата(Strannik @ 4.2.2007, 18:14

)

Это что за сортировка такая? Я тоже знаю прикольную сортировку, за О(N!).

Да, и я знаю такие «алгоритмы». Но вот это уже, по-моему, действительно, глупость, потому что верхний предел сложности не ограничен и при желании можно придумывать всё более сложные алгоритмы, например за время N^N^...^N (N paз), или (((N!)!)...)!, далее можно комбинировать/композиционировать эти функции, и т.д.

Автор: Paranorma 4.2.2007, 21:45

Цитата(V.A.KeRneL @ 4.2.2007, 17:37)

Нда, твоего бы препода...

Код


# -*- coding: windows-1251 -*-

a = []

while True: 
    s = raw_input(">>>")
    if (not s): 
        break
    a.append(s)
#print a

# Преобразовываем список введённых строк в список слов.
b = " ".join(a).split()
#print b

# Создание словаря.
d = dict()
for word in b: 
    key = len(word)
    if (not d.__contains__(key)):  # if (not key in d): 
        d[key] = [word]
    else: 
        d[key] += [word]

# Вывод результата (словаря) на экран.
print d

Всем спасибо!
Блин! Нет, я все понимаю, конечно, просто, пожалуйста, помогите на начальных этапах.
Есть пара вопросов:
Во-первых, что значит эта строка b = " ".join(a).split() Конкретно, что значит join?

Я тут буквально одну строку в программе поправила:

Код


key = len(word)
    if (not key in d):
        d[key] = [word]

И еще один вопрос: как сделать, что б и пробел учитывался как символ строки?

Вот пример:
Список:
["12 3", "4 5", "abcd", "xy", "klm"]
Результат:
{2:["xy"], 3:["4 5", "klm"], 4:["12 3", "abcd"] }

Еще раз прошу меня простить и заранее всем спасибо! smile

Автор: Strannik 4.2.2007, 23:16

V.A.KeRnel, эту сортировку я знал, только не знал что она гномья. А так, пузырёк - 4 строчки да и вообще я почти всегда кучу пишу, для тренировки.

Автор: V.A.KeRneL 4.2.2007, 23:23

Цитата(Paranorma @ 4.2.2007, 21:45

)

Всем спасибо!

Пожалуйста. smile

Цитата(Paranorma @ 4.2.2007, 21:45

)

Блин! Нет, я все понимаю, конечно, ...

Крута-а-а!.. Научи! А то я мало, что знаю и понимаю. Чуть перефразируя известное изречение: «Единиственное, что я знаю, это то, что я нихрена не знаю. ))»

Цитата(Paranorma @ 4.2.2007, 21:45

)

... просто, пожалуйста, помогите на начальных этапах.

ОК. Тока заруби на носике, что эти пресловутые «начальные этапы» не могут длиться вечно. На практике они не должны затягиваться более, чем на полгода (в крайнем случае год). Далее надо уметь пользоваться документацией (естественно, большая и самая ценная её часть представлена на английском языке — современном международном и программистском профессиональном языке) и поисковиками.

Цитата(Paranorma @ 4.2.2007, 21:45

)

что значит эта строка b = " ".join(a).split() Конкретно, что значит join?

Вот тут и надо воспользоваться http://www.google.com/search?hl=en&q=python+join&btnG=Google+Search, потыкать по ссылочкам с 1-ой страницы, среди них найти что-нибудь вроде http://www.wellho.net/resources/ex.php4?item=y108/bejo.py:
split and join
Example from a Well House Consultants training course
SOURCE CODE

Код


>>> days = ["Monday","Tuesday","Webnesday"]
>>> all = "<br>".join(days)
>>> print all
Monday<br>Tuesday<br>Webnesday
>>>
>>> if "o" in "Melksham": print "yes"
...
>>> say = "This is a line of text"
>>> parts = say.split(" ")
>>>
>>> first, second = "Tom Smiota".split(" ")
>>> second, first = first, second
>>>
>>> print parts
['This', 'is', 'a', 'line', 'of', 'text']
>>> print first
Smiota
>>> print second
Tom

Если непонятно, то скажу, что метод sep.join(list) возвращает строку из списка слов `list', сцеплённого разделителями `sep', а метод str.split([sep]), напротив, разбивает строку `str' [по разделителю `sep'] на слова (строки).

Цитата(Paranorma @ 4.2.2007, 21:45

)

как сделать, что б и пробел учитывался как символ строки?

Вот пример:
Список:
["12 3", "4 5", "abcd", "xy", "klm"]
Результат:
{2:["xy"], 3:["4 5", "klm"], 4:["12 3", "abcd"] }

Так как сделат-то нужно, чтобы в списке были не слова, как в предыдущей твоей задаче, а полные введённые пользователем строки? Если так, то строки ``b = " ".join(a).split()'', как раз, и не надо, а нужно проходиться циклом по списку `a': ``for word in a: ''

Цитата(Paranorma @ 4.2.2007, 21:45

)

Еще раз прошу меня простить и заранее всем спасибо! smile

Обращайся. smile

Автор: Strannik 4.2.2007, 23:32

Цитата

Тока заруби на носике, что эти пресловутые «начальные этапы» не могут длиться вечно.

Хи, а у меня начальный этап в изучении С++ продлился 3,5дня, т.к. вчера я уже участвовал в SRM на TopCoder. Для того что бы выучить язык(программирования) нужно кроме литературы и гугла как можно больше говорить(программировать) на нём.

Добавлено @ 23:35
V.A.KeRnel, Интересно, а почему все темы Paranorma'ы плавно переходят в наш с тобой оффтоп???

Автор: Paranorma 5.2.2007, 00:14

Значит вы любители оффтопа smile

на самом деле я питоном только 3 месяца балуюсь, поэтому и прошу у вас помощи так часто.

Автор: Paranorma 5.2.2007, 13:54

Please, help! Помогите это поправить. У меня на печать выводиться только последняя введенная строка, вместо всех введенных. Да тут именно введенные строки уже, а не слова, как в прошлый раз.

Код


a = []
while True: 
    s = raw_input(">>>")
    if (not s): 
        break
    a.append(s)
b = " ".join(a).split()
d = dict()
for word in b: 
    key = len(word)
    if (not key in d):
        d[key] = [word]
    else: 
        d[key] += [word]
print d

Автор: V.A.KeRneL 5.2.2007, 15:15

Код


a = []

while True: 
    s = raw_input(">>>")
    if (not s): 
        break
    a.append(s)

d = dict()
for line in a: 
    key = len(line)
    if (not key in d): 
        d[key] = [line]
    else: 
        d[key] += [line]

print d

Так что ли?
(Строки должны все выводиться нормально...)

Автор: Paranorma 5.2.2007, 16:00

Нижайший всем поклон smile

Автор: pythonwin 10.2.2007, 14:25

Paranorma, ты решила проблему?
покажи, пожалуйста, работающий код.

это не флейм - цель сделать архив в ЦП по языкам, в данном случае по питону smile

тема обсуждается http://forum.vingrad.ru/topic-130354/kw-%F6%E5%ED%F2%F0-%F4%E8%EB%FC%F2%F0.html

Автор: Paranorma 10.2.2007, 17:22

Код


a = []
while True: 
    s = raw_input(">>>")
    if not s: 
        break
    a.append(s)
d = {}
for s in a: 
    key = len(s)
    if key not in d: 
        d[key] = [s]
    else: 
        d[key] += [s]
print d