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

Сегодня вас просят определить, является ли перестановка на самом деле случайным образом. Наше определение 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

JavaScript (ES6), 47 байт

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

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

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

let f =

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

;[
  [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
  [3,1,4,2,5  ],  // -> True
  [2,3,6,1,4,5]   // -> False
]
.forEach(a => console.log(JSON.stringify(a) + ' -> ' + f(a)))

Как?

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

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

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

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

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

Haskell , 41 байт

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

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

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

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.], что дает тот же результат для любой перестановки.

Желе , 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.

Python 2 , 39 байт

l=input()
n=0
for x in l*2:n+=n==x
l[n]

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

Принимает список с 0 индексами и выводит через код выхода.

Брахилог , 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.

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

Python 2 , 75 60 47 байт

спасибо Деннису за -13 байт

x={0}
for v in input():x=x-{v-1}|{v}
len(x)<3>q

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

Выход через код выхода.

Рубин , 35 байт

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

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

Как?

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

Чистый , 56 55 байт

import StdEnv
?l=any(\e=sortBy(\a b=a<e&&b>=e)l<[1..])l

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

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.

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 ~ отсортированный ввод.

Шелуха , 7 байт

±§#OoṖD

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

Perl, 28 байт

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

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

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

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

C (gcc) , 61 байт

a,b,B;f(int*A){for(a=b=B=1;*A;A++)a-*A?B*=*A>b,b=*A:++a;b=B;}

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