Anagramm ausgeben! Nein, nicht das!

28

Ausgehend von einer Liste eindeutiger Zeichenfolgen, die Anagramme voneinander sind, geben Sie ein Anagramm der Wörter aus, die sich von den einzelnen Wörtern in der Liste unterscheiden.

Die Zeichenfolgen sind alphanumerisch und es wird garantiert ein gültiges Anagramm angezeigt.

Das Programm oder die Funktion kann, muss aber nicht nicht deterministisch sein, dh bei gleicher Eingabe kann die Mehrfachausführung eines Codes zu unterschiedlichen Ausgaben führen, sofern jede mögliche Ausgabe eine gültige ist.

Testfälle

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

Antworten:

20

Python 3 , 64 Bytes

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

Probieren Sie es online!

Mr. Xcoder
quelle
4
Aber ist itertoolsjemals die Antwort?
MildlyMilquetoast
@ MistahFiggins Nominiert
Mr. Xcoder
@ Mr.Xcoder vor dem 22. Juli 2015
Stan Strum
@StanStrum Ich habe es gerade erwähnt, mir ist diese Einschränkung bekannt. Wie Stewie sagte ...
Mr. Xcoder
1
@ jpmc26 Ja, auf diese Weise können Sie f=\den Try it Online-Header einfügen und die Funktion anonym lassen, ohne den automatischen TiO-Byte-Zähler zu beeinflussen
Mr. Xcoder
9

05AB1E , 5 Bytes

нœ¹мà

Probieren Sie es online!

Erläuterung

нœ¹мà

н     // 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)

quelle
7

Pyth , 5 Bytes

h-.ph

Probieren Sie es online!

Erläuterung

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

Gelee , 6 Bytes

XŒ!ḟµḢ

Probieren Sie es online!

1 Byte mehr als die 05AB1E- und die Pyth-Antwort.

Erläuterung:

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.

Ich habe gewählt, Xweil es der kürzeste Weg ist, ein Element aus der Liste auszuwählen, ohne die Liste zu ändern ( und funktioniert nicht, ḷ/undṛ/ ist länger), und es verursacht Zufälligkeiten.

Das µhier ist ziemlich redundant, aber ohne das würde das mit dem gepaart werden , und es wird als "Kopf der Eingabe herausfiltern" interpretiert, was ich hier nicht brauche (was ich brauche, ist "die Eingabe herausfiltern, und nimm den Kopf ").

user202729
quelle
4

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}

verwendet einen fehlerhaften Zufallsgenerator, um jede "zufällige" Permutation zu durchlaufen.

Wahrscheinlich falsch, aber der schlechte Zufallsgenerator bedeutet nur, dass wir keine echte Zufälligkeit erhalten, aber trotzdem jede Permutation erhalten.

Scheint auf allen Fällen in Chrome für mich zu funktionieren, aber anscheinend aufgrund undefinierten Verhaltens bei dieser Art Missbrauch, kann es in einigen Browsern nicht funktionieren.

(Wahrscheinlich sehr ungolfed fühlen Sie sich frei, es in Ihren eigenen Lösungen zu verbessern)

80 Bytes

Dank PirateBays Kommentar - viele Bytes

-4 Bytes dank Rick

f=a=>eval('s=[...a[0]].sort(()=>.5-Math.random()).join``;a.indexOf(s)<0?s:f(a)')
Ich bin ich
quelle
Zu Ihrer Information: Pfeilfunktionen sind zulässig (z. B. a=>banstelle von function(a){return b}). Das spart eine Menge Bytes.
Wow ... das spart ein paar Bytes.
Imme
s.split("")kann sein [...s]. Auch join("")kann `join``` sein
Rick Hitchcock
@ThePirateBay Ich hatte Angst, dass dies der Fall sein würde, aber warum ist das so? (Ich bin mir bewusst, dass die Sortierung nicht völlig zufällig ist, aber alle Sequenzen sollten möglich sein)
Imme
@Ich bin ich. Hier ist 87 Bytes Arbeitsversion. Beachten Sie, dass Ihre sortFunktion niemals zurückkehrt 0(oder zumindest extrem selten). Deshalb hat sie nicht funktioniert.
4

Haskell , 58 Bytes

-1 Byte und ein Update dank Laikoni.

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

Probieren Sie es online!

Es lohnt sich wahrscheinlich nicht Data.Listfür Permutationen zu importieren, aber eh.

