Генерация случайного расстройства

30

Описание задачи

«Нарушение» последовательности - это перестановка, при которой ни один элемент не появляется в исходном положении. Например ECABD, это расстройство ABCDE, но CBEDAэто не так:

ABCDE
 | |   <- B and D are in their orignal positions
CBEDA

Учитывая последовательность, генерировать случайное нарушение ее.

Заметки

  • Вы можете взять либо строку в качестве входных данных, либо массив / список элементов (целые числа, символы, объекты ...)

  • Вместо того, чтобы возвращать новый объект, вы можете изменить существующий, меняя его элементы

  • Каждое расстройство должно иметь равную вероятность возникновения

  • Вы можете предположить, что в последовательности более одного элемента, и ни один не появляется более одного раза

shooqie
источник
4
Связанный?
Эддисон Крамп
3
@VoteToClose: ха-ха, полностью обанкротился
shooqie
Я не очень много знаю обо всем этом, но связано ли это каким-либо образом с теоремой о неподвижной точке ... согласно которой вещи всегда окажутся в своей собственной позиции или что-то в этом роде ...? Держу пари, я ошибаюсь, но кто-то, пожалуйста, поправьте меня :)
Фархан Анам
Есть ли гарантия того, что элементы будут уникальными или они могут содержать дубликаты?
Carcigenicate
1
@Carcigenicate: это прямо в описании; Вы можете предположить, что нет дубликатов
shooqie

Ответы:

12

CJam , 14 байтов

q:X{mr_X.=:|}g

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

Продолжает перетасовывать ввод, пока это не помешает.

объяснение

q:X   e# Read input and store it in X.
{     e# While the condition at the end of the loop is truthy...
  mr  e#   Shuffle the string.
  _X  e#   Duplicate it and push the input.
  .=  e#   Element-wise equality check.
  :|  e#   Reduce OR over the list, gives something truthy if any character
      e#   remained in its original position.
}g
Мартин Эндер
источник
1
Я бы хотел, чтобы ОП указала, что решения должны гарантировать, что они всегда заканчиваются.
Джон Дворжак
4
@JanDvorak Ну, вероятность того, что это не закончится, равна 0. Но вы правы, что требование детерминированного времени выполнения сделало бы задачу более интересной.
Мартин Эндер
Является ли вероятность на самом деле 0? Операция тасования не будет идеальной, как она на самом деле работает? Я думаю, что это, вероятно, хорошее приближение к тому, что запрашивал OP, но я сомневаюсь, что вероятности каждого нарушения одинаковы (вероятно, это зависит от некоторого начального значения PRNG, которое, вероятно, используется операцией тасования).
Никто
3
@ Никто не сомневается, что вы можете получить абсолютно одинаковые результаты от PRNG, используя любой алгоритм. Тем не менее, предполагая, что сам тасование является равномерным (что в Java-документации гарантирует «Все перестановки происходят примерно с равной вероятностью»), решение на основе отклонения также приведет к равномерным отклонениям, потому что каждое отклонение - это одна перестановка, и каждое Перестановка имеет такую ​​же вероятность.
Мартин Эндер
1
@ Никто здесь не математик. Условие, которое либо успешно, либо безуспешно, называется испытанием Бернулли в статистике. Это подразумевает, что вероятность необходимости k испытаний для первого успеха составляет (1 - p) ^ (k - 1) * p, где p - вероятность успешного расстройства. Легко видеть, что с ростом k вероятность необходимости k испытаний становится исчезающе малой. Поэтому мы говорим, что алгоритм останавливается с вероятностью 1 («почти наверняка»), и все же не исключено, что он никогда не останавливается.
слуга
9

Желе , 6 байт

Ẋ=³S$¿

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

объяснение

Ẋ    ¿    Shuffle the given list while this is nonzero for it:
    $       A two-step process:
 =³           Element-wise equality of it and L (the original list)...
   S          Sum the ones in this binary array.

Джонатан Аллан сохранил байт.

Линн
источник
5
Значит, у тебя есть шляпа от Winter Bash раньше времени? :-)
Луис Мендо
2
Время нарисовать красивую новую картинку, Ẋ=³S$¿экономит байт.
Джонатан Аллан
2
Я никогда об этом не знал $. Благодарность!
Линн
Это 6 символов, но больше 6 байтов. Ẋ = ³S $ ¿длины байта: 312112. Таким образом, всего 10 байтов.
mxfh
6

