Output an Anagram! No Not That One!

Question

Given a list of unique strings that are anagrams of each other, output an anagram of those words that is different from each word in the list.

The strings will be alphanumeric, and there is guaranteed to be a valid anagram.

The program or function can, but doesn't have to be non-deterministic, meaning given the same input, multiple running a of the code can yield different outputs, as long as every possible output is a valid one.

Test Cases

[Input] -> Possible output
-----------------
[ab] -> ba
[aba, aab] -> baa
[123, 132, 231, 312, 321] -> 213
[hq999, 9h9q9, 9qh99] -> 999hq
[abcde123, ab3e1cd2, 321edbac, bcda1e23] -> ba213ecd

Answer 1

Python 3, 64 bytes

lambda a:[*{*permutations(a[0])}-{*a}][0]
from itertools import*

Try it online!

Answer 2

05AB1E, 5 bytes

нœ¹мà

Try it online!

Explanation

нœ¹мà

н     // Get the first element of the input list
 œ    // Generate all permutations
  ¹   // Push the input again
   м  // In the permutations list, replace all strings that
      //   are in the input list with empty strings
    à // Pick the string with the greatest lexicographic
      //   index (in this case a non-empty string)

Answer 3

Pyth, 5 bytes

h-.ph

Try it online!

Explanation

h-.ph
    h    First string in [the input]
  .p     All permutations
 -       Remove those in [the input]
h        First element.

Answer 4

Jelly, 6 bytes

XŒ!ḟµḢ

Try it online!

1 byte more than the 05AB1E and the Pyth answer.

Explanation:

XŒ!ḟµḢ   Main program.
 Œ!      All permutation of...
X        any element from the word list.
   ḟ     Filter out (remove) all the elements in the original word list.
    µ    With the filtered-out list,
     Ḣ   pick the first element.