total menschlich
quelle
1
Mit können Sie ein Byte speichern notElem. Ich wäre überrascht, wenn jemand eine Permutationsfunktion findet, die den Import schlägt. Mein kürzester Ansatz ist 60 Bytes im Vergleich zu den 29 Bytes des Imports.
Laikoni
1
Hier ist eine 43-Byte-Permutationsfunktion, jedoch nur für doppelte freie Listen.
Laikoni
1
Auch Ihre Lösung funktioniert derzeit nicht, weil $es vorher fehlt l!!0.
Laikoni
3

Brachylog , 7 Bytes

hp.¬∈?∧

Probieren Sie es online!

Erläuterung

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)
Tödlich
quelle
3

Japt , 7 6 Bytes

-1 Byte dank @Shaggy

á kN ö

Probieren Sie es online!

Nimmt Eingabezeichenfolgen als mehrere Eingaben statt als Array. Gibt eine zufällige Permutation aus. Wechseln Sie özu g, um stattdessen die erste zu erhalten.

Erläuterung

á 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
Justin Mariner
quelle
Nuts, du hast mich geschlagen. Sie können Eingaben als einzelne Zeichenfolgen nehmen und ein Byte mit speichern á kN ö.
Shaggy
@ Shaggy Das ist eine großartige Möglichkeit, das erste Eingabeelement zu erhalten, das muss ich mir merken. Vielen Dank!
Justin Mariner
2

MATL , 15 , 13 , 12 Bytes

1X)Y@Z{GX-1)

Probieren Sie es online!

2 Bytes dank Sanchises gespart. setdiff(...,'rows')ist kürzer als das Negieren ismember(...,'rows')und vermeidet eine Duplizierung. Dank Luis Mendo konnte ein weiteres Byte eingespart werden, indem auf Zellen anstatt auf Arrays gewechselt wurde.

Erläuterung:

Die MATLAB / Octave-Entsprechungen sind ebenfalls enthalten.

                 % 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

Die Eingabe muss im Format erfolgen {'abc', 'acb'}.

Stewie Griffin
quelle
2

Python 3 , 78 Bytes

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

Probieren Sie es online!

-1 Byte danke an Herrn Xcoder

HyperNeutrino
quelle
if x not in aist if~-(x in a)für 178
Mr. Xcoder
@ Mr.Xcoder. Du meinst 78, richtig?
@ThePirateBay Ja, das tue ich ... Whoops!
Mr. Xcoder
1
Wie wäre es mit 66 Bytes ?
NieDzejkob
1
@NieDzejkob Das ist beeindruckend kürzer. Sie sollten Ihre eigenen veröffentlichen, wenn Sie wollen
HyperNeutrino
2

Pip , 11 Bytes

@:_NIgFIPMa

Übernimmt die Eingaben als Befehlszeilenargumente. Probieren Sie es online!

Erläuterung

          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
DLosc
quelle
2

Python 3 , 87 Bytes

Ich glaube, dies ist die einzige Einreichung, die bisher weder eine eingebaute Permutation noch zufälliges Mischen / Sortieren verwendet. Obwohl es länger ist, finde ich den Algorithmus ziemlich ordentlich.

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]

Probieren Sie es online!

Erläuterung

Was wir tun, ist im Grunde Folgendes:

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

Hier ist ein Beweis, dass es funktioniert:

SDefinieren Sie für eine Zeichenfolge die Zeichenfolge , die Sie front(S)erhalten, indem Sie ein Zeichen aus auswählen Sund es nach vorne verschieben S. Zum Beispiel front(ABCDE)ist {ABCDE, BACDE, CABDE, DABCE, EABCD}.

Betrachten Sie nun eine Liste von Anagrammen L, Ldie nicht jedes mögliche Anagramm enthält (gemäß der Problembeschreibung). Wir wollen zeigen , dass es eine Zeichenfolge besteht Sin Lsolchen , die front(S)mindestens ein Anagramm enthält , S'die nicht in ist L.

Nehmen wir im Widerspruch an, dass für jede Saite Sin Lauch jede Saite in front(S)ist L. Beachten Sie, dass wir durch eine Reihe von "Fronting" -Zügen eine beliebige Permutation für eine beliebige Zeichenfolge erzeugen können. Zum Beispiel zu bekommen

ABCDE -> BAEDC

wir können tun

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

Wir haben angenommen, dass für jedes SIn Ljedes S'In front(S)auch In ist L. Dies bedeutet auch, dass jedes In S''in front(S')ist Lund so weiter. Wenn Salso in ist L, Sist auch jede Permutation von in L. Dann Lmuss ein kompletter Satz von Anagrammen ein Widerspruch sein.