Python, 85 байт

Изменяет переданный ему список (разрешенный мета и в вопросе).

from random import*
def D(l):
 o=l[:]
 while any(x==y for x,y in zip(o,l)):shuffle(l)

Попробуйте онлайн здесь!

FlipTack
источник
1
Если вы укажете Python 2, я думаю , вы могли бы заменить def D(l):с , l=input()а затем сохранить отступы пробелов в следующих строках (так у вас есть программа вместо функции). Не понизить, хотя!
Матмандан
@mathmandan хорошая идея, но тогда мне нужно будет снова распечатать ее, если это полная программа, которая стоит больше байтов.
FlipTack
1
Хорошо, если вы говорите так. Я предполагаю, что в спецификации говорилось, что вам не нужно распечатывать или возвращать результат - что достаточно взять список [из пользовательского ввода] и перемешать его. Но разумно читать «существующий» как «существующий до запуска любого вашего кода», и в этом случае я согласен с вами. (Может быть, есть устоявшийся консенсус по этому вопросу.) :)
mathmandan
5

ES6 (Javascript), 7169 байт

Ввод и вывод - это массивы, которые должны работать с любыми типами элементов (строки, числа и т. Д.), Если их можно сравнить с "==".

Golfed

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

Тест

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

F(['A','B','C','D'])
Array [ "D", "C", "A", "B" ]

F(['A','B','C','D'])
Array [ "D", "A", "B", "C" ]

F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]

F(['A','B','C','D'])
Array [ "D", "C", "B", "A" ]

F(['A','B','C','D'])
Array [ "C", "D", "B", "A" ]

Интерактивный фрагмент

F=s=>(r=[...s]).sort(_=>Math.random()-.5).some((e,i)=>s[i]==e)?F(s):r

function G() {
    console.log(F(T.value.split``).join``); 
}
<input id=T value="ABCDEF"><button id=G onclick="G()">GENERATE</button>

дирижабль
источник
5

Perl 6 , 33 байта

{first (*Zne$_).all,.pick(*)xx *}

Лямбда, которая принимает список целых чисел или символов в качестве входных данных и возвращает новый список.

Если он должен поддерживать списки произвольных значений, neего следует заменить на !eqv(+2 байта).

( Попробуйте онлайн. )

Объяснение:

  • { }: Определяет лямбду
  • .pick(*): Генерирует случайное перемешивание списка ввода.
  • .pick(*) xx *: Создает ленивую бесконечную последовательность таких перемешиваний.
  • (* Zne $_).allЛямбда, которая упаковывает два списка (его аргумент *и аргумент внешней лямбды $_) с помощью neоператора (отрицательное равенство строк), получая список логических значений, а затем создает allсоединение, чтобы свернуть их в одно логическое состояние.
  • first PREDICATE, SEQUENCE: Берет первый элемент из нашей бесконечной последовательности перестановок, который удовлетворяет критерию «сумасшествия».
SMLS
источник
3

Perl 6 , 45 байт

{(@^a,{[.pick(*)]}...{none @a Zeqv@$_})[*-1]}
{(@^a,{[.pick(*)]}...{!sum @a Zeqv@$_})[*-1]}

Попытайся

Ввод - это массив всего.

Expanded:

{
  (

    @^a,          # declare parameter, and seed sequence generator

    {             # lambda with implicit parameter 「$_」
      [           # store into an array
        .pick(*)  # shuffle 「$_」
      ]
    }

    ...           # keep generating the sequence until

    {
      none        # none
      @a          # of the outer blocks input
      Z[eqv]      # is zip equivalent
      @$_         # with the current value being tested
    }

  )[ * - 1 ]      # return the last value
}
Брэд Гилберт b2gills
источник
3

MATL, 7 байт

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

Честно говоря, я не совсем уверен t, что там нужно, но это единственный способ заставить это работать. Он используется для того, чтобы я мог сравнить пользовательский ввод (полученный с G) со случайной перестановкой. Я думаю, я мог бы сравнить два без этого, но ...?

Во всяком случае, здесь идет:

