Find Unique Anagrams

Question

Challenge Description: An anagram is a word or phrase formed by rearranging the letters of another word or phrase. For example, "listen" and "silent" are anagrams. In this challenge, your task is to write a program or function that takes a list of strings as input and returns the unique anagrams.

Write a program or function that takes a list of strings as input and returns the unique anagrams, preserving the order of appearance. Your solution should handle lowercase letters (a-z) only.

Examples:

Input	Output
["cat", "act", "tac", "dog", "god"]	["cat", "dog"]
["a", "ab", "abc", "abcd"]	["a", "ab", "abc", "abcd"]
["cat", "dog", "tac", "god", "act"]	["cat", "dog"]

The input list contains five strings. The strings "cat", "act", and "tac" are anagrams of each other, and "dog" and "god" are anagrams of each other. The output should contain only one representative from each group of anagrams, preserving the order of appearance. Hence, the output is ["cat", "dog"].

Requirements:

The input list can contain duplicate strings, and they should be considered as separate entities. The output should contain only one representative from each group of anagrams, preserving the order of appearance. The input list may contain an arbitrary number of strings. The input list and the output list can be empty.

This is code-golf, so the shortest solution in bytes is the winner.

Good luck!

Answer 1

Jelly, 4 bytes

Ṣ€Ḣƙ

A monadic Link that accepts a list of lists and yields a list of lists containing the first of each anagram.

Try it online!

How?

Ṣ€Ḣƙ - Link: list of lists, Words
Ṣ€   - sort each word
   ƙ - group Words by sorted_words and apply to each:
  Ḣ  -   head

Answer 2

Ruby, 28 bytes

->l{l.uniq{|z|z.chars.sort}}

Try it online!

Answer 3

Vyxal, 32 bits^v1, 4 bytes

⁽sġvh

Try it Online!

Works well.

Explained

⁽sġvh
⁽sġ   # Group by sorting each word - groups based on first appearance of each word 
  vh  # Get the first word in each group 

Answer 4

05AB1E, 6 bytes

.¡{}€н

Try it online or verify all test cases.

Or alternatively:

