18
\$\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\$
  • 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\$ – ShreevatsaR May 1 '17 at 7:50
  • \$\begingroup\$ @ShreevatsaR Sorry, I've edited the question. \$\endgroup\$ – Leaky Nun May 1 '17 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\$ – Conor O'Brien May 1 '17 at 14:26
  • \$\begingroup\$ @ConorO'Brien saying yes would invalidate most of the answers here... \$\endgroup\$ – Leaky Nun May 1 '17 at 14:29
  • \$\begingroup\$ @LeakyNun As in, is it an acceptable alternative? \$\endgroup\$ – Conor O'Brien May 1 '17 at 14:30

21 Answers 21

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\$
  • \$\begingroup\$ I thought Jelly doesn't have a maximum quick... \$\endgroup\$ – Leaky Nun May 1 '17 at 3:31
  • \$\begingroup\$ It's technically a maximal quick, but yes, it does. \$\endgroup\$ – Dennis May 1 '17 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\$
  • 1
    \$\begingroup\$ Oh hey, another Brachylogist. \$\endgroup\$ – Leaky Nun May 1 '17 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 '17 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\$
  • \$\begingroup\$ 3 bytes off \$\endgroup\$ – Leaky Nun May 1 '17 at 3:50
  • \$\begingroup\$ Consider updating your explanation \$\endgroup\$ – Leaky Nun May 1 '17 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\$
  • \$\begingroup\$ Would like to see an answer in Python 3 :p \$\endgroup\$ – Leaky Nun May 1 '17 at 5:32
  • 1
    \$\begingroup\$ Porting this one is trivial: just replace print with return. \$\endgroup\$ – Dennis May 1 '17 at 5:33
  • \$\begingroup\$ Oh, I thought Python 3 doesn't have map. \$\endgroup\$ – Leaky Nun May 1 '17 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 '17 at 5:36
  • \$\begingroup\$ I thought Python had a built-in for this \$\endgroup\$ – Beta Decay May 1 '17 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\$
  • 1
    \$\begingroup\$ You can save 5 bytes with Gather@#~MaximalBy~Length&. \$\endgroup\$ – Greg Martin May 1 '17 at 5:59
  • 2
    \$\begingroup\$ @GregMartin and then MaximalBy[Length]@*Gather. \$\endgroup\$ – Martin Ender May 1 '17 at 14:20
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 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\$
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\$
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\$
  • \$\begingroup\$ itertools is never the shortest :p \$\endgroup\$ – Leaky Nun May 1 '17 at 5:31
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 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\$
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 at 14:39
  • \$\begingroup\$ @LeakyNun Thanks for letting me know \$\endgroup\$ – Luis Mendo May 1 '17 at 17:55
  • \$\begingroup\$ It is my responsibility. \$\endgroup\$ – Leaky Nun May 1 '17 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\$
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 at 14:39
1
\$\begingroup\$

05AB1E, 8 5 bytes

Outputs a flat list in order

.M¹Ã{

Uses the 05AB1E encoding. Try it online!

\$\endgroup\$
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 at 14:39
  • \$\begingroup\$ @LeakyNun Thanks for the notification :) \$\endgroup\$ – Adnan May 1 '17 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\$
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\$
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 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\$
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 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\$
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 at 14:39
  • \$\begingroup\$ @LeakyNun Thanks for the notification. \$\endgroup\$ – Arnauld May 1 '17 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\$
  • \$\begingroup\$ This only works if the smallest integer belongs to the most common elements. You'll need $W= instead of the first 0=. \$\endgroup\$ – Martin Ender May 1 '17 at 14:22
  • \$\begingroup\$ I have added another acceptable alternative which might help you golf off some bytes. \$\endgroup\$ – Leaky Nun May 1 '17 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\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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