28
\$\begingroup\$

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
\$\endgroup\$

29 Answers 29

20
\$\begingroup\$

Python 3, 64 bytes

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

Try it online!

\$\endgroup\$
9
  • 4
    \$\begingroup\$ But is itertools ever the answer? \$\endgroup\$ Nov 14, 2017 at 6:44
  • \$\begingroup\$ @MistahFiggins Nominated \$\endgroup\$
    – Mr. Xcoder
    Nov 14, 2017 at 9:46
  • \$\begingroup\$ @Mr.Xcoder before 22 July 2015 \$\endgroup\$
    – Stan Strum
    Nov 14, 2017 at 15:24
  • \$\begingroup\$ @StanStrum I just mentioned it, I am aware of that restriction. As Stewie said... \$\endgroup\$
    – Mr. Xcoder
    Nov 14, 2017 at 15:25
  • 1
    \$\begingroup\$ @jpmc26 Yes, this way you can put f=\ in the Try it Online header and leave the function anonymous, while not affecting the automatic TiO byte counter \$\endgroup\$
    – Mr. Xcoder
    Nov 14, 2017 at 21:27
9
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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").

\$\endgroup\$
4
\$\begingroup\$

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)')
\$\endgroup\$
6
  • \$\begingroup\$ FYI arrow functions are allowed (for example a=>b instead of function(a){return b}). It saves a lot of bytes. \$\endgroup\$
    – user72349
    Nov 14, 2017 at 15:24
  • \$\begingroup\$ Wow... that'll save quite a few bytes. \$\endgroup\$
    – Imme
    Nov 14, 2017 at 15:49
  • \$\begingroup\$ s.split("") can be [...s]. Also join("") can be `join``` \$\endgroup\$ Nov 14, 2017 at 16:05
  • \$\begingroup\$ @ThePirateBay i was afraid that would be the case, but why is that? (im aware that sort is not fully random,but all sequences SHOULD be possible) \$\endgroup\$
    – Imme
    Nov 14, 2017 at 16:12
  • \$\begingroup\$ @Imme. Here is 87 bytes working version. Notice that your sort function never returns 0 (or at least extremely rare), that's why it didn't work. \$\endgroup\$
    – user72349
    Nov 14, 2017 at 16:18
4
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can save a byte with notElem. i would be surprised if someone finds a permutation function which beats the import, my shortest approach is 60 bytes vs. the 29 bytes of the import. \$\endgroup\$
    – Laikoni
    Nov 14, 2017 at 12:54
  • 1
    \$\begingroup\$ Here is a 43 bytes permutation function, but only for duplicate free lists. \$\endgroup\$
    – Laikoni
    Nov 14, 2017 at 12:57
  • 1
    \$\begingroup\$ Also your solution is currently not working because $ is missing before l!!0. \$\endgroup\$
    – Laikoni
    Nov 14, 2017 at 12:59
3
\$\begingroup\$

Ruby, 46 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 57 bytes

non-deterministic

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

Try it online!

Mathematica, 56 bytes

deterministic

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Nuts, you beat me to it. You could take input as individual strings and save a byte with á kN ö. \$\endgroup\$
    – Shaggy
    Nov 14, 2017 at 14:50
  • \$\begingroup\$ @Shaggy That's a great way to get the first input item, I'll have to remember that. Thanks! \$\endgroup\$ Nov 14, 2017 at 18:43
2
\$\begingroup\$

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'}.

\$\endgroup\$
0
2
\$\begingroup\$

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

\$\endgroup\$
7
  • \$\begingroup\$ if x not in a is if~-(x in a) for 178 \$\endgroup\$
    – Mr. Xcoder
    Nov 14, 2017 at 5:14
  • \$\begingroup\$ @Mr.Xcoder. You mean 78, right? \$\endgroup\$
    – user72349
    Nov 14, 2017 at 5:22
  • \$\begingroup\$ @ThePirateBay Yes, I do... Whoops! \$\endgroup\$
    – Mr. Xcoder
    Nov 14, 2017 at 5:22
  • 1
    \$\begingroup\$ How about 66 bytes? \$\endgroup\$
    – Maya
    Nov 14, 2017 at 12:58
  • 1
    \$\begingroup\$ @NieDzejkob That's impressively shorter. You should post your own if you want \$\endgroup\$
    – hyper-neutrino
    Nov 14, 2017 at 12:59
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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")))
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
1
\$\begingroup\$

Husk, 6 bytes

←-⁰P←⁰

Try it online!

\$\endgroup\$
2
1
\$\begingroup\$

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;
\$\endgroup\$
1
  • \$\begingroup\$ Save two bytes with do{...}while($j); instead of $j=1;while($j){...}. Use in-place definition for $g to get rid of the braces (and save four bytes). \$\endgroup\$
    – Titus
    Oct 27, 2018 at 18:01
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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]}

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Taking input as a table, for 21 bytes: {.@(-.~i.@!@#@{.A.{.). Try it online! \$\endgroup\$
    – Jonah
    Nov 15, 2017 at 2:30
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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"
\$\endgroup\$
1
  • \$\begingroup\$ I think there might be a typo in your explanation - The answer that your code gives is different from what your explanation says \$\endgroup\$ Nov 15, 2017 at 19:08
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.