Это случайное перемешивание?

19

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

Сегодня вас просят определить, является ли перестановка на самом деле случайным образом. Наше определение riffle shuffle адаптировано из нашего последнего вопроса:

Первая часть шаффла - это разделение. В разделе делить колода карт на две части. Два подраздела должны быть непрерывными, взаимоисключающими и исчерпывающими. В реальном мире вы хотите, чтобы ваш раздел был как можно ближе к максимально возможному, однако в этом испытании это не рассматривается, все разделы, включая вырожденные (один раздел пуст), имеют одинаковое значение.

После того, как они были разделены, карты объединяются таким образом, что карты поддерживают свой относительный порядок в пределах раздела, членом которого они являются . Например, если карта A находится перед картой B в колоде, а карты A и B находятся в одном и том же разделе, карта A должна быть перед картой B в конечном результате, даже если количество карт между ними увеличилось. Если A и B находятся в разных разделах, они могут быть в любом порядке, независимо от их начального порядка, в конечном результате.

Каждый случай перемешивания может быть рассмотрен как перестановка оригинальной колоды карт. Например перестановка

1,2,3 -> 1,3,2

это риффл шаффл. Если вы разделите колоду так

1, 2 | 3

мы видим, что каждая карта 1,3,2имеет одинаковый относительный порядок по отношению к любой другой карте в своем разделе. 2все еще после 1.

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

1,2,3 -> 3,2,1

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

1, 2 | 3
1 | 2, 3 

есть пара карт, которые не поддерживают свои относительные порядки. В первом разделе 1и 2измените их порядок, а во втором разделе 2и 3измените их порядок.

задача

Учитывая перестановку с помощью любого разумного метода, определите, представляет ли она действительный случайный случай. Вы должны вывести два различных значения констант: одно для «Да, это случайное перемешивание» и одно для «Нет, это не случайное перемешивание».

Это поэтому ответы будут оцениваться в байтах, причем меньше байтов будет лучше.

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

1,3,2 -> True
3,2,1 -> False
3,1,2,4 -> True
2,3,4,1 -> True
4,3,2,1 -> False
1,2,3,4,5 -> True
1,2,5,4,3 -> False
5,1,4,2,3 -> False
3,1,4,2,5 -> True
2,3,6,1,4,5 -> False
Мастер пшеницы
источник
1
Может ли результат быть противоречивым, но правдивым / ложным на нашем языке? Как (Python, где среди целых чисел только 0 - ложь) 0для ложных, но любое целое число [1, +∞)для правдивых?
Мистер Кскодер
1
@ Mr.Xcoder Мне не нравятся истинные / ложные значения, потому что их довольно сложно определить хорошо. Ответы должны придерживаться текущих правил.
Пшеничный волшебник
Похожий тест: [3,1,4,2,5].
Орджан Йохансен
9
К сожалению об этом, но: [2,3,6,1,4,5].
Орджан Йохансен,
1
Можем ли мы принять перестановки [0, ..., n-1]вместо [1, ..., n]ввода?
Деннис

Ответы:

8

JavaScript (ES6), 47 байт

Принимает ввод как массив целых чисел. Возвращает логическое значение.

([x,...a],y)=>a.every(z=>z+~x?y?z==++y:y=z:++x)

Контрольные примеры

Как?

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

Правила вызова указать , что мы дали перестановку из [1 ... N] . Поэтому нам не нужно дополнительно проверять, что отсортированное объединение этих последовательностей действительно приводит к такому диапазону.

Мы используем счетчик x, инициализированный в A [0], и счетчик y, изначально не определенный.

Для каждой записи z в A , начиная со 2-й:

  • Мы проверяем, равен ли z x + 1 или y + 1 . Если да, мы увеличиваем соответствующий счетчик.
  • Иначе: если y все еще не определено, мы инициализируем это к z .
  • Иначе: мы проваливаем тест.
Arnauld
источник
6

Haskell , 41 байт

n%h=n+0^(n-h)^2
f l=elem(foldl(%)0$l++l)l

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

Проверяет, содержит ли составленный список список 0..n-1в порядке подпоследовательности.

XNOR
источник
5

Haskell , 43 байта

sпринимает список целых чисел, как в примерах OP, и возвращает a Bool.

s p=or[f(<x)p++f(>=x)p<[1..]|x<-p]
f=filter

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

