26
\$\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
    \$\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 '17 at 0:13

21 Answers 21

6
\$\begingroup\$

Pyth, 8 7 bytes

_{M.g/Q

Try it online!

1 byte thanks to FryAmTheEggman.

\$\endgroup\$
  • \$\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 '17 at 8:07
  • \$\begingroup\$ got it - thanks for the explanation! \$\endgroup\$ – Digital Trauma Jun 14 '17 at 17:26
  • \$\begingroup\$ Congratulations. \$\endgroup\$ – Magic Octopus Urn Aug 17 '17 at 21:44
  • \$\begingroup\$ @MagicOctopusUrn thank you. \$\endgroup\$ – Leaky Nun Aug 17 '17 at 21:44
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
    \$\begingroup\$ There's no built-in? \$\endgroup\$ – Magic Octopus Urn Jun 13 '17 at 16:22
  • \$\begingroup\$ Is GatherBy an option, not sure because I don't know the language. \$\endgroup\$ – Magic Octopus Urn Jun 13 '17 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\$ – Martin Ender Jun 13 '17 at 16:34
  • \$\begingroup\$ Interesting, so the "must be in order from maximal to minimal" messes that up? \$\endgroup\$ – Magic Octopus Urn Jun 13 '17 at 16:35
  • \$\begingroup\$ @carusocomputing Exactly. \$\endgroup\$ – Martin Ender Jun 13 '17 at 16:36
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\$
  • 4
    \$\begingroup\$ Welcome to PPCG :). Don't get as addicted as I did. \$\endgroup\$ – Magic Octopus Urn Jun 13 '17 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 '17 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\$
  • \$\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 '17 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 '17 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 '17 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\$
  • 5
    \$\begingroup\$ Did... Pyth... beat... Jelly? \$\endgroup\$ – Leaky Nun Jun 13 '17 at 16:06
  • 1
    \$\begingroup\$ Jelly doesn't have group-by, so that shouldn't be surprising. \$\endgroup\$ – Dennis Jun 13 '17 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\$
  • \$\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 '17 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 '17 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\$
  • \$\begingroup\$ Wow, I always forget about Bag, nice one! \$\endgroup\$ – Magic Octopus Urn Jun 13 '17 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\$
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\$
  • \$\begingroup\$ The GatherBy I mentioned to Martin! I wondered how this would be done :). \$\endgroup\$ – Magic Octopus Urn Jun 13 '17 at 22:21
  • \$\begingroup\$ Sort[...,...&] is just SortBy[...,-Last@#&]. \$\endgroup\$ – Martin Ender Jun 14 '17 at 6:11
  • \$\begingroup\$ Length[f=...]. And First/@ is #&@@@. \$\endgroup\$ – Martin Ender Jun 14 '17 at 8:31
  • \$\begingroup\$ fixed, fixed and fixed \$\endgroup\$ – J42161217 Jun 14 '17 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\$
  • \$\begingroup\$ You can lose 7 bytes by eliminating the "which", and using logical indexing \$\endgroup\$ – mb7744 Jun 14 '17 at 19:00
  • \$\begingroup\$ @mb7744 oh duh. \$\endgroup\$ – Giuseppe Jun 14 '17 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 '17 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\$
  • \$\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 '17 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\$ – Rick Hitchcock Jun 14 '17 at 21:44
  • \$\begingroup\$ Save 3 more bytes by changing .filter(a=>1/a[0]) to .filter(a=>''+a). \$\endgroup\$ – Tomas Langkaas Jun 15 '17 at 13:29
  • \$\begingroup\$ Nice one, @TomasLangkaas, thanks. (Saves 2 bytes.) \$\endgroup\$ – Rick Hitchcock Jun 15 '17 at 13:41
  • \$\begingroup\$ My bad (have trouble with counting), but .filter(a=>a+a) would provide the extra byte. \$\endgroup\$ – Tomas Langkaas Jun 15 '17 at 13:49
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\$

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
    \$\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\$ – Kevin Cruijssen Jun 14 '17 at 7:04
  • \$\begingroup\$ @KevinCruijssen, I had no idea. Thanks! \$\endgroup\$ – Hand-E-Food Jun 14 '17 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\$
  • \$\begingroup\$ as.double is shorter by one byte, and it should work the same as as.integer \$\endgroup\$ – Giuseppe Jun 15 '17 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 '17 at 17:43
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\$
  • \$\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 '17 at 6:32
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\$
0
\$\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\$

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.