Find imperfect anagrams

Question

The goal of this challenge is to write a program which takes a string (of any length) as input and displays anagrams (see these examples of anagrams) of this string, made by taking words in a dictionary (either individually or in pairs), but the anagrams don't need to be perfect.

An anagram is the result of a rearrangement of a set of characters:

• ABCD and CADB are perfect anagrams, all the characters are present in both strings
• ABCD and CADBEF are imperfect anagrams because the characters ABCD are present in both strings but the characters EF only exist in the second string

The dictionary contains 1949 words:

ability
able
aboard
etc.

By taking each word and each pair of distinct words we generate a list of candidates to compare against the input:

ability
ability able
ability aboard
ability ...
able
able aboard
able ...
...

The program must display only the strings from the previous list which are anagrams of the input string. In other words, the program needs to filter the candidates down to the imperfect anagrams of the input.

Examples

Input

Sample:

> your_program 85 "Meta Code Golf" ./dict.txt

You may take input from any method you like, be it command line arguments or stdin.

Expected output

ExCLAiMED FOOT
FrEEDOM LOCATe

(if I didn't make any mistake in my code)

Rules

Input:

n string filepath

(You may take input from any method you like, be it command line arguments or stdin)

• The first input will be an integer n. This is a threshold to define the minimum percentage of characters which must be present in the string input and the anagrams. n will be between 0 and 100, inclusive
• The second input will be a string (a string with one or more words)
• The path to a file containing one word per line. The dictionary to use is available here (**), it contains 1949 common words (source). You have to save this file without the comments to keep one word per line

**: I chose to use only 1949 common words because the dictionaries like wamerican package (with Ubuntu it adds the /usr/share/dict/american-english file) contains about 100,000 words, this would lead to 10,000,000,000 possible combinations of 2 words. It may take to much time to compute in the context of code golfing. But a program which works with 2,000 words may still work with 100,000 words if someone wants to use all the words from a complete dictionary.

Output:

• One matching anagram string per line. The matching letters between the input string and the anagram must be displayed in uppercase, and the non-matching letters must be lowercase. In the example, only 2 of the 3 e are in uppercase, because there are only 2 e in Meta Code Golf
• You must not display the same anagram twice (eg. ExCLAiMED FOOT and FOOT ExCLAiMED are both valid but they are only the result of a swap between the 2 words)

Other rules:

• Comparison between input string and anagrams:
  • Lower and upper-case characters are considered as the same character when searching the anagrams
  • Non-letter characters (space), -, etc. are considered as one character
• Standard “loopholes” are forbidden
• Shortest code wins

Similarity index and threshold

Similarity index:

The similarity index (SI) is calculated by counting the number of times each character from a string appear in another string. So we have to compute 2 SIs if the 2 strings have different lengths.

Examples

ABCD and CADB are perfect anagrams, the characters are identical, the SI is 100%

ABCD and CADBEF: - ABCD in CADBEF: the SI is 100% because all the characters of the first string exist in the second string - CADBEF in ABCD: the SI is 4/6 because ABCD are present in the second string (and not E and F)

You have to ensure that you compare the input with the word and the word with the input, otherwise the word AAABBBCCCDDDEEE (etc.) may match the vast majority of the words. So we have to check that the 2 SIs are greater or equal than the threshold in order to accept an anagram.

Example of SI function (pseudo-code):

function SI(a, b) {
    s_i = 0

    foreach (character in a) {
        if (character exists in b) {
            remove the character in b /* avoid to find several times "AAAA" in "A" */
            s_i++
        }
    }

    return(s_i / length(a))
}

Threshold

The threshold acts as a filter to display only the anagrams which SI is greater or equal than the threshold.

To apply the threshold, we must use this function twice:

if ((SI(input, candidate) >= threshold) && (SI(candidate, input) >= threshold)) {/* anagram is ok */}

Examples:

Threshold = 100

> program 100 "explanation" ./dict.txt
EXPLANATION

There is only one result because there is no perfect anagram for Explanation, except the word itself.

Threshold = 90

> program 90 "explanation" ./dict.txt
ALONE PAINT
EXPLAIN NOT
EXPLANATION
NATION PALE

Threshold = 75

> program 75 "explanation" ./dict.txt
AbLE cONTAIN
AbLE NATION
AbOuT EXPLAIN
AcT EXPLAIN
AcTION ALoNE
AcTION ANgLE
...

Threshold = 0

> program 0 "Meta Code Golf" ./dict.txt
AbILiTy
AbILiTy AblE
AbILiTy AbOard
AbILiTy AbOut
...

It will display all the words and all the combination of words from the dictionary (because all the SIs are greater or equal than the threshold).

Random example

> program 85 "Beyonce Knowles" ./dict.txt
BEtWEEN COLONY
COWBOY SENtENcE

---

I was inspired by a french TV program named Le Complot where they make funny correlations between two unrelated persons, ideas, etc. For example, they showed that the soccer player Pastore is an anagram of Apotres (the french word for Apostles) in order to link Zlatan Ibrahimovic to Catholic Church.

Answer 1

Python 2, 375 ... 313

S=lambda a,b:1.*len([b.remove(q)for q in a if q in b])/len(a)
T=lambda a,b:min(S(a,b[:]),S(b,a[:]))
t,s,d=input()
d=open(d).read().split()
for x in{' '.join(sorted([a,b]))for a in d for b in d}|set(d):
 q=list(s.lower())
 if T(list(x),q)*100>=t:print''.join([w,w.upper()][q.count(w)and not q.remove(w)]for w in x)

This expects slightly different input; like so: 90, "explanation", "dict.txt". If that's not allowed, I'll fix it.

Sample run, with stdin 90, "explanation", "dict.txt":

EXPLANATION
NATION PALE
EXPLAIN NOT
ALONE PAINT

This works by iterating through a set of all the possibilities, checking them. This is what makes it so slow.

S=lambda a,b:1.*len([b.remove(q)for q in a if q in b])/len(a) # define the SI function
  lambda a,b:                                                 # define a lambda with 2 inputs
                     b.remove(q)for q in a if q in b          # for q in a, if q is in b, remove q from b
                len([                               ])        # list.remove returns None, so collect all the removes and the resulting list will have len of the number of times we removed things
             1.*len([b.remove(q)for q in a if q in b])/len(a) # 1.* converts the len to a float, so that when we divide by len(a), we get a float

T=lambda a,b:min(S(a,b[:]),S(b,a[:])) # Determine the min SI for both possibilities
                 S(a,b[:]),           # run S with a and a copy of b; since b gets removes called in S
                           S(b,a[:])  # run S with b and a copy of a
             min(S(a,b[:]),S(b,a[:])) # get the min of those values

t,s,d=input()
d=open(d).read().split() # read the dict file and split it on newlines, creating a list of words

for x in{' '.join(sorted([a,b]))for a in d for b in d}|set(d): # iterate over possible word choices
                         [a,b]  for a in d for b in d          # create all possible pairs of words
                  sorted(     )                                # sort the list, making it so that ['exclaimed', 'foot'] and ['foot', 'exclaimed'] make the same element
         ' '.join(             )                               # combine the words with a space between
        {                                            }         # turn into set; this is a set comprehension
                                                      |set(d)  # take the union of that set and the set of single words.
for x in                                                     : # this is what we iterate over

 q=list(s.lower()) # we want to convert our string to lowercase, but we also want it as a list of characters because str doesn't have a remove function.

 if T(list(x),q)*100>=t: # decide if the element of the set matches the threshold
                        print''.join([w,w.upper()][q.count(w)and not q.remove(w)]for w in x) # it does; now we print the correct output
                                     [w,w.upper()]                               for w in x) # consider both the lower/uppercase versions of the char in the string
                                                  [q.count(w)and not q.remove(w)]            # if w appears at least once in the target string, we remove it from the target string, and do a logical negation on the None, resulting in True ie 1, so we choose uppercase
                             ''.join(                                                      ) # join these elements back into a string
                        print                                                                # print the result