`Z@tG=a

`          % Loop
 Z@        % Random permutation of input
   t       % Duplicating the stack
    G      % Paste from clipboard G (user input)
     =     % Comparing the random permutation with the input (retrieved from clipboard)
      a    % any(input == random permutation)
           % Implicit end and display

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

Стьюи Гриффин
источник
Какие-нибудь улучшения? Мне действительно нужно tтам или я могу от этого избавиться? Было весело пытаться играть в гольф в MATL ... :)
Stewie Griffin
:-) Я не вижу, как избавиться от этого t(или, что эквивалентно, другого G). Вам нужно что-то оставить в стеке для следующей итерации или в качестве конечного результата
Луис Мендо
3

На самом деле , 13 байтов

;;WX╚│♀=ΣWX)X

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

Объяснение:

;;WX╚│♀=ΣWX)X
;;             make two copies of input
  WX╚│♀=ΣW     while top of stack is truthy:
   X             discard top of stack
    ╚            shuffle array
     │           duplicate entire stack
      ♀=         compare corresponding elements in shuffled and original for equality
        Σ        sum (truthy if any elements are in the same position, else falsey)
          X)X  discard everything but the derangement
Mego
источник
2

Октава, 56 55 байт

x=input('');while any(x==(y=x(randperm(nnz(x)))));end,y

Мы должны использовать, input('')так как это не функция. Кроме того, так как я могу выбрать, чтобы ввод был в виде строки, мы можем использовать хитрость это nnz(x)==numel(x).

Объяснение:

x=input('')            % Self-explanatory
while any(x==y)        % Loop until x==y has only 0s (i.e. no elements are equal)
y=x(randperm(nnz(x)))  % Continue to shuffle the indices and assign x(indices) to y
end                    % End loop
y                      % Display y

Спасибо Луису за то, что он заметил, что ввод может быть строкой, поэтому я мог бы использовать nnzвместо numelсохранения два байта.

Стьюи Гриффин
источник
Примечание для себя: прочитайте весь вопрос в следующий раз :) Спасибо!
Стьюи Гриффин
1
Это происходит со мной все время :-)
Луис Мендо
2

MATL, 13 байт

Это совместные усилия @LuisMendo и меня. В отличие от многих других ответов здесь, этот является детерминированным в том смысле, что он не отбирает случайные перестановки, пока не получит расстройство, но генерирует все отклонения и выбирает один случайным образом.

Y@tG-!Af1ZrY)

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

объяснение

Y@tG-!Af1ZrY)
Y@             generate all permutatoins
  t            create a duplicate
   G-!A        find the (logical) indices of all valid derangements (where no character of the string is in the same position as the original string)
       f       convert logical to linear indices
        1Zr    choose one of those indices randomly
           Y)  get the derangement (from the ones we generated earlier) at this index
flawr
источник
2

Pyth - 10 9 байт

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

.WsqVHQ.S

Попробуйте это онлайн здесь .

.W           Iterate while
 s           Sum, this is works as any() on a boolean list
  qV         Vectorized equality
   H         The lambda variable for the check step
   Q         The input
 .S          Shuffle
  (Z)        Lambda variable, implicit
 (Q)         Start .W with input, implicit
Maltysen
источник
Можете ли вы добавить объяснение. Я хотел написать ответ Pyth. Я не знаю много об этом.
Гурупад Мамадапур
@GurupadMamadapur уверен, был бы счастлив тоже.
Maltysen
1
@GurupadMamadapur добавил. У нас есть учебник . Это довольно устарело, но научит вас основам. Если вам нужна помощь с чем-либо, связанным с pyth, не стесняйтесь пинговать меня в чате.
Maltysen
2

Mathematica, 57 байт

#/.x_:>RandomChoice@Select[Permutations@x,FreeQ[#-x,0]&]&

Безымянная функция, принимая список whatevers в качестве входных данных и выводя список. После генерации всех перестановок #входных данных xмы оставляем только те, для которых набор #-xразностей элементов не содержит a 0; затем мы делаем (равномерно) случайный выбор из этого множества.

Грег Мартин
источник
1
хороший! Чуть дольше, #/.x_:>NestWhile[RandomSample[#,Length@#]&,#,Not@FreeQ[#-x,0]&]&очевидно, быстрее на практике для длинных струн
Мартин
Подожди, ты говоришь мне, что в Mathematica нет встроенных средств защиты от сбоев? : o
shooqie
Я наполовину ожидал встроенного себя :)
Грег Мартин
0