€{DÙkè

Try it online or verify all test cases.

Explanation:

        #  EXAMPLE INPUT: ["cat","tac","dog","god","act"]

.¡ }    # Group the words in the (implicit) input-list by:
  {     #  Sort the characters of the word
        #   STACK: [["cat","tac","act"],["dog","god"]]
    €   # Then map over each group of words:
     н  #  And only leave the first one
        #   STACK: ["cat","dog"]
        # (after which the list of remaining words is output implicitly)

€       # Map over each word of the (implicit) input-list:
 {      #  Sort the characters of the word
        #   STACK: ["act","act","dgo","dgo","act"]
  D     # Duplicate this list of individually sorted words
        #  STACK: ["act","act","dgo","dgo","act"],["act","act","dgo","dgo","act"]
   Ù    # Uniquify the copy list of strings
        #  STACK: ["act","act","dgo","dgo","act"],["act","dgo"]
    k   # Pop both, and get the indices of the remaining strings
        #  STACK: [0,2]
     è  # Use those indices to index into the (implicit) input-list of words
        #  STACK: ["cat","dog"]
        # (after which the list of remaining words is output implicitly)

Answer 5

APL (Dyalog Extended), 7 bytes

Anonymous tacit prefix function.

⊣/∧¨⊢⌸⊢

Try it online!

⊣/ the first elements of

∧¨ the each-sorted

⊢⌸ grouping of

⊢ the argument

Answer 6

Nibbles, 4.5 bytes (9 nibbles)

.=~$~`<$/

.=~$~`<$/
 =~         # group
   $        # the input
    ~       # without sorting the groups
     `<$    # by the results of sorting each element
.           # then map over this list of lists
        /   # folding over each list
            # (implicitly) returning the left-hand argument
            # (so returning the first element of each)

Answer 7

JavaScript (ES6), 43 bytes

a=>a.filter(s=>a[q=[...s].sort()]?0:a[q]=1)

Try it online!

Alternate versions (same size)

a=>a.filter(([...s])=>a[s.sort()]?0:a[s]=1)

Try it online!

a=>a.filter(([...s])=>a[s.sort()]^(a[s]=1))

Try it online!

Commented

a =>          // a[] = input array
a.filter(s => // for each string s in a[]:
  a[          //   test a[q]:
    q =       //     where q[] is the array
      [...s]  //     made of the characters of s
      .sort() //     sorted in lexicographical order
  ] ?         //   if a[q] is already defined:
    0         //     discard this entry
  :           //   else:
    a[q] = 1  //     set a[q] and keep this entry
)             // end of filter()

Answer 8

Perl 5 -nlF, 23 bytes

$k{"@{[sort@F]}"}||=say

Try it online!

Input and output are one word per line.

Answer 9

Pyth, 5 bytes

hM.gS

Try it online!

Explanation

hM.gSkQ    # implicitly add k and Q
           # implicitly assign Q = eval(input())
  .g  Q    # group Q by lambda k
    Sk     #   sort k
hM         # take the first element of each group

Answer 10

Husk, 2 bytes

üO

Try it online!

A not particularly clever solution, but seeing that Husk could solve this with half the bytes of other golfing languages I had to post it.

Explanation

üO
ü     Remove duplicates from the list, keyed on
 O       the sorted strings

Basically ü does exactly what we need for this challenge: for each value in the input list, discard it if it is the same as any previous value when a function is applied to it. The function we use for this comparison is here simply the sorting function.

Answer 11

Scala, 80 bytes

Golfed version. Try it online!

w=>{var s=Set[String]();w.filter(x=>if(s(x.sorted)) 0>1 else {s+=x.sorted;0<1})}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val list = List("cat", "act", "tac", "dog", "god")
    val distinctAnagrams = removeAnagrams(list)
    println(distinctAnagrams)
  }

  def removeAnagrams(words: List[String]): List[String] = {
    var seen = Map[String, Boolean]()
    words.filter { word =>
      val sortedWord = word.sorted
      if (seen.contains(sortedWord)) false
      else {
        seen += (sortedWord -> true)
        true
      }
    }
  }
}

Answer 12

Wolfram Language (Mathematica), 38 33 bytes

#&@@@#~GatherBy~Sort@*Characters&

Thanks to @att!
Try it online!

Answer 13

R, 70 bytes

\(x)x[match(unique(y<-sapply(x,\(s)intToUtf8(sort(utf8ToInt(s))))),y)]

Attempt This Online!

String manipulation isn't something R is good at.

Answer 14

Japt, 9 bytes

Could be 4 if Japt had a built-in for grouping without sorting.

üñ mÎñ@bX

Try it

üñ mÎñ@bX     :Implicit input of array U
ü             :Group & sort by
 ñ            :  Sorting
   m          :Map
    Î         :  First element
     ñ        :Sort by
      @       :Passing each X through the following function
       bX     :  First index of X in U

Answer 15

C# (Visual C# Compiler), 116 bytes

a=>a.Aggregate(new Dictionary<string,string>(),(d,i)=>{d.TryAdd(string.Concat(i.OrderBy(m=>m)),i);return d;}).Values

Try it online!

Answer 16

Python 3, 91 bytes

def h(l):s=set();return[w for w in l if(x:=''.join(sorted(w)))not in s and (s.add(x) or 1)]

Attempt This Online

I wonder whether the filter expression can be shortened further.

Answer 17

Haskell, 64 bytes

import Data.List
s=sort
a=map head.groupBy((.s).(==).s).sortOn s

Try it online!

Answer 18

Julia 1.0, 17 bytes

!x=unique(sort,x)

Try it online!

input and output are a list of lists of characters

28 bytes with a list of strings as input and output: Try it online!

Answer 19

C (gcc), 277 bytes

#define C(A,L)for(int i=A=0;L[i];L[i++]==t&&++A);
i,j,k,x,y,r,t;D(char*a,char*b){for(r=k=0;(t=a[k])||b[k];++k){if(!a[k]||!b[k]){++r;break;}C(x,a)C(y,b)x-y!=0&&++r;}}
main(int c,char**v){for(i=1;i<c;++i){for(j=i-1;j>0;--j){D(v[j],v[i]);if(r==0)goto B;}printf("%s ",v[i]);
B:1;}}

Try it online!

Readable version:

#define C(A,L)for(int i=A=0;L[i];L[i++]==t&&++A);

i,j,k,x,y,r,t;

D(char*a,char*b){
    for(r=k=0;(t=a[k])||b[k];++k){
        if(!a[k]||!b[k]){++r;break;}
        C(x,a)
        C(y,b)
        x-y!=0&&++r;
    }
}

main(int c,char**v) {
    for(i=1;i<c;++i){
        for(j=i-1;j>0;--j){
            D(v[j],v[i]);
            if(r==0)goto B;
        }
        printf("%s ",v[i]);
B:1;
    }
}

Explanation:

Not the most efficient approach but light on code: go through each item in the list (given as arguments), compare to each prior item using a difference function D, and print if none of them matched.

To check matching, the difference function goes through each character in the first string and counts the number of occurrences in either string of that character. If at any point either that number differs or we have finished processing one string while the other is still going, we consider the two non-matching.

To save bytes, I added the counting macro C, which accumulates into variable A the number of occurrences of global character t in list L.

-

C (gcc), 303 bytes (alternate answer)

typedef unsigned long long u;n,i,j,k,z;u t;u y(n){return n==1?1:z*y(n-1)+1;}s(char* v){for(k=t=0;v[k];++k)t+=y(v[k]-96);}main(int c,char *v[]){long f[c];for(i=1;i<c;++i)for(j=0;v[i][j];++j>z&&++z);for(i=1;i<c;++i){s(v[i]);for(j=n,k=0;j>0;--j){f[j-1]==t&&++k;}if(k)continue;printf("%s ",v[i]);f[n++]=t;}}

Try it online!

Readable version:

typedef unsigned long long u;
n,i,j,k,z;u t;
u y(n){return n==1?1:z*y(n-1)+1;}
s(char* v){for(k=t=0;v[k];++k)t+=y(v[k]-96);}
main(int c,char *v[]) {
    long f[c];
    for(i=1;i<c;++i)for(j=0;v[i][j];++j>z&&++z);
    for(i=1;i<c;++i){
        s(v[i]);
        for(j=n,k=0;j>0;--j){f[j-1]==t&&++k;}
        if(k)continue;
        printf("%s ",v[i]);
        f[n++]=t;
    }
}

Explanation:

For sufficiently short strings, this alternate approach will work. We are calculating a signature, which is something like a checksum but reserving non-overlapping number ranges for the potential counts of each letter, for each given list item. We go through the items and then, each time we encounter a novel signature, we print the item and store the signature.

These signatures as currently calculated get really large really fast, so this will only work for short words. Realizing this, I switched to the other approach, but still thought it was interesting enough to include.

I suspect that with a little more work, this could not only work for arbitrarily-long arguments, but also do so with a lighter footprint than the first approach!

Answer 20

Arturo, 32 bytes

$=>[gather&=>sort|map[k,v]->v\0]

Try it!

Collect input strings in a dictionary where the key is the sorted string and the value is a list of strings that sort to that key, then map each dictionary entry to its first value. Input is taken as a list of lists of code points.

Answer 21

Excel, 99 bytes

=LET(r,ROW(A:A),b,BYROW(A:A,LAMBDA(s,CONCAT(SORT(MID(s,r,1))))),FILTER(A:A,(b<>"")*MATCH(b,b,0)=r))

Note: This takes quite a long time to run on my weak machine and sometimes just locked Excel. For the sake of the screenshots below, I changed the range references from A:A to just A1:A10. The logic is all the same, though.

Input is one string per cell in column A.

• LET(r,ROW(A:A) creates an array of values 1 to 1,048,576 and assigns it to the variable r.
• b,BYROW(A:A,LAMBDA(s,CONCAT(SORT(MID(s,r,1))))) takes each string, splits it into pieces, sorts those pieces, and then combines them back into a string. The array of all these new, sorted strings is assigned to the variable b.
• FILTER(A:A,(b<>"")*MATCH(b,b,0)=r) filters out the values where that result array b is blank and then only returns the strings from the input array where their index in the input matches the first instance of their sorted string in the sorted string array b.

There are probably shorter ways to do this and I welcome someone pointing them out.

Answer 22

PowerShell Core, 53 bytes

$args|?{($k="$($_|% t*y|sort)")-notin$s-and($s+=,$k)}

Try it online!

Takes the words arguments using splatting, returns a list or words.

It works by building a list of keys for each word by sorting its letters alphabetically:
e.g. cat has the key a c t
Then for each word $_, if the word's key $k is not in the list $s, add $k to $s and return $_

Answer 23

Factor + sets.extras, 22 bytes

[ [ sort ] unique-by ]

Factor has the perfect combinator for this, unique-by, which returns a list of the first unique values in a list after a function has been applied to each element. Requires Factor build ~2207+ for sort, hence this won't work on TIO or ATO.

Answer 24

Thunno 2, 4 bytes

ñṠ€h

Attempt This Online!

Explanation

ñṠ€h  # Implicit input
ñṠ    # Group by sorting
  €h  # First item of each
      # Implicit output

Answer 25

simply, 105 100 bytes

Yes, it's very long, but makes use of the built-in &marsagain.
(It's an anagram for &is_anagram, that happens to be 1 byte shorter.)

fn($x){$A=[]each$X in$x{$L=0each$a in$A if!$L$L=&marsagain($X$a)if!$L$A=&array_concat($A$X)}send$A;}

Defines an anonymous function that takes an array of strings and returns an array of strings.

---

---

Ungolfed

This is the same code, but ungolfed.

Code-like

anonymous function($words) {
    $anagrams = [];
    each $word in $words {
        $in_the_list = false;
        each $anagram in $anagrams {
            unless $in_the_list then {
                $in_the_list = &is_anagram($word, $anagram);
            }
        }
        
        unless $in_the_list then {
            $anagrams = &array_concat($anagrams, $word);
        }
    }
    
    return $anagrams;
};

English-like

Set the variable $fn to an anonymous function with arguments($words)
Begin.
    Set the variable $anagrams = [].
    Foreach $word in $words
    Begin.
        Set the variable $in_the_list to false.
        
        Foreach $anagram in $anagrams
        Begin.
            Unless $in_the_list then
            Begin.
                Set the variable $in_the_list to the result of calling the function &is_anagram with the arguments ($word, $anagram).
            End.
        End.
        
        Unless $in_the_list then
        Begin.
            Set the variable $anagrams to the result of calling the function &array_concat with the arguments ($anagrams, $word).
        End.
    End.
    
    Return the value of $anagrams.
End.

Both variants do the same.

---

---

Testing it

To test it, you have to assign it to a variable, E.g.:

$fn = fn($x){$A=[$x->0]each$X in$x{$L=0each$a in$A if!$L$L=&marsagain($X$a)if!$L$A=&array_concat($A$X)}send$A;};

// Copy-paste from the tests
$result = call $fn(["cat", "dog", "tac", "god", "act"]);

// Should output ["cat","dog"]
echo &json_encode($result);

Answer 26

Charcoal, 20 bytes

ＷＳＦ⬤υ⊙⁺ικ⁻№ιμ№κμ⊞υιυ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

ＷＳ

Repeat for each input string.

Ｆ⬤υ⊙⁺ικ⁻№ιμ№κμ

If none of the unique anagrams so far are anagrams of this string, then...

⊞υι

... add this string to the list of unique anagrams so far.

υ

Output the final list of unique anagrams.

Answer 27

Uiua ^SBCS, 9 bytes

▽◰⍚(⊏⍏.).

Try it!

▽◰⍚(⊏⍏.).
        .  # duplicate
  ⍚(⊏⍏.)   # sort each string
 ◰         # mark firsts
▽          # keep