29
\$\begingroup\$

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 , lowest byte-count wins.

Related

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Can the output be in string format? Ie. A list of lists, but each number represented by a character instead of an integer. \$\endgroup\$
    – mb7744
    Jun 15, 2017 at 0:13

26 Answers 26

7
\$\begingroup\$

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&
\$\endgroup\$
5
  • 6
    \$\begingroup\$ There's no built-in? \$\endgroup\$ Jun 13, 2017 at 16:22
  • \$\begingroup\$ Is GatherBy an option, not sure because I don't know the language. \$\endgroup\$ Jun 13, 2017 at 16:32
  • 1
    \$\begingroup\$ @carusocomputing It sorts the groups by the first occurrence of the elements in the original list, so I'd still have to sort the groups afterwards. By sorting the list first, I can save a byte with SplitBy (also the SortBy would actually be more complicated if I did GatherBy first). \$\endgroup\$ Jun 13, 2017 at 16:34
  • \$\begingroup\$ Interesting, so the "must be in order from maximal to minimal" messes that up? \$\endgroup\$ Jun 13, 2017 at 16:35
  • \$\begingroup\$ @carusocomputing Exactly. \$\endgroup\$ Jun 13, 2017 at 16:36
6
\$\begingroup\$

Pyth, 8 7 bytes

_{M.g/Q

Try it online!

1 byte thanks to FryAmTheEggman.

\$\endgroup\$
4
  • \$\begingroup\$ @DigitalTrauma you can't; it's in a lambda; the implicit variable there is k, which I have already omitted. \$\endgroup\$
    – Leaky Nun
    Jun 14, 2017 at 8:07
  • \$\begingroup\$ got it - thanks for the explanation! \$\endgroup\$ Jun 14, 2017 at 17:26
  • \$\begingroup\$ Congratulations. \$\endgroup\$ Aug 17, 2017 at 21:44
  • \$\begingroup\$ @MagicOctopusUrn thank you. \$\endgroup\$
    – Leaky Nun
    Aug 17, 2017 at 21:44
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • 5
    \$\begingroup\$ Welcome to PPCG :). Don't get as addicted as I did. \$\endgroup\$ Jun 13, 2017 at 20:04
  • \$\begingroup\$ Creating your own itemgetter function is 4 bytes shorter than importing it: o=lambda n:lambda l:l[n] \$\endgroup\$
    – ovs
    Jun 13, 2017 at 21:38
5
\$\begingroup\$

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([]))) // []

\$\endgroup\$
3
  • \$\begingroup\$ I think a Set saves you a byte: a=>a.map(e=>(r[n=0,a.map(f=>n+=e!=f),n]||(r[n]=new Set)).add(e),r=[])&&r.filter(s=>s).map(s=>[...s]). \$\endgroup\$
    – Neil
    Jun 14, 2017 at 20:58
  • \$\begingroup\$ @Neil This is quite different from my current approach. Maybe you should post it as a new answer? \$\endgroup\$
    – Arnauld
    Jun 14, 2017 at 22:29
  • \$\begingroup\$ I didn't think changing o[n] from an array to a set was that different, but I already golfed @RickHitchcock's answer anyway so there's not that much point. \$\endgroup\$
    – Neil
    Jun 14, 2017 at 23:39
3
\$\begingroup\$

PHP, 85 bytes

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

Try it online!

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

Jelly, 9 8 bytes

QɓċЀĠṚị

Try it online!

\$\endgroup\$
2
  • 5
    \$\begingroup\$ Did... Pyth... beat... Jelly? \$\endgroup\$
    – Leaky Nun
    Jun 13, 2017 at 16:06
  • 1
    \$\begingroup\$ Jelly doesn't have group-by, so that shouldn't be surprising. \$\endgroup\$
    – Dennis
    Jun 13, 2017 at 16:07
2
\$\begingroup\$

Clojure, 74 bytes

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

Looks quite verbose :/

\$\endgroup\$
2
  • \$\begingroup\$ Beat me to it (and beat me by a few bytes, clever use of comp - to reverse!). Not as short as other languages, but I thought it was amusing since Clojure has "group-by" and "frequencies" built in. \$\endgroup\$
    – MattPutnam
    Jun 13, 2017 at 18:04
  • \$\begingroup\$ When I read the task description I was hoping for 50 or 60 bytes, but the actual implementation turned out to be a bit trickier. \$\endgroup\$
    – NikoNyrh
    Jun 13, 2017 at 18:32
2
\$\begingroup\$

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])
\$\endgroup\$
1
  • \$\begingroup\$ Wow, I always forget about Bag, nice one! \$\endgroup\$ Jun 13, 2017 at 19:59
2
\$\begingroup\$

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.

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

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

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

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

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

