Кодируйте гольф: найдите все анаграммы

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

Задача:

  • Самый короткий исходный код по количеству символов для поиска всех наборов анаграмм по списку слов.

  • Пробелы и новые строки должны считаться символами

  • Используйте линейку кода

    ---------10--------20--------30--------40--------50--------60--------70--------80--------90--------100-------110-------120

Вход:

список слов из стандартного ввода, где каждое слово отделено новой строкой.

e.g.

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's plum's
dewar's wader's
postman tampons
dent tend
macho mocha
stoker's stroke's
hops posh shop
chasity scythia
...

У меня есть решение на 149 символов на perl, которое я опубликую, как только опубликуют еще несколько человек :)

Развлекайся!

РЕДАКТИРОВАТЬ: Разъяснения

  • Предположим, что анаграммы нечувствительны к регистру (т.е. буквы верхнего и нижнего регистра эквивалентны)
  • Следует печатать только наборы с более чем 1 шт.
  • Каждый набор анаграмм следует распечатывать только один раз.
  • Каждое слово в наборе анаграмм должно встречаться только один раз.

EDIT2: дополнительные пояснения

  • Если два слова различаются только заглавными буквами, они должны быть свернуты в одно и то же слово, и вам решать, какую схему использования заглавных букв использовать для свернутого слова.
  • наборы слов должны заканчиваться только новой строкой, если каждое слово каким-либо образом разделено, например допустимы разделенные запятыми или пробелами. Я понимаю, что в некоторые языки встроены методы быстрой печати массивов, поэтому это должно позволить вам воспользоваться этим, если он не выводит массивы, разделенные пробелами.

person Community    schedule 02.04.2010    source источник
comment
Похоже, решение на Прологе можно сделать довольно быстро.   -  person JesperE    schedule 02.04.2010
comment
Прописные и строчные буквы эквивалентны или нет?   -  person Dan Andreatta    schedule 02.04.2010
comment
Печатать только наборы с более чем одним элементом?   -  person Dan Andreatta    schedule 02.04.2010
comment
Два вопроса: 1) Если в списке слов есть одно и то же слово дважды, но в разных случаях, Азалия и Азалия, считается ли это анаграммой (как и большинство решений, приведенных ниже), или их нужно свернуть в одно слово, и если других анаграмм нет, не выводить? 2) Должен ли выходной формат точно соответствовать указанному выше? Или будет приемлем вывод по строкам вроде «[верстальщик, полемист]»?   -  person MtnViewMark    schedule 02.04.2010
comment
Вы должны явно добавить требование кратчайшего кода к вопросу meta.stackexchange.com/questions/24242   -  person John La Rooy    schedule 03.04.2010
comment
@mtnviewMark 1. они должны быть свернуты в 1 слово 2. до тех пор, пока каждый набор заканчивается новой строкой, так что да, это нормально. @gnibbler, спасибо, добавлю это   -  person Charles Ma    schedule 03.04.2010
comment
Полагаю, мне очень жаль, что я спросил :-P Ни одна из представленных мной работ сейчас не проходит, включая мою, поскольку, учитывая список слов с азалией и азалией, они напечатают строку с этими двумя словами как анаграммы, а не свернут их . Тьфу ...   -  person MtnViewMark    schedule 03.04.2010


Ответы (8)


Powershell, 104 97 91 86 83 символа

$k=@{};$input|%{$k["$([char[]]$_|%{$_+0}|sort)"]+=@($_)}
$k.Values|?{$_[1]}|%{"$_"}

Обновление для нового требования (+8 символов):

Чтобы исключить слова, которые отличаются только заглавными буквами, мы могли бы просто удалить дубликаты (без учета регистра) из входного списка, то есть $input|sort -u, где -u означает -unique. sort по умолчанию не учитывает регистр:

$k=@{};$input|sort -u|%{$k["$([char[]]$_|%{$_+0}|sort)"]+=@($_)} 
$k.Values|?{$_[1]}|%{"$_"} 

Объяснение [char[]]$_|%{$_+0}|sort -части

Это ключ для записи в хеш-таблице, под которой хранятся анаграммы слова. Мое первоначальное решение было: $_.ToLower().ToCharArray()|sort. Затем я обнаружил, что мне не нужен ToLower() для ключа, так как поиск в хэш-таблице нечувствителен к регистру.

[char[]]$_|sort было бы идеально, но сортировка символов для ключа должна быть нечувствительной к регистру (иначе Cab и abc будут храниться под разными ключами). К сожалению, sort не учитывает регистр для символов (только для строк).

