Определения

• Подпоследовательность не может быть смежной, например, [1, 1, 1]является подпоследовательностью [1, 2, 1, 2, 1].
• Равная подпоследовательность - это подпоследовательность, в которой каждый элемент равен.
• Самая длинная равная подпоследовательность может не быть уникальной, например, [1, 1]и [2, 2]обе являются самыми длинными равными подпоследовательностями [2, 1, 1, 2].

вход

Непустой список натуральных чисел в одном из следующих форматов:

• как нативная реализация массива натуральных чисел в вашем языке
• как строка разделенных символом новой строки целых чисел в десятичной дроби
• как строка разделенных символом новой строки целых чисел в унарном
• любые другие разумные форматы

Выход

Все самые длинные равные подпоследовательности в любом порядке в одном из следующих форматов:

• как двумерный вложенный массив на вашем языке (если вход является массивом)
• как сплющенный массив с равными элементами, являющимися смежными
• любой другой разумный формат

счет

Хотя мы ищем что-то длинное, используемый код должен быть как можно более коротким с точки зрения количества байтов, поскольку это код-гольф

Testcases

Входы:

[1, 2, 3]
[1, 2, 2, 1]
[1, 2, 3, 2, 1]
[1, 2, 1, 2, 3, 4, 1]

Выходы:

[[1], [2], [3]]
[[1, 1], [2, 2]]
[[1, 1], [2, 2]]
[[1, 1, 1]]

Обратите внимание, что для выходов выше, любой заказ действителен.

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

Желе , 5 байт

ĠLÐṀị

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

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

ĠLÐṀị  Main link. Argument: A (array)

Ġ      Group; partition the indices of A by their corresponding values.
 LÐṀ   Select all index arrays with maximal length.
    ị  Unindex; retrieve the items of A at the specified indices.

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

⊇ᶠ=ˢlᵍh

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

объяснение

⊇ᶠ=ˢlᵍh
⊇ᶠ        Find all subsequences
  =ˢ      Keeping only those for which all elements are equal
    lᵍ    Group by length
      h   Take the first group

⊇Естественный порядок сначала генерирует самые длинные подпоследовательности, так что именно они попадают в первую группу.

Pyth, 5 байт

S.M/Q

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

Объяснение:

Это неявно S.M/QZQ. .Mявляется максимальной функцией, поэтому .M/QZQвыбирает все элементы, в которых значение /QZ, подсчитывающее количество вхождений элемента на входе, является максимальным. Sзатем сортирует список так, чтобы идентичные элементы были смежными.

Баш, 66 байт

sort|uniq -c|sort -rn|awk 'NR==1{a=$1}$1==a{for(i=a;i--;)print$2}'

Кажется, это должно быть короче, но я не могу понять, как.

sort                  # sort the input
|uniq -c              # group runs of identical lines and prefix with count
|sort -rn             # sort by count, with largest at top
|awk '                # pipe to awk...
  NR==1{a=$1}         # on the first line, set the variable "a" to field 1
  $1==a{              # on any line, if first field is a (max count)...
    for(i=a;i--;)     # a times...
    print$2           # print the second field
  }
'

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

Спасибо Leaky Nun за 3 байта!

Python 2 , 68 63 байта

lambda x:sorted(n for n in x if x.count(n)/max(map(x.count,x)))

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

Mathematica, 42 31 25 байт

Спасибо @GregMartin за 5 байтов и @MartinEnder за еще один байт!

MaximalBy[Length]@*Gather

объяснение

MaximalBy[Length]@*Gather  (*                       {1, 2, 3, 2, 1}       *)
                   Gather  (* Gather same numbers:  {{1, 1}, {2, 2}, {3}} *)
                 @*        (* Function composition                        *)
MaximalBy[Length]          (* Find longest:         {{1, 1}, {2, 2}}      *)

Stacked , 55 52 43 байта

