19
\$\begingroup\$

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

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.

\$\endgroup\$
6
  • 4
    \$\begingroup\$ It would be simpler to talk of “most frequent elements” IMO: subsequences are used when the order is important, but here, every permutation of the input has the same set of allowed correct outputs. \$\endgroup\$ May 1, 2017 at 7:50
  • \$\begingroup\$ @ShreevatsaR Sorry, I've edited the question. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 7:51
  • \$\begingroup\$ Does a flat list work for output? E.g. 1 2 3, 1 1 2 2, 1 1 2 2, 1 1 1? \$\endgroup\$ May 1, 2017 at 14:26
  • \$\begingroup\$ @ConorO'Brien saying yes would invalidate most of the answers here... \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:29
  • \$\begingroup\$ @LeakyNun As in, is it an acceptable alternative? \$\endgroup\$ May 1, 2017 at 14:30

26 Answers 26

8
\$\begingroup\$

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.
\$\endgroup\$
2
  • \$\begingroup\$ I thought Jelly doesn't have a maximum quick... \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 3:31
  • \$\begingroup\$ It's technically a maximal quick, but yes, it does. \$\endgroup\$
    – Dennis
    May 1, 2017 at 3:31
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Oh hey, another Brachylogist. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 6:51
  • 1
    \$\begingroup\$ Somehow you and me must have missed each other repeatedly in the Brachylog chat; I've been using it for months, and was surprised to learn that apparently someone else besides Fatalize was too. \$\endgroup\$
    – user62131
    May 1, 2017 at 6:53
5
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ 3 bytes off \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 3:50
  • \$\begingroup\$ Consider updating your explanation \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 4:24
3
\$\begingroup\$

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!

\$\endgroup\$
10
  • \$\begingroup\$ Would like to see an answer in Python 3 :p \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 5:32
  • 1
    \$\begingroup\$ Porting this one is trivial: just replace print with return. \$\endgroup\$
    – Dennis
    May 1, 2017 at 5:33
  • \$\begingroup\$ Oh, I thought Python 3 doesn't have map. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 5:35
  • \$\begingroup\$ It's a bit different in 3 (returns a generator and truncates longer iterables if there are more than two arguments), but it's there. \$\endgroup\$
    – Dennis
    May 1, 2017 at 5:36
  • \$\begingroup\$ I thought Python had a built-in for this \$\endgroup\$
    – Beta Decay
    May 1, 2017 at 6:07
2
\$\begingroup\$

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}}      *)
\$\endgroup\$
3
  • 1
    \$\begingroup\$ You can save 5 bytes with Gather@#~MaximalBy~Length&. \$\endgroup\$ May 1, 2017 at 5:59
  • 2
    \$\begingroup\$ @GregMartin and then MaximalBy[Length]@*Gather. \$\endgroup\$ May 1, 2017 at 14:20
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:38
2
\$\begingroup\$

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.

\$\endgroup\$
0
2
\$\begingroup\$

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
\$\endgroup\$
0
2
\$\begingroup\$

K (ngn/k), 18 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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]]
\$\endgroup\$
2
  • \$\begingroup\$ itertools is never the shortest :p \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 5:31
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:40
1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:39
  • \$\begingroup\$ @LeakyNun Thanks for letting me know \$\endgroup\$
    – Luis Mendo
    May 1, 2017 at 17:55
  • \$\begingroup\$ It is my responsibility. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 17:55
1
\$\begingroup\$

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(...)).

\$\endgroup\$
1
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:39
1
\$\begingroup\$

05AB1E, 8 5 bytes

Outputs a flat list in order

.M¹Ã{

Uses the 05AB1E encoding. Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:39
  • \$\begingroup\$ @LeakyNun Thanks for the notification :) \$\endgroup\$
    – Adnan
    May 1, 2017 at 14:49
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Perl 5, 58 bytes

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

Husk, 5 bytes

→kLk=

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Japt -h, 4 bytes

ü üÊ

Try it

ü üÊ     :Implicit input of array
ü        :Group & sort by value
  üÊ     :Group & sort by length
         :Implicit output of last element
\$\endgroup\$
1
  • \$\begingroup\$ Hey, is there a way to wait for a certain amount of time, or run a block until condition in Japt? \$\endgroup\$
    – Razetime
    Nov 17, 2020 at 11:54
1
\$\begingroup\$

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)

enter image description here

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:40
0
\$\begingroup\$

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));
\$\endgroup\$
1
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:40
0
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:39
  • \$\begingroup\$ @LeakyNun Thanks for the notification. \$\endgroup\$
    – Arnauld
    May 1, 2017 at 15:43
0
\$\begingroup\$

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]
                      }
\$\endgroup\$
2
  • \$\begingroup\$ This only works if the smallest integer belongs to the most common elements. You'll need $W= instead of the first 0=. \$\endgroup\$ May 1, 2017 at 14:22
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$
    – Leaky Nun
    May 1, 2017 at 14:39
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Ruby, 57 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.