I chosen X because it is the shortest way I know to pick any element from the list without altering the list (Ḣ and Ṫ doesn't work, ḷ/ and ṛ/ is longer), and it happens to cause some randomness.

The µ here is pretty redundant, but without it, the Ḣ would be paired with the ḟ, and it is interpreted as "filter out the head of the input", which is not what I need here (what I need is "filter out the input, and get the head").

Answer 5

Haskell, 58 bytes

-1 byte and a fix thanks to Laikoni.

import Data.List
f l=[i|i<-permutations$l!!0,all(/=i)l]!!0

Try it online!

It's probably not worth importing Data.List for permutations but eh.

Answer 6

Javascript, 118 Bytes

function f(a){s=a[0];while(a.indexOf(s)!=-1)s=s.split("").sort(function(){return .5-Math.random()).join("")};return s}

uses a bad randomizer to iterate over each "random" permutation.

Probably provably wrong but afaik the bad randomizer just means we wont get true randomness, but will still get every permutation.

Seems to work on all cases in chrome for me but apparently due to undefined behaviour in this sort abuse, it can not work in some browsers.

(Probably very ungolfed feel free to improve it in your own solutions)

80 bytes

Thanks to pirateBay's comment -a lot of bytes

-4 bytes thanks to Rick

f=a=>eval('s=[...a[0]].sort(()=>.5-Math.random()).join``;a.indexOf(s)<0?s:f(a)')

Answer 7

Ruby, 46 bytes

->l{(l[0].chars.permutation.map(&:join)-l)[0]}

Try it online!

Answer 8

Brachylog, 7 bytes

hp.¬∈?∧

Try it online!

Explanation

hp.        The Output is a permutation of the first element of the Input
  .¬∈?     The Output is not a member of the Input
      ∧    (Disable implicit Input = Output)

Answer 9

Japt, 7 6 bytes

-1 byte thanks to @Shaggy

á kN ö

Try it online!

Takes input strings as several inputs instead of as an array. Outputs a random permutation; switch ö to g to get the first one instead.

Explanation

á kN ö  Implicit input: N = array of input strings
á       Get all permutations of the first input string
  kN    Remove all input strings from those
     ö  Get a random element from the array. Implicit output

Answer 10

Mathematica, 57 bytes

non-deterministic

(While[!FreeQ[#,s=""<>RandomSample@Characters@#&@@#]];s)&

Try it online!

Mathematica, 56 bytes

deterministic

#&@@Complement[""<>#&/@Permutations@Characters@#&@@#,#]&

Try it online!

Answer 11

Python 3, 78 bytes

lambda a:[x for x in permutations(a[0])if~-(x in a)][0]
from itertools import*

Try it online!

-1 byte thanks to Mr. Xcoder

Answer 12

MATL, 15, 13, 12 bytes

1X)Y@Z{GX-1)

Try it online!

Saved 2 bytes thanks to Sanchises. setdiff(...,'rows') is shorter than negating ismember(...,'rows') and it avoids one duplication. Saved another byte thanks to Luis Mendo, by switching to cells instead of arrays.

Explanation:

The MATLAB / Octave equivalents are also included.

                 % Implicitly grab input x containing cells of strings
1X)              % Get first cell. Equivalent to x{1}
   Y@            % All permutations of first row input. Equivalent to p=perms(y)
      Z{         % Convert the list of permutations to a cell array
        G        % Grab input again      
         X-      % setdiff, comparing the input cells with the permutations
           1)    % The first of the results

Input must be one the format {'abc', 'acb'}.

Answer 13

Pip, 11 bytes

@:_NIgFIPMa

Takes the inputs as command-line arguments. Try it online!

Explanation

          a  1st cmdline arg
        PM   List of all permutations
      FI     Filter on this function:
  _NIg         Permutation not in cmdline args
@:           First element of resulting list (with : meta-operator to lower precedence)
             Autoprint

Answer 14

Python 3, 87 bytes

I believe this is the only submission so far that uses neither a permutation builtin nor random shuffle/sort. Even though it's longer, I think the algorithm is pretty neat.

lambda L:[p for s in L for i,c in enumerate(s)for p in[c+s[:i]+s[i+1:]]if~-(p in L)][0]

Try it online!

Explanation

What we're doing is basically this:

def unique_anagram(string_list):
    for string in string_list:
        for i, char in enumerate(string):
            # Move the character to the beginning of the string
            permutation = char + string[:i] + string[i+1:]
            if permutation not in string_list:
                return permutation

Here's a proof that it works:

For a string S, define front(S) as the set of strings obtained by choosing one character from S and moving it to the front of S. For example, front(ABCDE) is {ABCDE, BACDE, CABDE, DABCE, EABCD}.

Now consider a list of anagrams L, such that L does not contain every possible anagram (as per the problem description). We wish to show that there exists a string S in L such that front(S) contains at least one anagram S' that is not in L.

Suppose, by way of contradiction, that for every string S in L, every string in front(S) is also in L. Observe that we can generate an arbitrary permutation of any string via a series of "fronting" moves. For example, to get

ABCDE -> BAEDC

we can do

ABCDE -> CABDE -> DCABE -> EDCAB -> AEDCB -> BAEDC

We have assumed that for each S in L, every S' in front(S) is also in L. This also means that every S'' in front(S') is in L, and so forth. Therefore, if S is in L, every permutation of S is also in L. Then L must be a complete set of anagrams, a contradiction.

So, since we are guaranteed that there is at least one permutation not in L, there must exist a string S in L for which some S' in front(S) is not in L. QED.

The code iterates over front(S) for each S in L and selects an S' which is not in L. By the above result, there will be at least one S' that qualifies.

Answer 15

C# (Visual C# Interactive Compiler), 116 96 bytes

s=>{for(var g="";;)if(s.All(z=>z!=(g=string.Concat(s[0].OrderBy(t=>Guid.NewGuid())))))return g;}

My golfing skills have certainly gotten better since when I first posted this!

Try it online!

Answer 16

Husk, 6 bytes

←-⁰P←⁰

Try it online!

Answer 17

JavaScript (ES7), 172 bytes

f=(a,s=a[0],b=[...s],k=b.findIndex((e,i)=>s[i-1]>e))=>a.includes(s)?f(a,(~k?(t=b[k],b[k]=b[l=a.findIndex(e=>e>t)],b[l]=t,b.map((e,i)=>i<k?b[k+~i]:e)):b.reverse()).join``):s

Find the first lexicographic permutation of the first element of the array that's not contained in the array.

Answer 18

Kotlin, 104 bytes

{var r=""
do{r=it[0].map{it to Math.random()}.sortedBy{(_,b)->b}.fold("",{a,(f)->a+f})}while(r in it)
r}

Beautified

{
    var r = ""
    do {
        r = it[0].map { it to Math.random() }
            .sortedBy { (_, b) -> b }
            .fold("", { a, (f) -> a + f })
    } while (r in it)
    r
}

Test

var ana: (List<String>) -> String =
{var r=""
do{r=it[0].map{it to Math.random()}.sortedBy{(_,b)->b}.fold("",{a,(f)->a+f})}while(r in it)
r}

fun main(args: Array<String>) {
    println(ana(listOf("ab")))
}

Answer 19

C++, 169 bytes

#import<set>
#import<string>
#import<algorithm>
using S=std::string;S f(std::set<S>l){S s=*l.begin();for(;l.count(s);)std::next_permutation(s.begin(),s.end());return s;}

Try it online!

Answer 20

Scala, 50 bytes

(l:Seq[String])=>(l(0).permutations.toSet--l).head

Try it online!

Explanation

l(0)         // Take the first anagram
permutations // Built-in to get all permutations
toSet        // Convert to set, required for -- function
-- l         // Remove the original anagrams
head         // Take a random element from the set

Answer 21

R, 89 bytes

x=scan(,'');repeat{a=paste(sample(el(strsplit(x[1],''))),collapse='');if(!a%in%x)break};a

Repeatedly sample the letters from the first entry (as they should be anagrams of each other) and stop when one of those samples is not in the original list.

Answer 22

PHP, 70 bytes

$j=1;while($j){$g=str_shuffle($_GET[0]);$j=in_array($g,$_GET);}echo$g;

Run on a webserver, inputting 0 indexed get values or Try it online!

Ungolfed

$j=1; //set truty value
while($j){ 
    $g=str_shuffle($_GET[0]); //shuffle the first anagram of the set
    $j=in_array($g,$_GET); //see if in the set, if false, the loop ends
}
echo $g;

Answer 23

PHP, 58 55 bytes

while(in_array($s=str_shuffle($argv[1]),$argv));echo$s;

non-deterministic; takes input from command line arguments

Run with php -r <code> follwed by space separated words or try it online.

Answer 24

Attache, 16 bytes

&\S@{!S@_[0]Ø_}

Try it online!

Explanation

&\S@{!S@_[0]Ø_}
    {         }    lambda (input: `_`)
        _[0]       first element of the given array
       @           pass to:
     !                 on each permutation:
      S                cast to string
            Ø      without any member of
             _     the input
                   this gives all anagrams not in the input
   @               then
&\S                "first string element"
&                  spread input array over each individual arguments
 \                 tale first argument
  S                as a string

Alternatives

17 bytes: {&\S! !S@_[0]Ø_}

18 bytes: {&\S! !Id@_[0]Ø_}

19 bytes: {&\S!(!Id)@_[0]Ø_}

26 bytes: {&\S!Permutations@_[0]Ø_}

26 bytes: {&\S!Permutations[_@0]Ø_}

26 bytes: {(Permutations[_@0]Ø_)@0}

26 bytes: &\S##~`Ø#Permutations@&\S

27 bytes: Last@{Permutations[_@0]Ø_}

27 bytes: `@&0@{Permutations[_@0]Ø_}

28 bytes: Last##~`Ø#Permutations@&{_}

28 bytes: Last##~`Ø#Permutations@Last

28 bytes: First@{Permutations[_@0]Ø_}

30 bytes: {NestWhile[Shuffle,`in&_,_@0]}

33 bytes: {If[(q.=Shuffle[_@0])in _,$@_,q]}

33 bytes: {q.=Shuffle[_@0]If[q in _,$@_,q]}

34 bytes: {If[Has[_,q.=Shuffle[_@0]],$@_,q]}

Answer 25

J, 25 bytes

((A.~i.@!@#)@{.@:>){.@-.>

The input is a list of boxed strings - I felt it was fair like this and not to declare the lists of strings explicitly as 4 8$'abcde123', 'ab3e1cd2', '321edbac', 'bcda1e23'.

I don't like the @ mess in my code, but there are a lot of serialized verbs this time.

How it works:

                         >  - unboxes the strings
 (                 )        - left verb of the fork as follows:
             @{.@:>         - unbox and take the first string
  (         )               - finds all permutations of the first string
      i.@!@#                - a list 0 .. the factorial of the length of the 1st string
   A.~                      - anagram index, all permutations
                    {.@-.   - remove the inital strings and take the first of the remaining

Try it online!

Answer 26

05AB1E, 5 bytes

нœIмà

Try it online!

Explanation

нœIмà full program with implicit input i
н     push first element of i
 œ    push all permutations
  I   push input i
   м  remove all elements of i from the permutations
    à extract greatest element and print implicitly

Pretty much the same answer that @ThePirateBay found.

Answer 27

JavaScript, 87 bytes

a=>eval('for(s=[...a[0]];(a+[]).includes(k=s.sort(a=>~-(Math.random``*3)).join``););k')

Try it online!

This answer is based (although heavily modified) on Imme's answer. He suggested in a comment that this should be a different answer.

The problem with the old approach is because sort is completely implementation-dependent. The standard doesn't guarantee the order of calling the sort function, therefore theoretically it may never end for the first or the second test case.

This approach is few bytes longer, but it guarantee that it will finish in constrained time, even if Math.random never returns .5.

Answer 28

CJam, 11 bytes

q~_0=m!\m0=

Try it online!

Explanation

q~  e# Read input and evaluate: ["123" "132" "231" "312" "321"]
_   e# Duplicate:               ["123" "132" "231" "312" "321"] ["123" "132" "231" "312" "321"]
0=  e# First:                   ["123" "132" "231" "312" "321"] "123"
m!  e# Permutations:            ["123" "132" "231" "312" "321"] ["123" "132" "213" "231" "312" "321"]
\   e# Swap:                    ["123" "132" "213" "231" "312" "321"] ["123" "132" "231" "312" "321"]
m0  e# Subtract, push 0:        ["213"] 0
    e# (m is used instead of - when in front of a digit)
=   e# Get item:                "213"

Answer 29

Perl 6, 42 bytes

{(.[0],*.comb.pick(*).join...*∉$_)[*-1]}

Try it online!

Randomly shuffles the first string of the input until it is not an element of the input.

Explanation:

{(.[0],*.comb.pick(*).join...*∉$_)[*-1]}
{                                      }   # Anonymous code block
 (                        ...    )   # Create a sequence
  .[0],   # The first element is the first element of the input
       *.comb.pick(*).join   # Each element is the previous one shuffled
                             *∉$_   # Until it is not in the input
                                  [*-1]   # Return the last element