Keluarkan Anagram! Tidak Bukan Itu!

28

Diberikan daftar string unik yang merupakan anagram satu sama lain, menghasilkan anagram kata-kata yang berbeda dari setiap kata dalam daftar.

String akan berupa alfanumerik, dan dijamin ada anagram yang valid.

Program atau fungsi dapat, tetapi tidak harus non-deterministik, artinya diberi input yang sama, beberapa menjalankan kode dapat menghasilkan output yang berbeda, selama setiap kemungkinan output adalah yang valid.

Uji Kasus

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

Jawaban:

20

Python 3 , 64 byte

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

Cobalah online!

Tuan Xcoder
sumber
4
Tetapi apakah itertoolspernah jawabannya?
MildlyMilquetoast
@MistahFiggins Dinominasikan
Tn. Xcoder
@ Mr.Xcoder sebelum 22 Juli 2015
Stan Strum
@StanStrum Saya baru saja menyebutkannya, saya menyadari pembatasan itu. Seperti yang dikatakan Stewie ...
Tn. Xcoder
1
@ jpmc26 Ya, dengan cara ini Anda dapat memasukkan f=\tajuk Try it Online dan meninggalkan fungsi anonim, tanpa memengaruhi penghitung byte TiO otomatis
Tn. Xcoder
9

05AB1E , 5 byte

нœ¹мà

Cobalah online!

Penjelasan

нœ¹мà

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

sumber
7

Pyth , 5 byte

h-.ph

Cobalah online!

Penjelasan

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

Jelly , 6 byte

XŒ!ḟµḢ

Cobalah online!

1 byte lebih dari jawaban 05AB1E dan Pyth.

Penjelasan:

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.

Saya memilih Xkarena ini adalah cara terpendek yang saya tahu untuk memilih elemen apa pun dari daftar tanpa mengubah daftar ( dan tidak berfungsi, ḷ/dan ṛ/lebih lama), dan itu menyebabkan beberapa keacakan.

Di µsini cukup berlebihan, tetapi tanpa itu, akan dipasangkan dengan , dan ditafsirkan sebagai "menyaring kepala input", yang bukan apa yang saya butuhkan di sini (apa yang saya butuhkan adalah "menyaring input, dan dapatkan kepala ").

pengguna202729
sumber
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}

menggunakan pengacak buruk untuk mengulangi setiap permutasi "acak".

Mungkin terbukti salah tetapi afaik randomizer buruk hanya berarti kita tidak akan mendapatkan keacakan yang sebenarnya, tetapi masih akan mendapatkan setiap permutasi.

Tampaknya berfungsi pada semua case di chrome untuk saya tetapi tampaknya karena perilaku yang tidak terdefinisi dalam penyalahgunaan semacam ini, itu tidak dapat bekerja di beberapa browser.

(Mungkin sangat ungolfed merasa bebas untuk memperbaikinya dalam solusi Anda sendiri)

80 byte

Berkat komentar bajak laut eBay -banyak byte

-4 byte terima kasih kepada Rick

f=a=>eval('s=[...a[0]].sort(()=>.5-Math.random()).join``;a.indexOf(s)<0?s:f(a)')
Aku
sumber
Fungsi panah FYI diizinkan (misalnya, a=>bbukan function(a){return b}). Menghemat banyak byte.
Wow ... itu akan menghemat beberapa byte.
Imme
s.split("")bisa [...s]. Juga join("")bisa `join```
Rick Hitchcock
@ ThePirateBay saya takut itu akan terjadi, tapi mengapa begitu? (Saya sadar bahwa pengurutan tidak sepenuhnya acak, tetapi semua urutan HARUS dimungkinkan)
Imme
@Imme. Berikut adalah 87 byte versi yang berfungsi. Perhatikan bahwa sortfungsi Anda tidak pernah kembali 0(atau setidaknya sangat jarang), itu sebabnya tidak berfungsi.
4

Haskell , 58 byte

-1 byte dan perbaikan terima kasih kepada Laikoni.

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

Cobalah online!

Mungkin tidak layak mengimpor Data.Listpermutasi tetapi eh.

