Code golf: найти все анаграммы
Слово anagram, если буквы в этом слове могут быть перегруппированы, чтобы сформировать другое слово.
Задача:
Вход:
a список слов из stdin с каждым словом, разделенным новой строкой.
например.
A
A's
AOL
AOL's
Aachen
Aachen's
Aaliyah
Aaliyah's
Aaron
Aaron's
Abbas
Abbasid
Abbasid's
Вывод:
Все наборы анаграмм, причем каждый набор разделяется отдельной строкой.
Пример выполнения:
./anagram < words
marcos caroms macros
lump plum's
dewar wader's
postman tampons
dent tend
macho mocha
stoker stroke's
hops posh shop
chasity scythia
...
У меня есть решение 149 char perl, которое я выложу, как только опубликует еще несколько человек:)
Удачи!
РЕДАКТИРОВАТЬ: Уточнения
- Предположим, что анаграммы нечувствительны к регистру (т.е. буквы верхнего и нижнего регистра эквивалентны)
- Должны быть напечатаны только наборы с более чем 1 элементом.
- Каждый набор анаграмм следует печатать только один раз
- Каждое слово в наборе анаграмм должно появляться только один раз
EDIT2: Дополнительные разъяснения
- Если два слова отличаются только капитализацией, они должны быть свернуты в одно и то же слово, и вам решать, какая схема капитализации использовать для спящего слова
- набор слов должен заканчиваться только в новой строке, если каждое слово разделено каким-либо образом, например. разделенные запятыми или разделенные пробелы. Я понимаю, что некоторые языки имеют встроенные методы печати массива, поэтому это должно позволить вам воспользоваться этим, если оно не выводит массивы, разделенные пробелами.
Ответы
Ответ 1
Powershell, 104 97 91 86 83 символа
[email protected]{};$input|%{$k["$([char[]]$_|%{$_+0}|sort)"][email protected]($_)}
$k.Values|?{$_[1]}|%{"$_"}
Обновление для нового требования (+8 символов):
Чтобы исключить слова, которые отличаются только капитализацией, мы могли бы просто удалить дубликаты (без учета регистра) из списка ввода, т.е. $input|sort -u
, где -u
означает -unique
. sort
имеет значение по умолчанию:
[email protected]{};$input|sort -u|%{$k["$([char[]]$_|%{$_+0}|sort)"][email protected]($_)}
$k.Values|?{$_[1]}|%{"$_"}
Объяснение [char[]]$_|%{$_+0}|sort
-part
Это ключ для записи хеш-таблицы, в которой хранятся анаграммы слова. Моим первоначальным решением было: $_.ToLower().ToCharArray()|sort
. Тогда я обнаружил, что мне не нужен ToLower()
для ключа, так как поиск в хэш-таблице нечувствителен к регистру.
[char[]]$_|sort
был бы идеальным, но сортировка символов для ключа должна быть нечувствительной к регистру (иначе Cab
и abc
будут храниться под разными ключами). К сожалению, sort
не учитывает регистр символов (только для строк).
Нам нужно [string[]][char[]]$_|sort
, но я нашел более короткий способ преобразования каждой строки char в строку, которая заключается в том, чтобы приложить к ней что-то еще, в этом случае целое число 0
, следовательно [char[]]$_|%{$_+0}|sort
. Это не влияет на порядок сортировки, и фактический ключ заканчивается чем-то вроде: d0 o0 r0 w0
. Это не очень, но это делает работу:)
Ответ 2
Perl, 59 символов
chop,$_{join'',sort split//,lc}.="$_ "for<>;/ ./&&say for%_
Обратите внимание, что для этого требуется Perl 5.10 (для функции say
).
Ответ 3
Haskell, 147 символов
предыдущие размеры: 150 159 chars
import Char
import List
x=sort.map toLower
g&a=g(x a).x
main=interact$unlines.map unwords.filter((>1).length).groupBy((==)&).sortBy(compare&).lines
Эта версия на 165 символов удовлетворяет новым, уточненным правилам:
import Char
import List
y=map toLower
x=sort.y
g&f=(.f).g.f
w[_]="";w a=show a++"\n"
main=interact$concatMap(w.nubBy((==)&y)).groupBy((==)&x).sortBy(compare&x).lines
Эта версия обрабатывает:
- Слова на входе, которые отличаются только случаем, должны считаться только одним словом
- Вывод должен быть одним набором анаграмм на строку, но допустима дополнительная пунктуация
Ответ 4
Ruby, 94 символа
h={};(h[$_.upcase.bytes.sort]||=[])<<$_ while gets&&chomp;h.each{|k,v|puts v.join' 'if v.at 1}
Ответ 5
Python, 167 символов, включает ввод/вывод
import sys
d={}
for l in sys.stdin.readlines():
l=l[:-1]
k=''.join(sorted(l)).lower()
d[k]=d.pop(k,[])+[l]
for k in d:
if len(d[k])>1: print(' '.join(d[k]))
Без входного кода (т.е. если мы принимаем список слов уже в списке w
), это всего 134 символа:
d={}
for l in w:
l=l[:-1]
k=''.join(lower(sorted(l)))
d[k]=d.pop(k,[])+[l]
for k in d:
if len(d[k])>1: print(' '.join(d[k]))
Ответ 6
AWK - 119
{split(toupper($1),a,"");asort(a);s="";for(i=1;a[i];)s=a[i++]s;x[s]=x[s]$1" "}
END{for(i in x)if(x[i]~/ .* /)print x[i]}
AWK не имеет функции join
, такой как Python, или она может быть короче...
Предполагается, что в верхнем и нижнем регистре используются разные.
Ответ 7
С++, 542 символа
#include <iostream>
#include <map>
#include <vector>
#include <boost/algorithm/string.hpp>
#define ci const_iterator
int main(){using namespace std;typedef string s;typedef vector<s> vs;vs l;
copy(istream_iterator<s>(cin),istream_iterator<s>(),back_inserter(l));map<s, vs> r;
for (vs::ci i=l.begin(),e=l.end();i!=e;++i){s a=boost::to_lower_copy(*i);
sort(a.begin(),a.end());r[a].push_back(*i);}for (map<s,vs>::ci i=r.begin(),e=r.end();
i!=e;++i)if(i->second.size()>1)*copy(i->second.begin(),i->second.end(),
ostream_iterator<s>(cout," "))="\n";}
Ответ 8
Python, O (n ^ 2)
import sys;
words=sys.stdin.readlines()
def s(x):return sorted(x.lower());
print '\n'.join([''.join([a.replace('\n',' ') for a in words if(s(a)==s(w))]) for w in words])