Нам нужно [string[]][char[]]$_|sort, но я нашел более короткий способ преобразования каждого символа в строку, который состоит в том, чтобы связать с ним что-то еще, в данном случае целое число 0, следовательно, [char[]]$_|%{$_+0}|sort. Это не влияет на порядок сортировки, и фактический ключ оказывается примерно таким: d0 o0 r0 w0. Это некрасиво, но работает :)

person Community    schedule 02.04.2010
comment
Этот Powershell начинает меня пугать;) - person Dan Andreatta; 02.04.2010
comment
Я принимаю это, потому что 1. он соответствует всем требованиям 2. это самый высокий голос за ответ и 3. Я не видел много игр в гольф с помощью Power Shell code :) - person Charles Ma; 04.04.2010

Perl, 59 символов

chop,$_{join'',sort split//,lc}.="$_ "for<>;/ ./&&say for%_

Обратите внимание, что для этого требуется Perl 5.10 (для функции say).

person Community    schedule 02.04.2010
comment
Perl 5.10 на моей машине говорит: «Оператор или точка с запятой отсутствует перед &» в строке 1 ana-perl.pl. Неоднозначное использование & разрешено в качестве оператора & в строке 1 ana-perl.pl. - person MtnViewMark; 03.04.2010
comment
@MtnViewMark: Для защиты обратной совместимости функции, добавленные в Perl в версии 5.10, должны быть явно включены: perl -M5.010 ana-perl.pl < wordlist Как это должно повлиять на результаты игры в гольф, остается спорным. - person Michael Carman; 04.04.2010

Haskell, 147 символов

предыдущие размеры: 150 159 символов

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

Эта версия обрабатывает:

  1. Слова во входных данных, которые отличаются только регистром, должны считаться только одним словом.
  2. В выводе должна быть одна анаграмма для каждой строки, но допустимо использование дополнительных знаков препинания.
person Community    schedule 02.04.2010
comment
Просто моя первая попытка - я уверен, что выжать можно. - person MtnViewMark; 02.04.2010
comment
Так приятно видеть, что что-то близкое к идиоматичному, читабельному Haskell также неплохо показывает себя в гольф-коде! - person Thomas; 03.04.2010
comment
Согласен, наверное, это мой любимый ответ :) - person Charles Ma; 04.04.2010

Рубин, 94 символа

h={};(h[$_.upcase.bytes.sort]||=[])<<$_ while gets&&chomp;h.each{|k,v|puts v.join' 'if v.at 1}
person Community    schedule 02.04.2010
comment
Это довольно похожий на Perl подход, поэтому я ожидаю, что кто-нибудь сможет отбросить как минимум 5-10 символов с помощью Perl-решения. - person Mark Rushakoff; 02.04.2010

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]))
person Community    schedule 02.04.2010
comment
Удалите пробел между : и print и используйте точку с запятой. Я думаю, вы могли бы использовать input(). - person kennytm; 02.04.2010
comment
Это дает результаты с учетом регистра. Сравните с Дэном Андреаттой или моими решениями. - person Mark Rushakoff; 02.04.2010
comment
Исправлено, теперь нечувствительность к регистру была указана как обязательная. - person Amber; 02.04.2010
comment
Python 2.6.1 на моей машине утверждает: NameError: имя 'lower' не определено - person MtnViewMark; 03.04.2010
comment
Да, это была ошибка с моей стороны, я ее исправил (должно быть .lower() вместо lower(...)). - person Amber; 03.04.2010

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, иначе она могла бы быть короче ...

Прописные и строчные буквы считаются разными.

person Community    schedule 02.04.2010
comment
Будет ли это печатать только слова, которые являются анаграммами? Или он также будет печатать слова без других анаграмм на своих строках? - person Amber; 02.04.2010
comment
Исходная версия печатает все. Обновите с исправлением. - person Dan Andreatta; 02.04.2010
comment
Я думаю, это должно быть только для Gnu awk (gawk). Стандартный awk не имеет функции asort. - person MtnViewMark; 03.04.2010

C ++, 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";}
person Community    schedule 02.04.2010
comment
Примечания: (1) Фактическое количество, как показано, немного выше, потому что я добавил некоторые символы новой строки для удобства чтения (main () может быть на одной строке) (2) Слегка сжатая, но читаемая версия: codepad.org/JtB1AHrE - person TC.; 02.04.2010

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])
person Community    schedule 02.04.2010
comment
Это ... невероятно медленно. : P Он также выводит каждый набор анаграмм несколько раз, что равно количеству анаграмм в наборе. - person Amber; 02.04.2010
comment
(Да, и он также выводит отдельные слова, которые не являются анаграммами в отдельной строке, которая, похоже, не является частью указанного вывода.) - person Amber; 02.04.2010
comment
Почему ; в конце строки, это не Python! - person Tony Veijalainen; 05.10.2010