Longest equal subsequences

Question

Definitions

• A subsequence may not be contiguous, e.g. [1, 1, 1] is a subsequence of [1, 2, 1, 2, 1].
• An equal subsequence is a subsequence in which every element is equal.
• The longest equal subsequence may not be unique, e.g. [1, 1] and [2, 2] are both longest equal subsequences of [2, 1, 1, 2].

Input

A non-empty list of positive integers in one of the format below:

• as the native implementation of an array of positive integers in your language
• as a string of newline-separated integers in decimal
• as a string of newline-separated integers in unary
• any other reasonable formats

Output

All of the longest equal subsequences in any order in one of the formats below:

• as a 2D nested array in your language (if the input is an array)
• as a flattened array with the equal elements being contiguous
• any other reasonable format

Scoring

Although we are looking for something long, the code used should be as short as possible in terms of number of bytes, since this is code-golf

Testcases

Inputs:

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

Outputs:

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

Note that for the outputs above, any order is valid.

A flattened array is also valid, as long as the equal elements are contiguous.

Answer 1

Jelly, 5 bytes

ĠLÐṀị

Try it online!

How it works

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

Answer 2

Brachylog, 7 bytes

⊇ᶠ=ˢlᵍh

Try it online!

Explanation

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

⊇'s natural order generates the longest subsequences first, so those are the ones that end up in the first group.

Answer 3

Pyth, 5 bytes

S.M/Q

Test suite

Explanation:

This is implicitly S.M/QZQ. .M is the maximal function, so .M/QZQ selects all elements where the value of /QZ, count the number of occurrences of the element in the input, is maximal. S then sorts the list so that identical elements are contiguous.

Answer 4

bash, 66 bytes

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

This seems like it should be way shorter, but I can't figure out how.

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

Try it online!

Thanks to Leaky Nun for 3 bytes!

Answer 5

Python 2, 68 63 bytes

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

Try it online!

Answer 6

Mathematica, 42 31 25 bytes

Thanks @GregMartin for 5 bytes and @MartinEnder for another byte!

MaximalBy[Length]@*Gather

Explanation

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}}      *)

Answer 7

Stacked, 55 52 43 bytes

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

Try it online!

Works by run-length encoding the input, sorting by occurrences, keeping occurances for which the number of occurrences is maximal, and run length decoding. Outputs through a flat list, as is acceptable by the challenge.

Answer 8

Actually, 23 bytes

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

Try it online, or run all test cases!

Thanks to Leaky Nun for pointing out a one-byte improvement that really should've been obvious to me

-3 bytes from relaxed output format

Explanation:

;╗⌠;╜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

Answer 9

K (ngn/k), 18 bytes

{x{b=|/b:#'x}#.=x}

Try it online!

Answer 10

Python 2, 138 bytes

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

Answer 11

MATL, 10 bytes

3#XMg1bX"&

Try it online!

Explanation

Similar to my Octave answer. Consider input [10, 20, 30, 20, 10] as an example.

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

Answer 12

Octave, 47 bytes

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

Try it online!

Explanation

The second and third outputs of mode (obtained as [~,b,c]=mode(...)) respectively give the number of repetitions (b) and a column cell array (c) of the most repeated elements in the input (input(0)) . The cell array c is then repeated horizontally b times (repmat(c,1,b)), converted to a comma-separated list ({:}) and contatenated horizontally ([...]) to give a numeric matrix, which is displayed (disp(...)).

Answer 13

05AB1E, 8 5 bytes

Outputs a flat list in order

.M¹Ã{

Uses the 05AB1E encoding. Try it online!

Answer 14

CJam, 22 bytes

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

This is an anonymous block (function) that takes the input from the top of the stack and repaces it with the output. The output is a flattened array withequal elements being contiguous.

Try it online!

Explanation

Consider input [10 20 30 20 10 ] as an example.

{      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

Answer 15

Perl 5, 58 bytes

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

Answer 16

Husk, 5 bytes

→kLk=

Try it online!

Answer 17

Japt -h, 4 bytes

ü üÊ

Try it

ü üÊ     :Implicit input of array
ü        :Group & sort by value
  üÊ     :Group & sort by length
         :Implicit output of last element

Answer 18

Nibbles, 5 bytes (10 nibbles)

/=~=~$$,$@

/=~=~$$,$@
   =~       # group
     $      # the input
      $     # by its own values,
 =~         # now group each of these groups
       ,$   # by their lengths
            # (group of longest groups comes last),
/           # fold over this list-of-lists from right
         @  # always returning the second argument
            # (so this fold just returns the last item,
            # which is the list of the longest groups
            # of values)

Answer 19

APL (Dyalog), 22 bytes

Requires ⎕ML←3 which is default on many systems.

Program: s/⍨(⌈/=⊢)≢¨s←⊂⍨(⍋⊃¨⊂)⎕

⎕ get numeric (evaluated) input

(…) tacit function
 ⍋ the indices of ascending items
 ⊃¨ each pick from
 ⊂ the entire array

⊂⍨ partition by cutting at its increases

s← store as s

≢¨ tally each

(…) tacit function
 ⌈/ the maximum (tally)
 = equals
 ⊢ the argument (the tallies)

s/⍨ filter s with that

Function: {s/⍨(⌈/=⊢)≢¨s←⊂⍨⍵[⍋⍵]}

{…} anonymous function where argument is ⍵

⍵[⍋⍵] sort (lit. index with indices of ascending items)

⊂⍨ partition by cutting at its increases

s← store as s

≢¨ tally each

(…) tacit function
 ⌈/ the maximum (tally)
 = equals
 ⊢ the argument (the tallies)

s/⍨ filter s with that Try it online!

Answer 20

PHP, 69 Bytes

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

Online Version

Output Format

key = value , value = count

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

PHP, 96 Bytes

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

Online Version

Output Format

1D Key= value

2D Key = position in the input array for each value

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

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

)

PHP, 97 Bytes

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

Answer 21

JavaScript (ES6), 84 83 bytes

Returns a sorted flattened array.

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

Test cases

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

Answer 22

CJam, 24 bytes

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

I wanted to do this in 05ab1e, but I gave up :P

This is a block. Input and output are arrays on the stack.

Try it online!

Explanation:

{                      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]
                      }

Answer 23

Clojure, 65 bytes

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

Answer 24

C#, 145 Bytes

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());}

This must be possible better as well, however I'm kind of stuck.

Explanation

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
};                                                     //...

Probably a totally different approach would be much shorter, so the C# challenge is still open :)

Answer 25

Ruby, 57 bytes

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

Try it online!

Answer 26

Factor + math.combinatorics, 46 bytes

[ all-subsets [ all-eq? ] filter all-longest ]

Try it online!

• all-subsets Get all the subsets of the input
• [ all-eq? ] filter Get the ones where all the elements are the same
• all-longest Get all the longest of these