# Solve an Anagram

You will be given a string of lowercase ASCII letters. Using this dictionary file (UPDATED), your task is to solve the anagram. To solve an anagram, you must output all words or groups of words that can be formed using each letter from the input string exactly once, separated by newlines. Groups of the same words in a different order are not unique and should not be output separately; however, the order of the words does not matter. The order of output solutions also does not matter. If the input cannot form a word, output nothing.

Some useful test cases:

Input:  viinlg
Output: living

Input:  fceodglo
Output: code golf

Input:  flogflog
Output: golf golf

Input:  ahwhygi
Output: highway
high way

Input:  bbbbbb
Output:


Rules/caveats:

• You may access the dictionary list any way you like. Command line argument, stdin, reading from file, or reading from internet are all acceptable.

• Input will consist of lowercase ASCII letters only. You are not required to output results in any particular case.

• You will not be given a string that already forms a valid word (you may, however, be given a string that forms multiple words, such as bluehouse).

• Trailing newlines are allowed but not required.

• Standard loopholes apply.

This is . Shortest code in bytes wins. Good luck!

• Sandbox post. – scatter Jun 19 '17 at 14:59
• Should we use 1 space to separate sets of words or any non-letter separator suffices? – Erik the Outgolfer Jun 19 '17 at 16:19
• @EriktheOutgolfer To separate sets of words, any separator is fine; however you should still separate words within a single solution with a space. – scatter Jun 19 '17 at 17:21
• @Christian Rules say you must separate sets of words with newlines though. – Erik the Outgolfer Jun 19 '17 at 17:24
• @EriktheOutgolfer Then why did you ask "Should we use 1 space to separate sets of words"? Your question confused me, and there should be no reason to prefer anything over newlines for separating sets. I'd say stick to the spec. – scatter Jun 19 '17 at 17:27

# Python 3, 248 202 bytes

from itertools import*
A=set()
def f(s,*G,i=1,A=A):
if' '>s:A|={' '.join(sorted(G))}
for _ in s:s[:i]in S and f(s[i:],s[:i],*G);i+=1
I,*S=iter(input,'')
for p in permutations(I):f(''.join(p))
print(A)


Try it online!

### Input is as follows:

word_input
dic_entry_1
dic_entry_2
....
dic_entry_N
# <<< empty line + \n


### Speeding it up:

For testing purposes, if you change from I,*S=iter(input,'') to I=input();S=set(iter(input,'')), the runtime will be reduced drastically and the output will be the same.

### Explanation:

In every permutation of the input, it tries to split recursively the permutation in all possible locations, starting from left to right, without skipping letters, with words that are in the dictionary. If a split combination matches all the input permutation, the split words are sorted and added to a set that will be printed at the and of the evaluation.

# Python 2, 341327337 320 bytes

This solution assumes the dictionary is stored in a variable w as a set of strings. The first set of combinations does not need to use combinations_with_replacement, but using the latter saves bytes.

from itertools import*
d,o,j,c={},sorted,''.join,combinations_with_replacement
s,w=o(raw_input()),input()
l=len(s)
r=range(l)
for x in w:d.setdefault(j(o(x)),[]).append(x)
b=set(chain(*[d[j(x)]for y in r for x in c(s,y+1)if j(x) in d]))
print'\n'.join(' '.join(x)for y in r for x in c(b,y+1)if(len(j(x)),o(j(x)))==(l,s))


Try it online!

Input - Anagrammed word followed by the dictionary of words as a set:

anagram_word
{'entry1', 'entry2', ...., 'entryN'}


Edit: Updated Inputs.

# Javascript, 139137 129 Bytes

-2 Bytes thanks to @FelipeNardiBatista

-8 Bytes thanks to reading the docs ;)

k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])}


Takes in the dictionary as input in form of an array of strings.

var arr = ["living", "code", "golf", "highway", "high", "way"];

var _=
k=>w=>{t=w;return k.reduce((a,v)=>{r=([...v].every(c=>w.includes(c)&&((w=w.replace(c,""))||!0)))?a.concat(v):a;w=t;return r},[])};

console.log(_(arr)("viinlg"));
console.log(_(arr)("fceodglo"));

Explanation:

For every word in dictionary, check if every letter is contained in the chosen word, while simultaneously removing it from the word. At the end of every dictionary entry, restore the word to its unaltered state to check for further matches.

• @FelipeNardiBatista You're right, I forgot to golf that name. Thanks :) – Hankrecords Jun 21 '17 at 9:44