Как это устроено

  • Понимание списка проверяет каждый элемент xпо pочереди и проверяет, может ли он быть первым элементом второго раздела шаффла. Затем orвозвращает, Trueесли какие-либо проверки были True.
  • Понимание делает это путем разбиения (с filter) pна элементы, меньшие и большие (или равные) x, конкатенации и проверки, является ли результирующий список [1..length p], то есть элементы в порядке.
  • Проверка того, составлен ли результирующий список, проверяется, [1..length p]строго ли результат меньше бесконечного списка [1..] == [1,2,3,etc.], что дает тот же результат для любой перестановки.
Орджан Йохансен
источник
5

Желе , 13 6 байт

ỤIṢḊRẠ

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

Альтернативная версия, задание постдаты, 5 байт

Ụ>ƝSỊ

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

Как это устроено

ỤIṢḊRẠ  Main link. Argument: A (permutation of [1, ..., n])

Ụ       Grade up; sort the indices of A by their respective values.
        For shuffles, the result is the concatenation of up to two increasing
        sequences of indices.
 I      Compute the forward differences.
        In a shuffle, only one difference may be negative.
  Ṣ     Sort the differences.
   Ḋ    Dequeue; remove the first (smallest) difference.
    R   Range; map each k to [1, ..., k].
        This yields an empty array for non-positive values of k.
     Ạ  All; check if all resulting ranges are non-empty.
Деннис
источник
4

Брахилог , 9 байт

o~cĊ⟨⊆⊇⟩?

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

Предикат завершается успешно, если входные данные представляют собой случайное перемешивание, и дает сбой, если это не так, что означает, среди прочего, что, если предикат будет выполнен как целая программа, будет напечатан успех и произойдет true.сбой false.. Ввод принимается как список любых видов элементов и интерпретирует его как представление перестановки самого отсортированного.

   Ċ         Some length-two list
 ~c          which concatenated
o            is the input sorted
    ⟨        satisfies the condition that its first element
     ⊆       is an ordered not-necessarily-contiguous sublist
        ?    of the input
      ⊇      which is an ordered superlist of
       ⟩     the list's second element.

Я чувствую, что в ⊆ᵐчетырехбайтовой конструкции типа «сэндвич» должно работать нечто, в духе чего ⟨⊆⊇⟩.

Несвязанная строка
источник
1
Я думаю, что вы первый, кто использовал бутерброд в ответе PPCG (и это красивый симметричный ответ :))
Fatalize
2

Рубин , 35 байт

->l{l.any?{|a|l&[*1..a]|l==l.sort}}

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

Как?

  • l & [*1..a] | lприменяет пересечение, а затем объединение: сначала получают элементы, lкоторые есть, <=aа затем добавляют оставшиеся элементы lбез изменения порядка. Если a - это число, которое мы ищем, то эта операция аналогична сортировке l.
гигабайт
источник
2

Pyth, 5 байт

}SQy+

Тестирование

}SQy+

    +QQ  concatenated two copies of the (implicit) input
   y     all subsequences of it
}        contain an element equaling
 SQ      the input list sorted 

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

Благодаря Эрику Outgolfer за 1 байт, который лучше использует неявный ввод +QQ, чем *2Q.

XNOR
источник
5 байт: }SQy+. Это расширяется до }SQy+QQ.
Эрик Outgolfer
@EriktheOutgolfer Хороший, спасибо.
xnor
1

Pyth , 9 байт

!t-.+xLQS

Тестирование.

Сохранено 3 байта благодаря isaacg .

Pyth , 14 байт

}SQm.nS.Tcd2./

Попробуй это здесь! или Проверьте все контрольные примеры.

Выходы Trueи Falseдля riffle-shuffle и non-riffle-shuffle соответственно.

Как?

} SQm.nS.Tcd2./ ~ Полная программа. Считывает ввод из STDIN и выводит в STDOUT.

            ./ ~ Вернуть все деления входа в непересекающиеся подстроки (раздел).
   m ~ Отобразить вышеуказанное, используя переменную d.
         cd2 ~ Измельчить d в двухэлементные списки.
       .T ~ Оправдано транспонировать, игнорируя пропуски.
      Сортировка (лексикографически).
    .n ~ Deep-flatten.
} ~ Проверьте, содержит ли вышесказанное ...
 SQ ~ отсортированный ввод.
Мистер Xcoder
источник
Кроме того, <#0можно заменить еще -на 2 байта.
Исаак
@isaacg Ах да FACEPALM спасибо. Ред. Ред.
г-н Xcoder
0

Perl, 28 байт

Включает +1в себя дляa

Ввод на STDIN, 1 на основе

perl -aE '$.+=$_==$.for@F,@F;say$.>@F' <<< "3 1 2 4"

Использует алгоритм xnor

Тон Хоспел
источник