\$\endgroup\$
4
  • \$\begingroup\$ The GatherBy I mentioned to Martin! I wondered how this would be done :). \$\endgroup\$ Jun 13, 2017 at 22:21
  • \$\begingroup\$ Sort[...,...&] is just SortBy[...,-Last@#&]. \$\endgroup\$ Jun 14, 2017 at 6:11
  • \$\begingroup\$ Length[f=...]. And First/@ is #&@@@. \$\endgroup\$ Jun 14, 2017 at 8:31
  • \$\begingroup\$ fixed, fixed and fixed \$\endgroup\$
    – ZaMoC
    Jun 14, 2017 at 8:38
2
\$\begingroup\$

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!

\$\endgroup\$
3
  • \$\begingroup\$ You can lose 7 bytes by eliminating the "which", and using logical indexing \$\endgroup\$
    – mb7744
    Jun 14, 2017 at 19:00
  • \$\begingroup\$ @mb7744 oh duh. \$\endgroup\$
    – Giuseppe
    Jun 14, 2017 at 19:24
  • 1
    \$\begingroup\$ I took another stab at it with R. It's unfortunate how long the lambda syntax is, so I set out trying to avoid it. In exchange I had to use nested lapply's, but at least in that case I can assign a short variable to lapply. I can't seem to assign a variable to the the function function... \$\endgroup\$
    – mb7744
    Jun 15, 2017 at 1:08
2
\$\begingroup\$

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

\$\endgroup\$
6
  • \$\begingroup\$ Your test is flawed (doesn't work for zero) but I think you can still save bytes by filtering and reversing instead of unshifting: a=>a.sort().map((_,n)=>a.filter((v,i)=>i-a.indexOf(v)==n&v!=a[i+1])).filter(a=>1/a[0]).reverse(). \$\endgroup\$
    – Neil
    Jun 14, 2017 at 21:06
  • \$\begingroup\$ Ahh, I should have known to test for 0! Your code fixes it, plus it's shorter, so thank you for that : ) \$\endgroup\$ Jun 14, 2017 at 21:44
  • \$\begingroup\$ Save 3 more bytes by changing .filter(a=>1/a[0]) to .filter(a=>''+a). \$\endgroup\$ Jun 15, 2017 at 13:29
  • \$\begingroup\$ Nice one, @TomasLangkaas, thanks. (Saves 2 bytes.) \$\endgroup\$ Jun 15, 2017 at 13:41
  • \$\begingroup\$ My bad (have trouble with counting), but .filter(a=>a+a) would provide the extra byte. \$\endgroup\$ Jun 15, 2017 at 13:49
2
\$\begingroup\$

Husk, 6 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
\$\endgroup\$
1
2
\$\begingroup\$

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

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

Factor, 63 bytes

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

Running the above code in Factor's REPL with some test cases

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

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!

\$\endgroup\$
3
  • \$\begingroup\$ This will currently fail if all elements are the same, because r is too short. r=[[]for _ in s*2] would be a simple fix, but replacing r[l.count(x)] with r[-l.count(x)] fixes this as well, while removing the [::-1] \$\endgroup\$
    – ovs
    Dec 31, 2021 at 11:10
  • \$\begingroup\$ And a few golfing hints: The assignment to s is not worth it, the last line can be shorter with a filter and using tuples instead of lists for the inner containers can save a few bytes \$\endgroup\$
    – ovs
    Dec 31, 2021 at 11:14
  • \$\begingroup\$ @ovs thanks! your tips helped a lot. I used l instead of s*2 and removed s assignment. \$\endgroup\$
    – Wasif
    Dec 31, 2021 at 16:34
1
\$\begingroup\$

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.

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ save one byte by removing the parentheses from a.count e \$\endgroup\$ Jan 9, 2021 at 17:54
1
\$\begingroup\$

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()
\$\endgroup\$
2
  • 2
    \$\begingroup\$ +1 You can remove the System.Func<int[],int[][]>F= and trailing ; though. That isn't part of the byte-count for these kind of lambdas. \$\endgroup\$ Jun 14, 2017 at 7:04
  • \$\begingroup\$ @KevinCruijssen, I had no idea. Thanks! \$\endgroup\$ Jun 14, 2017 at 22:41
1
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ as.double is shorter by one byte, and it should work the same as as.integer \$\endgroup\$
    – Giuseppe
    Jun 15, 2017 at 15:00
  • \$\begingroup\$ Well, it depends whether you want to return an integer or a double. If double is okay, maybe character would be as well, and we could both save some bytes. \$\endgroup\$
    – mb7744
    Jun 15, 2017 at 17:43
  • \$\begingroup\$ 50 bytes \$\endgroup\$
    – Giuseppe
    Dec 31, 2021 at 14:19
1
\$\begingroup\$

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]})}
\$\endgroup\$
1
  • \$\begingroup\$ Nice, thanks. I had to inlclude the ,() for grouping (since output was just showing as one continuous array). This is way more golfy than my original attempt; awesome work! \$\endgroup\$
    – JohnLBevan
    Jun 15, 2017 at 6:32
1
\$\begingroup\$

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!

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

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]]
}
\$\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.