benar-benar manusiawi
sumber
1
Anda dapat menyimpan byte dengan notElem. saya akan terkejut jika seseorang menemukan fungsi permutasi yang mengalahkan impor, pendekatan terpendek saya adalah 60 byte vs 29 byte impor.
Laikoni
1
Berikut adalah fungsi permutasi 43 byte, tetapi hanya untuk daftar gratis duplikat.
Laikoni
1
Solusi Anda saat ini tidak berfungsi karena $sebelumnya tidak ada l!!0.
Laikoni
3

Brachylog , 7 byte

hp.¬∈?∧

Cobalah online!

Penjelasan

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)
Fatalisasi
sumber
3

Mathematica, 57 byte

non-deterministik

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

Cobalah online!

Mathematica, 56 byte

deterministik

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

Cobalah online!

J42161217
sumber
3

Japt , 7 6 byte

-1 byte terima kasih kepada @Shaggy

á kN ö

Cobalah online!

Mengambil string input sebagai beberapa input, bukan sebagai array. Menghasilkan permutasi acak; beralih öke guntuk mendapatkan yang pertama sebagai gantinya.

Penjelasan

á 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
sumber
Kacang, Anda mengalahkan saya untuk itu. Anda dapat mengambil input sebagai string individual dan menyimpan byte á kN ö.
Shaggy
@ Shaggy Itu cara yang bagus untuk mendapatkan item input pertama, saya harus ingat itu. Terima kasih!
Justin Mariner
2

MATL , 15 , 13 , 12 byte

1X)Y@Z{GX-1)

Cobalah online!

Disimpan 2 byte berkat Sanchises. setdiff(...,'rows')lebih pendek daripada meniadakan ismember(...,'rows')dan menghindari satu duplikasi. Menyimpan byte lain berkat Luis Mendo, dengan beralih ke sel alih-alih array.

Penjelasan:

Setara MATLAB / Oktaf juga disertakan.

                 % 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 harus satu format {'abc', 'acb'}.

Stewie Griffin
sumber
2

Python 3 , 78 byte

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

Cobalah online!

-1 byte terima kasih kepada Tn. Xcoder

HyperNeutrino
sumber
if x not in aadalah if~-(x in a)untuk 178
Mr. Xcoder
@ Mr.Xcoder. Maksudmu 78benar?
@ThePirateBay Ya, saya lakukan ... Aduh!
Tn. Xcoder
1
Bagaimana dengan 66 byte ?
NieDzejkob
1
@NieDzejkob Itu mengesankan lebih pendek. Anda harus memposting sendiri jika Anda mau
HyperNeutrino
2

Pip , 11 byte

@:_NIgFIPMa

Mengambil input sebagai argumen baris perintah. Cobalah online!

Penjelasan

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

Python 3 , 87 byte

Saya percaya ini adalah satu - satunya pengajuan sejauh ini yang tidak menggunakan permutasi bawaan atau acak acak / semacam. Meskipun lebih lama, saya pikir algoritma ini cukup rapi.

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]

Cobalah online!

Penjelasan

Apa yang kami lakukan pada dasarnya adalah ini:

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

Inilah bukti bahwa itu bekerja:

Untuk string S, tentukan front(S)sebagai set string yang diperoleh dengan memilih satu karakter dari Sdan memindahkannya ke depan S. Sebagai contoh, front(ABCDE)adalah {ABCDE, BACDE, CABDE, DABCE, EABCD}.

Sekarang perhatikan daftar anagram L, sehingga Ltidak mengandung setiap anagram yang mungkin (sesuai dengan deskripsi masalah). Kami ingin menunjukkan bahwa ada string Sdi Lsehingga front(S)mengandung setidaknya satu anagram S'yang tidak L.

Misalkan, dengan cara kontradiksi, bahwa untuk setiap string Smasuk L, setiap string front(S)juga masuk L. Perhatikan bahwa kita dapat menghasilkan permutasi acak string apa pun melalui serangkaian gerakan "fronting". Misalnya, untuk mendapatkan

ABCDE -> BAEDC

kita bisa

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

Kami berasumsi bahwa untuk masing-masing Sdalam L, setiap S'dalam front(S)juga masuk L. Ini juga berarti bahwa setiap yang ada S''di front(S')dalam L, dan sebagainya. Oleh karena itu, jika Sdalam L, setiap permutasi Sjuga dalam L. Maka Lharus satu set anagram lengkap, sebuah kontradiksi.

