Выведите анаграмму! Нет, не тот!

28

Учитывая список уникальных строк, которые являются анаграммами друг друга, выведите анаграмму тех слов, которая отличается от каждого слова в списке.

Строки будут буквенно-цифровыми, и гарантированно будет действительной анаграммой.

Программа или функция могут, но не должны быть недетерминированными, то есть при наличии одного и того же ввода многократное выполнение кода может давать разные выходные данные, если каждый возможный вывод является допустимым.

Тестовые случаи

[Input] -> Possible output
-----------------
[ab] -> ba
[aba, aab] -> baa
[123, 132, 231, 312, 321] -> 213
[hq999, 9h9q9, 9qh99] -> 999hq
[abcde123, ab3e1cd2, 321edbac, bcda1e23] -> ba213ecd
MildlyMilquetoast
источник

Ответы:

20

Python 3 , 64 байта

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

Попробуйте онлайн!

Мистер Xcoder
источник
4
Но есть itertoolsли ответ?
MildlyMilquetoast
@MistahFiggins Номинация
г-н Xcoder
@ Mr.Xcoder до 22 июля 2015 года
Стэн Струм
@StanStrum Я только что упомянул об этом, я знаю об этом ограничении. Как сказал Стьюи ...
Мистер Xcoder
1
@ jpmc26 Да, таким образом, вы можете вставить f=\заголовок Try it Online и оставить функцию анонимной, не влияя на автоматический счетчик байтов TiO
Mr. Xcoder
9

05AB1E , 5 байтов

нœ¹мà

Попробуйте онлайн!

объяснение

нœ¹мà

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

источник
4

Желе , 6 байт

XŒ!ḟµḢ

Попробуйте онлайн!

На 1 байт больше, чем 05AB1E и Pyth.

Объяснение:

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.

Я выбрал, Xпотому что это самый короткий способ, которым я знаю, чтобы выбрать любой элемент из списка, не изменяя список ( и не работает, ḷ/и ṛ/длиннее), и это может привести к некоторой случайности.

µЗдесь довольно лишними, но без него, будет работать в паре с , и это интерпретируется как «фильтр из головки ввода», который не то , что надо здесь (что мне нужно «отфильтровать вход, и получить голову ").

user202729
источник
4

Javascript, 118 байт

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

использует плохой рандомизатор для перебора каждой «случайной» перестановки.

Возможно, ошибочно, но на самом деле плохой рандомизатор просто означает, что мы не получим истинную случайность, но все равно получим каждую перестановку.

Кажется, что работает для всех случаев в Chrome для меня, но, видимо, из-за неопределенного поведения в такого рода злоупотребления, он не может работать в некоторых браузерах.

(Вероятно, очень безрассудный, не стесняйтесь улучшать это в своих собственных решениях)

80 байт

Благодаря комментарию pirateBay - много байтов

-4 байта благодаря Рику

f=a=>eval('s=[...a[0]].sort(()=>.5-Math.random()).join``;a.indexOf(s)<0?s:f(a)')
Imme
источник
FYI функции стрелок разрешены (например, a=>bвместо function(a){return b}). Это экономит много байтов.
Вау ... это сэкономит немало байтов.
Im
s.split("")может быть [...s]. Также join("")можно `присоединиться```
Рик Хичкок
@ThePirateBay я боялся, что это будет так, но почему это так? (им известно , что - то не полностью случайным, но все последовательности должны быть по возможности)
IMME
@Imme. Вот рабочая версия 87 байт . Обратите внимание, что ваша sortфункция никогда не возвращается 0(или, по крайней мере, крайне редко), поэтому она не работает.
4

Haskell , 58 байт

-1 байт и исправление благодаря Laikoni.

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

Попробуйте онлайн!

Это, вероятно, не стоит импортировать Data.Listдля перестановок, но да.

totallyhuman
источник
1
Вы можете сохранить байт с помощью notElem. я был бы удивлен, если бы кто-то нашел функцию перестановки, которая превосходит импорт, мой самый короткий подход - 60 байтов против 29 байтов импорта.
Лайкони
1
Вот функция перестановки в 43 байта, но только для дубликатов свободных списков.
Лайкони
1
Также ваше решение в настоящее время не работает, потому что $раньше его не было l!!0.
Лайкони
3

Japt , 7 6 байт

-1 байт благодаря @Shaggy

á kN ö

Попробуйте онлайн!

Принимает входные строки как несколько входных данных, а не как массив. Выводит случайную перестановку; переключитесь, öчтобы gполучить первый вместо этого.

объяснение

á 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
Джастин Маринер
источник
Орехи, ты побил меня к этому. Вы можете принять ввод как отдельные строки и сохранить байт с помощью á kN ö.
Лохматый
@ Shaggy Это отличный способ получить первый элемент ввода, я должен помнить это. Благодарность!
Джастин Маринер,
2

MATL , 15 , 13 , 12 байтов

1X)Y@Z{GX-1)