PHP, 85 байт

for($a=$b=str_split($argv[1]);array_diff_assoc($a,$b)!=$a;)shuffle($b);echo join($b);

Копирует строковый аргумент в два массива, перетасовывает один из них, пока разница между ними (также сравнивая индексы элементов) не сравняется с другой. Беги с -r.

Titus
источник
0

R, 59 байт

z=x=1:length(y<-scan(,""));while(any(x==z))z=sample(x);y[z]

Читает список элементов в STDIN, берет длину списка и начинает выборочные диапазоны от 1 до длины, пока не найдет элемент, который не разделяет места с упорядоченным списком. Затем печатает этот список.

JAD
источник
0

Чудо , 32 байта

f\@[/>#I zip#=[#0a\shuf#0]?f a?a

Использование:

f\@[/>#I zip#=[#0a\shuf#0]?f a?a];f[1 2 3 4 5]

объяснение

Более читабельно:

f\@[
  some #I zip #= [#0; a\ shuf #0]
    ? f a
    ? a
]

Рекурсивная функция f. Проводит поэлементное сравнение между fсписком ввода и перетасованной версией списка ввода. Если сравнение дает какие-либо равные значения, то fвызывается в перетасованном списке. В противном случае мы просто возвращаем перемешанный список.

Mama Fun Roll
источник
0

Рубин, 67 байт

def f a
while (a.zip(o=a.shuffle).map{|x,y|x-y}.index 0);end
o
end
DepressedDaniel
источник
0

Октава, 54 53 байта

@(a)((p=perms(a))(L=!any(p==a,2),:))(randi(sum(L)),:)

Создайте все перестановки aи выберите случайным образом строку, с которой нет общего элемента a.

примечание: оно случайно совпадает с ответом @flawr MATL!

rahnema1
источник
0

Clojure, 94 90 79 байтов

#(let[s(shuffle %)](if(not(some(fn[[x y]](= x y))(map vector % s)))s(recur %)))

-4 байта, изменяя условное внутри редукции andи вставляя done?.

-11 байт путем преобразования сокращения в some.

Woot! Удар PHP.

Метод грубой силы. Перемешивает список, пока он недействителен. Это быстро заканчивается глупо, учитывая, что это метод грубой силы, который ничего не делает для предотвращения повторных попыток. Он обнаружил 1000 разложений длинного списка из 1000 элементов менее чем за секунду.

Ungolfed:

(defn dearang [ls]
  (let [s (shuffle ls)
        bad? (some (fn [[x y]] (= x y))
                (map vector ls s))]
    (if (not bad?) s (recur ls))))
Carcigenicate
источник
0

Clojure, 56 байт

#(let[s(shuffle %)](if((set(map = % s))true)(recur %)s))

Обратите внимание, что строка не может быть перетасована, должна быть передана через seqили vec.

Первоначально я пытался, #(first(remove(fn[s]((set(map = % s))true))(iterate shuffle %)))но recurподход действительно короче, чем iterate.

Магия в том, что (set(map = % s))возвращает либо набор ложных, набор истинных или набор истинных и ложных. Это можно использовать как функцию, если она содержит, trueто ответ - trueиначе ложь nil. =счастлив принять два входных аргумента, не нужно оборачивать это чем-то.

((set [false]) true)
nil

Может быть, есть еще более короткий способ проверить, является ли какое-либо из значений истинным?

NikoNyrh
источник
0

APL, 11 байт.

Со строкой в ​​правом аргументе:

⍵[⍋(⍴⍵)?⍴⍵]

объяснение

ρ⍵ получает длину (или форму) правильного аргумента.

?возвращает случайный массив (⍴⍵)из этих чисел.

возвращает их порядок, чтобы не было дубликатов.

⍵[..] представляет случайный ассортимент строки с использованием этого индекса.

Джейкоб Атли
источник
Добро пожаловать в PPCG! Мы требуем, чтобы все записи были действительными функциями или полными программами, поэтому ваш ответ должен принимать ввод через аргумент функции или метод ввода.
ETHproductions
Я думаю, что это должно соответствовать требованиям сейчас. Требуется правильный аргумент или .
Джейкоб Атли