Answer 2

Python 3 - 447

Again, this is one of these programs that takes a long time to test, but I'll add one of the test cases once it's done.

from sys import*
l=argv
e=''
t=[]
v=list
n='\n'
g=open(l[3]).read()
def s(a,b):
 m=0;a=list(a)
 for i in a:
  if i in b:b.remove(i);m+=1
 return m/len(a)*100
for i in g.split(n):
 for j in(n+g).split(n):
  a=i+' '+j if j!=''else i
  b=l[2].lower();c='';d=v(b);w=set(b.split(' '))
  t=l[1]
  if(s(a,d)>=t)and(s(d,v(a))>=t):
   if not w in t:
    for k in a:
     if k in d:d.remove(k);c+=k.upper()
     else:c+=k
    t.append(w)
    e+=c+n
print(e)

Edit

The latest edit accounts for the rule that states that you must not print different arrangements of the two words.

Answer 3

Perl 5 - 166 158 146 143

4 of the new line characters are added for clarity (those following a semicolon).

$s.=lc"+s/$_/uc\$&/e"for($i=pop)=~/[a-z]| (?!.* )/ig;
$/=pop;
$_=<>;
s!.+!"$&".join"
$& ",$'=~/^|.+/g!ge;
100*eval$s<$/*length($_|$i)||print"$_
"for split'
'

The array based candidate generation actually proved to be shorter than my original string substitution one. Kept the previous 153 version as its output order is exactly as in the examples (though it is not required).

$s.=lc"+s/$_/uc\$&/e"for($i=pop)=~/[a-z]| (?!.* )/ig;
$z=pop;
100*eval$s<$z*length($_|$i)||print"$_
"for map{map$&." $_"x!/^$&$/,@s=(@s,/.+/g)}<>

Usage:

perl ./a.pl 90 "explanation" <dict.txt

Edit

This version should conform to the specification with regard to non letter characters.

Answer 4

R - 512 (= 2⁹!)

v=function(a){unlist(strsplit(tolower(a),""))}
s=function(a,b){
s=0;for(l in a){if(l%in%b){b=b[-(which(l==b)[1])];s=(s+1)}};s/length(a)}
r=function(v,j){p=c();for(l in v){if(l%in%j){j=j[-(which(l==j)[1])]
o=toupper(l)}else{o=tolower(l)};p=c(p,o)};cat(p,"\n",sep="")}
a=commandArgs(T);j=v(a[2]);k=(as.integer(a[1])/100);
d=scan(a[3],what='raw',sep="\n",quiet=T);
for(w in d){t=v(w);if((s(t,j)>=k)&&(s(j,t)>=k)){r(t,j)};
for(x in d[-1]){w2=paste(w,x,sep=" ");t=v(w2)
if((s(t,j)>=k)&&(s(j,t)>=k)){r(t,j)}};d=d[-1]}

Ungolfed

get_array = function (a) {unlist(strsplit(tolower(a),""))}

# calculate similarity index of 2 strings
get_s = function (a, b) {
    s = 0
    for (letter in a) {
        if (letter %in% b) {
            b = b[-(which(letter == b)[1])]
            s = (s + 1)
        }
    }
    return(s / length(a))
}

# output
get_result = function (var_string, input) {
    output = c()

    for (letter in var_string) {
        if (letter %in% input) {
            input = input[-(which(letter == input)[1])]
            o = toupper(letter)
        }
        else
        {
            o = tolower(letter)
        }
        output = c(output, o)
    }
    cat(o, "\n",sep="")
}

# get arguments
a = commandArgs(T)
input = get_array(a[2])
threshold = (as.integer(a[1]) / 100)
dict = scan(a[3], what='raw', sep="\n", quiet=T)

# iterate through all the words from the dictionary
for (w in dict)
{
    t = get_array(w)

    # the word only
    if (
        (get_s(t, input) >= threshold)
        &&
        (get_s(input, t) >= threshold)
    )
    {
        get_result(t, input)
    }

    # the word + another word
    for (x in dict[-1]) {
        w2 = paste(w, x, sep=" ")
        t = get_array(w2)
        if (
            (get_s(t, input) >= threshold)
            &&
            (get_s(input, t) >= threshold)
        )
        {
            get_result(t, input)
        }
    }

    dict = dict[-1] # remove the word once it has be permuted with all the other words
}