sorted rle toarr:[1#]map MAX@K[1#K=]YES rld

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

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

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

;╗⌠;╜ck⌡M;♂NM╗⌠N╜=⌡░♂FS

Попробуйте онлайн или выполните все контрольные примеры !

Спасибо Leaky Nun за указание на однобайтовое улучшение, которое действительно должно было быть для меня очевидным

-3 байта из расслабленного выходного формата

Объяснение:

;╗⌠;╜ck⌡M;♂NM╗⌠N╜=⌡░♂FS
;╗                        save a copy of the input to register 0
  ⌠;╜ck⌡M                 for each value in the input list:
   ;                        make a copy on the stack
    ╜c                      count the occurrences in the input list (from register 0)
      k                     make a list: [value, count]
         ;♂N             make a copy, take last value of each list in the 2D list
            M╗           store the maximum count in register 0
              ⌠N╜=⌡░     filter the other copy of the list of [value, count] lists:
               N╜=         take items where the count equals the maximum count
                    ♂FS  take first items (values) and sort them

Python 2, 138 байт

lambda l:[[x[0]]*x[1] for x in next(__import__('itertools').groupby(__import__('collections').Counter(l).most_common(),lambda x:x[1]))[1]]

MATL , 10 байт

3#XMg1bX"&

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

объяснение

Похоже на мой октавский ответ Рассмотрим ввод [10, 20, 30, 20, 10]в качестве примера.

3#XM   % Three-output version of mode function. Gives the first mode, the
       % number of repetitions, and a cell array with all modes
       % STACK: 10, 2, {10; 20}
g      % Convert from cell array to matrix
       % STACK: 10, 2, [10; 20]
1      % Push 1
       % STACK: 10, 2, [10; 20], 1
b      % Bubble up in the stack
       % STACK: 10, [10; 20], 1, 2
X"     % Repeat those number of times vertically and horizontally
       % STACK: 10, [10, 10; 20, 20]
&      % Specify that implicit display will show only the top of the stack.
       % Since this is singleton cell array that contains a matrix, that 
       % matrix is directly displayed

октава , 47 байт

[~,b,c]=mode(input(0));disp([repmat(c,1,b){:}])

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

объяснение

Второй и третий выходы mode(полученные как [~,b,c]=mode(...)) соответственно дают количество повторений ( b) и массив ячеек столбца ( c) наиболее повторяющихся элементов в input ( input(0)). Затем массив ячеек cповторяется по горизонтали btimes ( repmat(c,1,b)), преобразуется в разделенный запятыми список ( {:}) и связывается по горизонтали ( [...]), чтобы получить числовую матрицу, которая отображается ( disp(...)).

05AB1E , 8 5 байт

Выводит плоский список в порядке

.M¹Ã{

Использует кодировку 05AB1E . Попробуйте онлайн!

CJam , 22 байта

{$e`z~\__:e>f=.*\]ze~}

Это анонимный блок (функция), который берет ввод с вершины стека и перераспределяет его с выводом. На выходе получается сплющенный массив с равными элементами, являющимися смежными.

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

объяснение

Рассмотрим ввод [10 20 30 20 10 ]в качестве примера.

{      e# Begin block
       e#   STACK: [10 20 30 20 10]
  $    e#   Sort
       e#   STACK: [10 10 20 20 30]
  e`   e#   Run-length encoding
       e#   STACK: [[2 10] [2 20] [1 30]]
  z    e#   Zip
       e#   STACK: [[2 2 1] [10 20 30]]
  ~    e#   Dump array contents onto the stack
       e#   STACK: [2 2 1] [10 20 30]
  \    e#   Swap
       e#   STACK: [10 20 30] [2 2 1]
  __   e#   Duplicate twice
       e#   STACK: [10 20 30] [2 2 1] [2 2 1] [2 2 1]
  :e>  e#   Fold maximum over array. Gives the maximum of the array
       e#   STACK: [10 20 30] [2 2 1] [2 2 1] 2
  f=   e#   Map "is equal" with number (2) over the array ([2 2 1])
       e#   STACK: [10 20 30] [2 2 1] [1 1 0]
  .*   e#   Vectorized multiplication
       e#   STACK: [10 20 30] [2 2 0]
  \    e#   Swap
       e#   STACK: [2 2 0] [10 20 30]
  ]    e#   Pack into array
       e#   STACK: [[2 2 0] [10 20 30]]
  z    e#   Zip
       e#   STACK: [[2 10] [2 20] [0 30]]
  e~   e#   Run-length decoding
       e#   STACK: [10 10 20 20]
}      e# End block

Perl 5, 58 байт

sub{sort grep$x{$_}>$m,grep{$/=$x{$_}++;$m=$/if$m<$/;1}@_}

APL (Dyalog) , 22 байта

Требуется ⎕ML←3по умолчанию во многих системах.

Программа: s/⍨(⌈/=⊢)≢¨s←⊂⍨(⍋⊃¨⊂)⎕

⎕ получить числовой (оцененный) ввод

(… ) Молчаливая функция
 ⍋ индексов элементов по возрастанию,
 ⊃¨ выбираемых из
 ⊂ всего массива

⊂⍨ разделение путем разрезания при его увеличении

s← хранить как с

≢¨ подсчитать каждый

(… ) Молчаливая функция,
 ⌈/ максимум (подсчет)
 = равен
 ⊢ аргументу (подсчету)

s/⍨ Фильтр с тем , что

Функция: {s/⍨(⌈/=⊢)≢¨s←⊂⍨⍵[⍋⍵]}

{… } Анонимная функция, где аргумент⍵

⍵[⍋⍵] сортировка (освещенный индекс с индексами по возрастанию)

⊂⍨ разделение путем разрезания при его увеличении

s← хранить как с

≢¨ подсчитать каждый

(… ) Молчаливая функция,
 ⌈/ максимум (подсчет)
 = равен
 ⊢ аргументу (подсчету)

s/⍨ фильтр S с этим попробовать его в Интернете!

PHP, 69 байт

<?print_r(preg_grep("#".max($r=array_count_values($_GET))."#",$r));

Онлайн версия

Выходной формат

ключ = значение, значение = количество

Array
(
    [1] => 2
    [2] => 2
)

PHP, 96 байт

<?foreach($_GET as$v)$r[$m[]=count($l=preg_grep("#^{$v}$#",$_GET))][$v]=$l;print_r($r[max($m)]);

Онлайн версия

Выходной формат

1D ключ = значение

2D Key = позиция во входном массиве для каждого значения

Array
(
    [1] => Array
        (
            [0] => 1
            [4] => 1
        )

    [2] => Array
        (
            [1] => 2
            [3] => 2
        )

)

PHP, 97 байт

<?foreach($_GET as$v)$r[count($l=preg_grep("#^{$v}$#",$_GET))][$v]=$l;ksort($r);print_r(end($r));

JavaScript (ES6), 84 83 байта

Возвращает отсортированный плоский массив.

a=>a.sort().filter((_,i)=>b[i]==Math.min(...b),b=a.map(i=>a.filter(j=>i-j).length))

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

let f =

a=>a.sort().filter((_,i)=>b[i]==Math.min(...b),b=a.map(i=>a.filter(j=>i-j).length))

console.log(JSON.stringify(f([1, 2, 3])))
console.log(JSON.stringify(f([1, 2, 2, 1])))
console.log(JSON.stringify(f([1, 2, 3, 2, 1])))
console.log(JSON.stringify(f([1, 2, 1, 2, 3, 4, 1])))

CJam, 24 байта

{$e`_$W=0=\{0=1$=},e~\;}

Я хотел сделать это в 05ab1e, но я сдался: P

Это блок. Вход и выход - это массивы в стеке.

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

Объяснение:

{                      e# Stack:                | [1 2 3 2 1]
 $                     e# Sort:                 | [1 1 2 2 3]
  e`                   e# RLE encode:           | [[2 1] [2 2] [1 3]]
    _$W=               e# Copy elements:        | [[2 1] [2 2] [1 3]] [2 1]
       0=              e# First element:        | [[2 1] [2 2] [1 3]] 2
         \             e# Swap:                 | 2 [[2 1] [2 2] [1 3]]
          {0=1$=},     e# Filter where x[0]==2: | 2 [[2 1] [2 2]]
                  e~   e# RLE decode:           | 2 [1 1 2 2]
                    \; e# Delete back:          | [1 1 2 2]
                      }

Clojure, 65 байт

#(let[P partition-by C count](last(P C(sort-by C(P +(sort %))))))

Ungolfed:

(def f #(->> %
             (sort-by      identity)   ; sort so that identical values are one after another, same as sort
             (partition-by identity)   ; partition by identity (duh!)
             (sort-by      count)      ; sort by item count
             (partition-by count)      ; partition by item count
             last))                    ; get the last partition

C #, 145 байт

l=>{var t=Enumerable.Range(0,l.Max()+1).Select(i=>l.Count(a=>a==i));return t.Select((a,i)=>Enumerable.Repeat(i,a)).Where(d=>d.Count()==t.Max());}

Это должно быть возможно лучше, но я застрял.

объяснение

l =>                                                   //Takes the list
{                                                      //...
    var t = Enumerable.Range(0, l.Max() + 1)           //Makes a range till the count, so that the items together with their indices are double defined (i.e. the items are 0,1,2,3... and the indices are the same)
                      .Select(i =>                     //Takes the items
                          l.Count(a => a == i));       //And replaces them with the count of themselves in the list (so the item has the index with its old value and the count as it's actual value)
    return t.Select((a, i) =>                          //Then it takes this list and selects the items together with the indices
        Enumerable.Repeat(i, a))                       //Repeats them as often as they appeared in the list
                  .Where(d => d.Count() == t.Max());   //And just keeps those which appear the maximum amount of times
};                                                     //...

Возможно, совершенно другой подход был бы намного короче, поэтому задача C # все еще открыта :)

Рубин , 57 байт

->a{a.reject{|i|a.map{|j|a.count j}.max>a.count(i)}.sort}

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