Jadi, karena kita dijamin bahwa ada setidaknya satu permutasi tidak di L, harus ada string Sdi Lmana beberapa S'di front(S)tidak di L. QED.

Kode berulang front(S)untuk masing-masing Sdalam Ldan memilih S'mana yang tidak ada L. Dengan hasil di atas, akan ada setidaknya satu S'yang memenuhi syarat.

DLosc
sumber
2

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

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

Keterampilan bermain golf saya tentu saja menjadi lebih baik sejak saya pertama kali memposting ini!

Cobalah online!

Perwujudan Ketidaktahuan
sumber
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

Temukan permutasi leksikografis pertama dari elemen pertama array yang tidak terkandung dalam array.

Neil
sumber
1

Kotlin , 104 byte

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

Yg diperindahkan

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

Uji

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

C ++, 169 byte

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

Cobalah online!

Steadybox
sumber
1

Scala, 50 byte

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

Cobalah online!

Penjelasan

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

R, 89 byte

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

Contoh surat berulang-ulang dari entri pertama (karena harus menjadi anagram satu sama lain) dan berhenti ketika salah satu dari sampel tersebut tidak ada dalam daftar asli.

Andrew Haynes
sumber
82 bytes
Giuseppe
1

PHP , 70 byte

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

Jalankan di server web, masukkan 0 nilai getar yang diindeks atau Coba online!

Tidak disatukan

$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
sumber
Simpan dua byte dengan do{...}while($j);sebagai gantinya $j=1;while($j){...}. Gunakan definisi in-place untuk $gmenyingkirkan kawat gigi (dan simpan empat byte).
Titus
1

PHP, 58 55 byte

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

non-deterministik; mengambil input dari argumen baris perintah

Jalankan dengan php -r <code>diikuti oleh kata-kata yang dipisahkan ruang atau coba online .

Titus
sumber
1

Attache , 16 byte

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

Cobalah online!

Penjelasan

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

Alternatif

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Conor O'Brien
sumber
0

J , 25 byte

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

Inputnya adalah daftar string kotak - Saya merasa adil seperti ini dan tidak menyatakan daftar string secara eksplisit sebagai $ 8 $ 'abcde123', 'ab3e1cd2', '321edbac', 'bcda1e23'.

Saya tidak suka @ mess dalam kode saya, tetapi ada banyak kata kerja berseri saat ini.

Bagaimana itu bekerja:

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

Cobalah online!

Galen Ivanov
sumber
1
Mengambil input sebagai meja, untuk 21 byte: {.@(-.~i.@!@#@{.A.{.). Cobalah online!
Jonah
0

05AB1E , 5 byte

нœIмà

Cobalah online!

Penjelasan

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

Hampir sama dengan jawaban yang ditemukan oleh @ThePirateBay.

Cinari
sumber
0

JavaScript, 87 byte

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

Cobalah online!

Jawaban ini didasarkan (walaupun sangat dimodifikasi) pada jawaban Imme . Dia menyarankan dalam komentar bahwa ini harus menjadi jawaban yang berbeda.

Masalah dengan pendekatan lama adalah karena sortsepenuhnya tergantung pada implementasi. Standar tidak menjamin urutan pemanggilan fungsi sortir, oleh karena itu secara teoritis mungkin tidak pernah berakhir untuk kasus uji pertama atau kedua.

Pendekatan ini beberapa byte lebih lama, tetapi itu menjamin bahwa itu akan selesai dalam waktu terbatas, bahkan jika Math.randomtidak pernah kembali .5.


sumber
0

CJam , 11 byte

q~_0=m!\m0=

Cobalah online!

Penjelasan

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"
Buah Esolanging
sumber
Saya pikir mungkin ada kesalahan ketik dalam penjelasan Anda - Jawaban yang diberikan kode Anda berbeda dari apa yang dikatakan penjelasan Anda
MildlyMilquetoast
0

Perl 6 , 42 byte

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

Cobalah online!

Acak acak string pertama input hingga bukan merupakan elemen input.

Penjelasan:

{(.[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
Jo King
sumber