Попробуйте онлайн!

Сохранено 2 байта благодаря Sanchises. setdiff(...,'rows')короче отрицания ismember(...,'rows')и избегает одного дублирования. Благодаря Луису Мендо сохранил еще один байт, переключаясь на ячейки вместо массивов.

Объяснение:

MATLAB / октавные эквиваленты также включены.

                 % 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

Ввод должен быть одного формата {'abc', 'acb'}.

Стьюи Гриффин
источник
2

Python 3 , 78 байт

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

Попробуйте онлайн!

-1 байт благодаря мистеру Xcoder

HyperNeutrino
источник
if x not in aэто if~-(x in a)для 178
Г -
@ Mr.Xcoder. Вы имеете в виду 78, верно?
@ThePirateBay Да, я делаю ... Упс!
г-н Xcoder
1
Как насчет 66 байтов ?
NieDzejkob
1
@NieDzejkob Это впечатляюще короче. Вы должны опубликовать свой собственный, если хотите
HyperNeutrino
2

Пип , 11 байт

@:_NIgFIPMa

Принимает входные данные в качестве аргументов командной строки. Попробуйте онлайн!

объяснение

          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
источник
2

Python 3 , 87 байт

Я считаю, что это пока единственное представление, в котором не используется ни встроенная перестановка, ни случайная случайная выборка / сортировка. Хотя он длиннее, я думаю, что алгоритм довольно аккуратный.

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]

Попробуйте онлайн!

объяснение

То, что мы делаем, в основном это:

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

Вот доказательство того, что это работает:

Для строки Sопределите front(S)набор строк, полученный путем выбора одного символа из Sи перемещения его в начало S. Например, front(ABCDE)есть {ABCDE, BACDE, CABDE, DABCE, EABCD}.

Теперь рассмотрим список анаграмм L, который Lне содержит всех возможных анаграмм (согласно описанию проблемы). Мы хотим показать , что существует строка Sв Lтаким образом, что front(S)содержит , по меньшей мере , один анаграмму , S'который не в L.

Предположим в противоречие, что для каждой строки Sв L, каждая строка в front(S)также в L. Заметьте, что мы можем сгенерировать произвольную перестановку любой строки с помощью серии «фронтовых» ходов. Например, чтобы получить

ABCDE -> BAEDC

мы можем сделать

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

Мы предположили , что для каждого Sдюйма L, каждый S'в front(S)также в L. Это также означает , что каждый S''в front(S')находится в L, и так далее. Следовательно, если Sнаходится в L, каждая перестановка Sтакже в L. Тогда Lдолжен быть полный набор анаграмм, противоречие.

Таким образом, поскольку мы гарантировали , что существует по крайней мере одна перестановка не в L, должна существовать строка Sв Lтечение которых некоторые S'в front(S)это не L. QED.

Код перебирает front(S)для каждого Sв Lи выбирает S'который не находится в L. По приведенному выше результату будет хотя бы один, S'который соответствует требованиям.

DLosc
источник
1

JavaScript (ES7), 172 байта

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

Найдите первую лексикографическую перестановку первого элемента массива, который не содержится в массиве.

Нил
источник
1

Котлин , 104 байта

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

украшенный

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

