Group a List by Frequency

Question

Given a list of integers, group the elements which occur most first, then group the next most and so on until each unique element in the list has been grouped once.

---

Examples:

Input: [1,2,3]

Output: [[1,2,3]]

---

Input: [1,1,1,2,2,3,3,4,5,6]

Output: [[1],[2,3],[4,5,6]]

---

Input: [1,1,1,4,5,6,6,6,7,7,8,8,8,8,8,8,8,9,5,6,5,6,5,6,5,6,-56]

Output: [[6, 8],[5],[1],[7],[9,4,-56]]

---

Input: []

Output: []

---

Input: (empty input)

Output: ERROR/Undefined/Doesn't matter

---

Rules

• Groupings must go from maximal frequency to minimal frequency.
• Internal order of the groupings are arbitrary (E.G. example 3 could have [8,6] instead).
• This is code-golf, lowest byte-count wins.

Related

• Sort the distinct elements of a list in descending order by frequency

Answer 1

Mathematica, 43 bytes

Union/@SortBy[l=#,f=-l~Count~#&]~SplitBy~f&

Try it online! (Using Mathics.)

Alternatively:

SortBy[Union[l=#],f=-l~Count~#&]~SplitBy~f&

Answer 2

Pyth, 8 7 bytes

_{M.g/Q

Try it online!

1 byte thanks to FryAmTheEggman.

Answer 3

Python 2, 145 141 bytes

import collections as c,itertools as i;o=lambda n:lambda l:l[n]
print[map(o(0),g)for _,g in i.groupby(c.Counter(input()).most_common(),o(1))]

Try it online!

This is my first submission after years of reading.

It basically it puts all the elements into a Counter (dictionary of how many of each element in the list) and .most_common() puts the items in decending frequency order. After that, it's just a matter of formatting the items into the right list.

Saved 4 bytes thanks to ovs.

Answer 4

JavaScript (ES6), 95 101 bytes

a=>a.map(x=>(o[a.map(y=>n+=x!=y,n=0)|n]=o[n]||[])[x*x+(x>0)]=x,o=[])&&(F=o=>o.filter(a=>a))(o).map(F)

How?

For each element x of the input array a, we compute the number n of elements of a that are different from x:

a.map(y => n += x != y, n = 0) | n

We use the indices n and x to fill the array o:

(o[n] = o[n] || [])[x * x + (x > 0)] = x

Edit: Because JS doesn't support negative array indices, we need the formula x * x + (x > 0) to force positive indices.

This gives us an array of arrays containing the unique elements of the original list, grouped by frequency and ordered from most frequent to least frequent.

However, both the outer array and the inner arrays potentially have many empty slots that we want to filter out. We do this with the function F, applied to o and each of its elements:

F = o => o.filter(a => a)

Test cases

let f =

a=>a.map(x=>(o[a.map(y=>n+=x!=y,n=0)|n]=o[n]||[])[x*x+(x>0)]=x,o=[])&&(F=o=>o.filter(a=>a))(o).map(F)

console.log(JSON.stringify(f([1,2,3]))) // [[1,2,3]]
console.log(JSON.stringify(f([1,1,1,2,2,3,3,4,5,6]))) // [[1],[2,3],[4,5,6]]
console.log(JSON.stringify(f([1,1,1,4,5,6,6,6,7,7,8,8,8,8,8,8,8,9,5,6,5,6,5,6,5,6,-56]))) // [[6, 8],[5],[1],[7],[9,4,-56]]
console.log(JSON.stringify(f([]))) // []

Answer 5

PHP, 85 bytes

<?$r=[];foreach(array_count_values($_GET)as$k=>$v)$r[$v][]=$k;krsort($r);print_r($r);

Try it online!

Answer 6

Jelly, 9 8 bytes

QɓċЀĠṚị

Try it online!

Answer 7

Clojure, 74 bytes

#(for[[_ g](sort-by(comp - key)(group-by val(frequencies %)))](map key g))

Looks quite verbose :/

Answer 8

Perl 6, 43 bytes

*.Bag.classify(-*.value).sort».value».key

Test it

Expanded:

*                   # WhateverCode lambda (this is the input)
                    # [1,1,1,2,2,3,3,4,5,6]

.Bag                # turn into a Bag
                    # (1=>3,5=>1,4=>1,3=>2,6=>1,2=>2).Bag

.classify(-*.value) # classify by how many times each was seen
                    # {-2=>[3=>2,2=>2],-3=>[1=>3],-1=>[5=>1,4=>1,6=>1]}

.sort\              # sort (this is why the above is negative)
                    # {-3=>[1=>3],-2=>[3=>2,2=>2],-1=>[5=>1,4=>1,6=>1]}

».value\            # throw out the classification
                    # ([1=>3],[3=>2,2=>2],[5=>1,4=>1,6=>1])

».key               # throw out the counts
                    # ([1],[3,2],[5,4,6])

Answer 9

Bash + GNU utilities, 71 61

sort|uniq -c|sort -nr|awk '{printf$1-a?"\n%d":",%d",$2;a=$1}'

Input as a newline-delimited list. Output as a newline-delimited list of comma-separated values.

Try it online.

Answer 10

MATL, 9 bytes

9B#uw3XQP

Input is a column vector, using ; as separator.

Try it online!

Explanation

9B#u   % Call 'unique' function with first and fourth outputs: unique entries and
       % number of occurrences
w      % Swap
3XQ    % Call 'accumarray' with anonymous function @(x){sort(x).'}. The output is
       % a cell array with the elements of the input grouped by their frequency.
       % Cells are sorted by increasing frequency. Some cells may be empty, but
       % those won't be displayed
P      % Flip cell array, so that groups with higher frequency appear first.
       % Implicitly display

Answer 11

k, 22 bytes

{x@!x}{(>x)@=x@>x}#:'=

Try it online.

^{(AW's k seems to require an extra @ before the #, but oK does not.)}

Explanation:

                     = /group identical numbers in a map/dict
                  #:'  /get number of times each number is repeated
                       /this is almost the answer, but without the inner lists
      {      x@>x}     /order "number of times" greatest to least
            =          /group them (to make the smaller groups)
       (>x)@           /get the actual numbers into place
{x@!x}                 /get values of the map/dict it's in

Answer 12

Brachylog, 10 bytes

ọtᵒ¹tᵍhᵐ²|

Try it online!

Explanation

Example input: [2,1,1,3]

ọ            Occurences:            [[2,1],[1,2],[3,1]]
 tᵒ¹         Order desc. by tail:   [[1,2],[3,1],[2,1]]
    tᵍ       Group by tail:         [[[1,2]],[[3,1],[2,1]]]
      hᵐ²    Map twice head:        [[1],[3,2]]

         |   Else (Input = [])      Input = Output

Answer 13

Mathematica, 79 bytes

Table[#&@@@f[[i]],{i,Length[f=GatherBy[Sort[Tally@#,#1[[2]]>#2[[2]]&],Last]]}]&

input

[{1, 1, 1, 4, 5, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 8, 9, 5, 6, 5, 6, 5, 6, 5, 6, -56}]

output

{{8, 6}, {5}, {1}, {7}, {-56, 9, 4}}

Answer 14

R, 84 77 bytes

-7 bytes thanks to mb7744

unique(lapply(x<-sort(table(scan()),T),function(y)as.double(names(x[x==y]))))

Reads from stdin; returns a list with subvectors of integers in increasing order. If we could return strings instead of ints, then I could drop 11 bytes (removing the call to as.double), but that's about it. R's table function does the heavy lifting here, counting the occurrences of each member of its input; then it aggregates them by count (names). Of course, that's a string, so we have to coerce it to an integer/double.

Try it online!

Answer 15

JavaScript (ES6), 100 98 96 93 bytes

Saved 2 bytes thanks to @Neil (plus he fixed an edge-case bug in my code). Saved 3 more bytes thanks to @TomasLangkaas.

a=>a.sort().map((_,n)=>a.filter((v,i)=>i-a.indexOf(v)==n&v!=a[i+1])).filter(a=>a+a).reverse()

Test cases

f=
a=>a.sort().map((_,n)=>a.filter((v,i)=>i-a.indexOf(v)==n&v!=a[i+1])).filter(a=>a+a).reverse()

console.log(JSON.stringify(f([1,2,3])))
console.log(JSON.stringify(f([1,1,1,2,2,3,3,4,5,6])))
console.log(JSON.stringify(f([1,1,1,4,5,6,6,6,7,7,8,8,8,8,8,8,8,9,5,6,5,6,5,6,5,6,-56])))
console.log(JSON.stringify(f([])))

Answer 16

Husk, ⁶ 5 bytes

↔k#¹u

Try it online!

-1 byte from Leo.

Explanation

↔k#¹u 
    u uniquify the input 
 k#¹  key on frequency in input
↔     reverse

Answer 17

05AB1E, 8 bytes

ÙΣ¢}R.γ¢

Try it online or verify all test cases.

Explanation:

Ù       # Uniquify the (implicit) input-list
 Σ      # Sort this uniquified list by:
  ¢     #  Get its count in the (implicit) input-list
 }R     # After the ascending sort: reverse it to make it descending
   .γ   # Then adjacently group each value by:
     ¢  #  Its count in the (implicit) input-list
        # (after which the result is output implicitly)

The .γ could have been .¡ for the same result. .¡ is the group-by builtin, and .γ is the adjacently group-by builtin. But since we use a sort first, the result ends up buying the same.
Unfortunately, 05AB1E lacks a sort & group-by as single builtin, so we'll have to do it in two steps instead (like most existing answers tbh).

Answer 18

Factor, 63 bytes

[ histogram unzip swap zip expand-keys-push-at values reverse ]

Explanation

                     ! { 1 1 1 2 2 3 3 4 5 6 }
histogram            ! H{ { 1 3 } { 2 2 } { 3 2 } { 4 1 } { 5 1 } { 6 1 } }
unzip                ! { 1 2 3 4 5 6 } { 3 2 2 1 1 1 }
swap                 ! { 3 2 2 1 1 1 } { 1 2 3 4 5 6 }
zip                  ! { { 3 1 } { 2 2 } { 2 3 } { 1 4 } { 1 5 } { 1 6 }
expand-keys-push-at  ! H{ { 1 V{ 4 5 6 } } { 2 V{ 2 3 } } { 3 V{ 1 } } }
values               ! { V{ 4 5 6 } V{ 2 3 } V{ 1 } }
reverse              ! { V{ 1 } V{ 2 3 } V{ 4 5 6 } }

Answer 19

Python 3, 85 bytes

def f(l):
 r=[[]for _ in l]
 for x in{*l}:r[-l.count(x)]+=x,
 return[*filter(bool,r)]

Try it online!

-12 thanks to tips from @ovs!

Answer 20

V, 60, 54 bytes

Úòͨ¼¾©î±/± ±òHòø 
pkJjòú!
Ǩ^ƒ ©î±/o
Îf ld|;D
òV{Jk

Try it online!

Hexdump:

00000000: daf2 cda8 bc81 bea9 eeb1 2fb1 20b1 f248  ........../. ..H
00000010: f2f8 200a 706b 4a6a f2fa 210a c7a8 5e83  .. .pkJj..!...^.
00000020: 20a9 81ee b12f 6f0a ce66 206c 647c 3b44   ..../o..f ld|;D
00000030: 0af2 567b 4a6b                           ..V{Jk

As much as I love V, I'm pretty sure this is the worst possible language for the task. Especially considering it has no support for lists, and basically no support for numbers. Just string manipulation.

Answer 21

Ruby, 62 bytes

->a{a.group_by{|e|a.count(e)}.sort_by{|x,_|-x}.map{|_,i|i|[]}}

Try it online!

There has got to be a shorter way to do this.

Answer 22

C#, 119 bytes

Just a quick stab at it:

using System.Linq;
a=>a.GroupBy(x=>x)
    .GroupBy(x=>x.Count(),x=>x.Key)
    .OrderBy(x=>-x.Key)
    .Select(x=>x.ToArray())
    .ToArray()

Answer 23

R, 66 bytes

(l=lapply)(l(split(x<-table(scan()),factor(-x)),names),as.integer)

Try it online!

If in the output the integers may be in string format, can drop to 48 bytes (as mentioned in @Giuseppe's answer).

---

Ungolfed:

input <- scan(); # read input
x <- table(input); # count how many times each integer appears, in a named vector
y <- split(x, factor(-x)) # split the count into lists in increasing order
z <- lapply(y, names) # access the the original values which are still
                      # attached via the names
lapply(z, as.integer) # convert the names back to integers

Answer 24

PowerShell, 77, 70 bytes

($a=$args)|group{($a-eq$_).count}|sort n* -Des|%{,($_.group|sort -u)}

NB: To see that these results are correctly grouped (since visually there's no deliniation between the contents of each array), you may wish to append | write-host to the end of the above line.

Acknowledgements

Thanks to:

• TessellatingHeckler for saving 7 bytes by massively refactoring / rewriting to a way more golfed approach.

---

Previous

77 bytes

param($x)$x|group|sort count -desc|group count|%{,($_.group|%{$_.group[0]})}

Answer 25

Perl 5 -pa, 89 bytes

map$k{$_}++,@F;$_="@{[sort{$k{$b}-$k{$a}}keys%k]}";s/\S+ /$&.'| 'x($k{1*$&}!=$k{1*$'})/ge

Try it online!

Answer 26

Groovy, 71 bytes

{a->a.groupBy{a.count(it)}.sort{-it.key}.values().collect{it.unique()}}

I actually just learned about groupBy after creating this. I didn't know collect wasn't my only choice.

---

{
    a->                 // [1,2,1,2,3,3,3,6,5,4]
    a.groupBy{      
        a.count(it)     // [2:[1,2,1,2],3:[3,3,3],1:[6,5,4]]
    }.sort{             
        -it.key         // [3:[3,3,3],2:[1,2,1,2],1:[6,5,4]]
    }.values().collect{ // [[3,3,3],[1,2,1,2],[6,5,4]]
        it.unique()
    }                   // [[3],[1,2],[6,5,4]]
}