Also, da wir garantiert werden , dass es zumindest eine Permutation nicht in L, muss es einen String existiert Sin , Lfür die einige S'in front(S)ist nicht in L. QED.

Der Code iteriert front(S)für jeden Sin Lund wählt eine S'der nicht in L. Aufgrund des obigen Ergebnisses wird es mindestens eines geben S', das sich qualifiziert.

DLosc
quelle
1

JavaScript (ES7), 172 Byte

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

Suchen Sie die erste lexikografische Permutation des ersten Elements des Arrays, das nicht im Array enthalten ist.

Neil
quelle
1

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}

Verschönert

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

Prüfung

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")))
}
jrtapsell
quelle
1

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

Probieren Sie es online!

Steadybox
quelle
1

Scala, 50 Bytes

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

Probieren Sie es online!

Erläuterung

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
Karl Bielefeldt
quelle
1

R 89 Bytes

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

Probieren Sie die Buchstaben aus dem ersten Eintrag wiederholt aus (da sie Anagramme voneinander sein sollten) und hören Sie auf, wenn eines dieser Beispiele nicht in der ursprünglichen Liste enthalten ist.

Andrew Haynes
quelle
82 Bytes
Giuseppe
1

PHP , 70 Bytes

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

Laufen Sie auf einem Webserver und geben Sie 0 indizierte Get-Werte ein oder versuchen Sie es 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;
SmartCoder
quelle
Speichern Sie zwei Bytes mit do{...}while($j);anstelle von $j=1;while($j){...}. Verwenden Sie die In-Place-Definition $g, um die geschweiften Klammern zu entfernen (und vier Bytes zu sparen).
Titus
1

PHP, 58-55 Bytes

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

nicht deterministisch; Nimmt Eingaben von Befehlszeilenargumenten entgegen

Laufen Sie mit php -r <code>durch Leerzeichen getrennten Wörtern oder probieren Sie es online aus .

Titus
quelle
1

Attache , 16 Bytes

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

Probieren Sie es online!

Erläuterung

&\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

Alternativen

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

Conor O'Brien
quelle
0

J , 25 Bytes

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

Die Eingabe ist eine Liste von Boxed-Strings. Ich fand es fair, diese Listen nicht explizit als 4 8 $ 'abcde123', 'ab3e1cd2', '321edbac', 'bcda1e23' zu deklarieren.

Ich mag das @ mess in meinem Code nicht, aber dieses Mal gibt es viele serialisierte Verben.

Wie es funktioniert:

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

Probieren Sie es online!

Galen Ivanov
quelle
1
Unter Eingabe als eine Tabelle, für 21 Bytes {.@(-.~i.@!@#@{.A.{.). Probieren Sie es online!
Jona,
0

05AB1E , 5 Bytes

нœIмà

Probieren Sie es online!

Erläuterung

нœ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

Ziemlich genau die gleiche Antwort, die @ThePirateBay gefunden hat.

Cinari
quelle
0

JavaScript, 87 Bytes

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

Probieren Sie es online!

Diese Antwort basiert (obwohl stark modifiziert) auf Immes Antwort . Schlug er in einem Kommentar vor dass dies eine andere Antwort sein sollte.

Das Problem mit dem alten Ansatz ist, weil sort vollständig von der Implementierung abhängt. Der Standard garantiert nicht die Reihenfolge des Aufrufs der Sortierfunktion, weshalb er theoretisch niemals für den ersten oder den zweiten Testfall enden kann.

Dieser Ansatz ist einige Bytes länger, aber er garantiert, dass er in begrenzter Zeit beendet wird, auch wenn er Math.randomniemals zurückkehrt .5.


quelle
0

CJam , 11 Bytes

q~_0=m!\m0=

Probieren Sie es online!

Erläuterung

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"
Esolanging Fruit
quelle
Ich denke , es könnte ein Tippfehler in Ihrer Erklärung sein - Die Antwort , dass Ihr Code gibt unterscheidet sich von dem, was Ihre Erklärung sagt
MildlyMilquetoast
0

Perl 6 , 42 Bytes

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

Probieren Sie es online!

Mischt die erste Zeichenfolge der Eingabe nach dem Zufallsprinzip, bis sie kein Element der Eingabe mehr ist.

Erläuterung:

{(.[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
Scherzen
quelle