Тест

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
источник
1

C ++, 169 байт

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

Попробуйте онлайн!

Steadybox
источник
1

Скала, 50 байт

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

Попробуйте онлайн!

объяснение

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
Карл Билефельдт
источник
1

R, 89 байт

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

Повторно сэмплируйте буквы из первой записи (поскольку они должны быть анаграммами друг друга) и остановитесь, когда один из этих сэмплов отсутствует в исходном списке.

Эндрю Хейнс
источник
82 байта
Джузеппе
1

PHP , 70 байт

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

Запустите на веб-сервере, введя 0 проиндексированных значений get или попробуйте онлайн!

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
источник
Сохранить два байта с do{...}while($j);вместо $j=1;while($j){...}. Используйте определение на месте для того, $gчтобы избавиться от скобок (и сохранить четыре байта).
Тит
1

PHP, 58 55 байт

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

недетерминированная; принимает входные данные из аргументов командной строки

Запустите с php -r <code>разделенными пробелами словами или попробуйте онлайн .

Titus
источник
1

Атташе , 16 байт

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

Попробуйте онлайн!

объяснение

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

альтернативы

17 байт :{&\S! !S@_[0]Ø_}

18 байт :{&\S! !Id@_[0]Ø_}

19 байт :{&\S!(!Id)@_[0]Ø_}

26 байт :{&\S!Permutations@_[0]Ø_}

26 байт :{&\S!Permutations[_@0]Ø_}

26 байт :{(Permutations[_@0]Ø_)@0}

26 байт :&\S##~`Ø#Permutations@&\S

27 байт :Last@{Permutations[_@0]Ø_}

27 байт :`@&0@{Permutations[_@0]Ø_}

28 байт :Last##~`Ø#Permutations@&{_}

28 байт :Last##~`Ø#Permutations@Last

28 байт :First@{Permutations[_@0]Ø_}

30 байтов :{NestWhile[Shuffle,`in&_,_@0]}

33 байта :{If[(q.=Shuffle[_@0])in _,$@_,q]}

33 байта :{q.=Shuffle[_@0]If[q in _,$@_,q]}

34 байта :{If[Has[_,q.=Shuffle[_@0]],$@_,q]}

Конор О'Брайен
источник
0

J , 25 байт

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

Входные данные представляют собой список строк в штучной упаковке - я чувствовал, что это справедливо, и не объявлять списки строк явно как 4 8 $ 'abcde123', 'ab3e1cd2', '321edbac', 'bcda1e23'.

Мне не нравится @ беспорядок в моем коде, но на этот раз много сериализованных глаголов.

Как это работает:

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

Попробуйте онлайн!

Гален Иванов
источник
1
Принимая вход в виде таблицы, в течение 21 байт: {.@(-.~i.@!@#@{.A.{.). Попробуйте онлайн!
Иона
0

05AB1E , 5 байтов

нœIмà

Попробуйте онлайн!

объяснение

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

Практически тот же ответ, который нашел @ThePirateBay.

Cinari
источник
0

JavaScript, 87 байт

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

Попробуйте онлайн!

Этот ответ основан (хотя и сильно изменен) на ответе Имме . Он предложил в комментарии, что это должен быть другой ответ.

Проблема старого подхода заключается в том, что sortон полностью зависит от реализации. Стандарт не гарантирует порядок вызова функции сортировки, поэтому теоретически он может никогда не закончиться для первого или второго контрольного примера.

Этот подход на несколько байтов длиннее, но он гарантирует, что он завершится в течение ограниченного времени, даже если Math.randomникогда не вернется .5.


источник
0

CJam , 11 байт

q~_0=m!\m0=

Попробуйте онлайн!

объяснение

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
источник
Я думаю, что в вашем объяснении может быть опечатка - ответ, который дает ваш код, отличается от того, что говорит ваше объяснение
MildlyMilquetoast
0

Perl 6 , 42 байта

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

Попробуйте онлайн!

Случайно перемешивает первую строку ввода, пока она не станет элементом ввода.

Объяснение:

{(.[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
Джо Кинг
источник