Grupuj listę według częstotliwości


26

Biorąc pod uwagę listę liczb całkowitych, zgrupuj elementy, które występują najczęściej, a następnie zgrupuj kolejne i tak dalej, aż każdy unikalny element na liście zostanie zgrupowany jeden raz.


Przykłady:

Wkład: [1,2,3]

Wydajność: [[1,2,3]]


Wkład: [1,1,1,2,2,3,3,4,5,6]

Wydajność: [[1],[2,3],[4,5,6]]


Wkład: [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]

Wydajność: [[6, 8],[5],[1],[7],[9,4,-56]]


Wkład: []

Wydajność: []


Wkład: (empty input)

Wydajność: ERROR/Undefined/Doesn't matter


Zasady

  • Grupy muszą przejść od częstotliwości maksymalnej do częstotliwości minimalnej.
  • Wewnętrzna kolejność zgrupowań jest dowolna ( [8,6]zamiast tego mógłby mieć przykład EG 3 ).
  • To jest , wygrana o najniższej liczbie bajtów.

Związane z


1
Czy dane wyjściowe mogą mieć format ciągów? To znaczy. Lista list, ale każda liczba reprezentowana jest przez znak zamiast liczby całkowitej.
mb7744

Odpowiedzi:



7

Mathematica, 43 bajty

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

Wypróbuj online! (Korzystanie z matematyki.)

Alternatywnie:

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

5
Nie ma wbudowanego?
Magic Octopus Urn

Jest GatherByopcją, nie jestem pewien, ponieważ nie znam języka.
Magic Octopus Urn

1
@carusocomputing Sortuje grupy według pierwszego wystąpienia elementów na oryginalnej liście, więc nadal będę musiał posortować grupy. Sortując najpierw listę, mogę zapisać bajt za pomocą SplitBy(również SortBybyłoby to bardziej skomplikowane, gdybym to zrobił GatherBy).
Martin Ender,

Interesujące, więc „musi być w porządku od maksymalnego do minimalnego”, że to popsuło?
Magic Octopus Urn

@carusocomputing Dokładnie.
Martin Ender,

5

Python 2 , 145 141 bajtów

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

Wypróbuj online!

To moje pierwsze zgłoszenie po latach czytania.

To w zasadzie stawia wszystkie elementy do licznika (Słownik ilu z każdego elementu na liście) i .most_common () umieszcza elementy w decending rozkaz częstotliwości. Następnie wystarczy sformatować elementy na właściwej liście.

Zaoszczędzono 4 bajty dzięki ovs .


4
Witamy w PPCG :). Nie uzależniaj się tak jak ja.
Magic Octopus Urn

Utworzenie własnej funkcji itemgetter jest o 4 bajty krótsze niż jej zaimportowanie:o=lambda n:lambda l:l[n]
ovs

5

JavaScript (ES6), 95 101 bajtów

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)

W jaki sposób?

Dla każdego elementu x tablicy wejściowej a obliczamy liczbę n elementów a, które są różne od x :

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

Używamy indeksów n i x do wypełnienia tablicy o :

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

Edycja : Ponieważ JS nie obsługuje ujemnych indeksów tablicowych, potrzebujemy formuły x * x + (x > 0)wymuszającej indeksy dodatnie.

Daje nam to tablicę tablic zawierającą unikalne elementy oryginalnej listy, pogrupowane według częstotliwości i uporządkowane od najczęstszej do najmniejszej.

Jednak zarówno zewnętrzna tablica, jak i wewnętrzne tablice potencjalnie mają wiele pustych miejsc, które chcemy odfiltrować. Robimy to za pomocą funkcji F , zastosowanej do o i każdego z jego elementów:

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

Przypadki testowe


Myślę, że Setoszczędza bajt: 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]).
Neil

@Neil Jest to zupełnie inne od mojego obecnego podejścia. Może powinieneś zamieścić to jako nową odpowiedź?
Arnauld

Nie sądziłem, że zmiana o[n]z zestawu na zestaw byłaby inna, ale i tak grałem już w grę @ RickHitchcock, więc nie ma aż tak wiele sensu.
Neil



2

Clojure, 74 bajty

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

Wygląda dość gadatliwie: /


Pokonaj mnie do tego (i pobij mnie o kilka bajtów, sprytne użycie comp -do cofania!). Nie tak krótkie jak inne języki, ale pomyślałem, że to zabawne, ponieważ Clojure ma wbudowane „grupowanie według” i „częstotliwości”.
MattPutnam

Kiedy czytałem opis zadania, liczyłem na 50 lub 60 bajtów, ale rzeczywista implementacja okazała się nieco trudniejsza.
NikoNyrh

2

Perl 6 , 43 bajtów

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

Sprawdź to

Rozszerzony:

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

Wow, zawsze zapominam o Bagmiłym!
Magic Octopus Urn

2

Narzędzia Bash + GNU, 71 61

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

Wprowadź jako listę rozdzielaną znakiem nowej linii. Dane wyjściowe jako rozdzielana przecinkami lista wartości rozdzielanych przecinkami.

Wypróbuj online .


2

MATL , 9 bajtów

9B#uw3XQP

Dane wejściowe to wektor kolumny, używany ;jako separator.

Wypróbuj online!

Wyjaśnienie

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

2

k, 22 bajtów

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

Wypróbuj online.

( Wydaje się, że k AW wymaga dodatkowego @przed #, ale ok nie.)

Wyjaśnienie:

                     = /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

github.com/JohnEarnest/ok dla każdego, kto zastanawia się, co to kjest, tak naprawdę ok. Ba-dum-tssss ...
Magic Octopus Urn

2

Brachylog , 10 bajtów

ọtᵒ¹tᵍhᵐ²|

Wypróbuj online!

Wyjaśnienie

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

2

Mathematica, 79 bajtów

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

wkład

[{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}]

wydajność

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


Spotkanie, o którym wspominałem Martin! Zastanawiałem się, jak by to było zrobione :).
Magic Octopus Urn

Sort[...,...&]jest po prostu SortBy[...,-Last@#&].
Martin Ender

Length[f=...]. I First/@jest #&@@@.
Martin Ender

naprawiono, naprawiono i naprawiono
J42161217

2

R , 84 77 bajtów

-7 bajtów dzięki mb7744

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

Czyta ze standardowego; zwraca listę z wektorami liczb całkowitych w porządku rosnącym. Jeśli moglibyśmy zwrócić ciągi zamiast ints, to mógłbym upuścić 11 bajtów (usuwając wywołanie do as.double), ale to wszystko. tableFunkcja R wykonuje tutaj podnoszenie ciężarów, licząc wystąpienia każdego elementu swojego wkładu; następnie agreguje je według count ( names). Oczywiście jest to ciąg, więc musimy zmusić go do liczby całkowitej / podwójnej.

Wypróbuj online!


Możesz stracić 7 bajtów, eliminując „które” i używając logicznego indeksowania
mb7744,

@ mb7744 oh duh.
Giuseppe

1
Zrobiłem kolejne dźgnięcie w to z R. To niefortunne, jak długo trwa składnia lambda, więc postanowiłem tego uniknąć. W zamian musiałem użyć zagnieżdżonych lapply, ale przynajmniej w takim przypadku mogę przypisać krótką zmienną lapply. Nie mogę przypisać zmiennej do funkcji function...
mb7744,

2

JavaScript (ES6), 100 98 96 93 bajtów

Zaoszczędzono 2 bajty dzięki @Neil (plus naprawił błąd w krawędzi w moim kodzie). Zaoszczędź jeszcze 3 bajty dzięki @TomasLangkaas.

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

Przypadki testowe

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


Twój test jest błędny (nie działa na zero), ale myślę, że można jeszcze uratować bajtów poprzez filtrowanie i cofania zamiast 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().
Neil

Ahh, powinienem był wiedzieć, żeby przetestować na 0! Twój kod to naprawia, a ponadto jest krótszy, więc dziękuję za to
:)

Zaoszczędź 3 bajty więcej, zmieniając .filter(a=>1/a[0])na .filter(a=>''+a).
Tomas Langkaas,

Niezły, @TomasLangkaas, dzięki. (Zapisuje 2 bajty.)
Rick Hitchcock,

Mój zły (mam problem z liczeniem), ale .filter(a=>a+a)zapewniłby dodatkowy bajt.
Tomas Langkaas,

1

V , 60 , 54 bajtów

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

Wypróbuj 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

Mimo że uwielbiam V, jestem prawie pewien, że jest to najgorszy możliwy język dla tego zadania. Zwłaszcza biorąc pod uwagę, że nie obsługuje list i zasadniczo nie obsługuje liczb. Po prostu manipulacja ciągiem.


1

C #, 119 bajtów

Wystarczy szybkie dźgnięcie w to:

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

2
+1 Możesz jednak usunąć System.Func<int[],int[][]>F=i końcowe ;. To nie jest część liczby bajtów dla tego rodzaju lambd.
Kevin Cruijssen

@KevinCruijssen, nie miałem pojęcia. Dzięki!
Hand-E-Food

1

R , 66 bajtów

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

Wypróbuj online!

Jeśli na wyjściu liczby całkowite mogą mieć format ciągów, mogą spaść do 48 bajtów (jak wspomniano w odpowiedzi @ Giuseppe).


Nie golfowany:

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

as.doublejest krótszy o jeden bajt i powinien działać tak samo jakas.integer
Giuseppe

Zależy to od tego, czy chcesz zwrócić liczbę całkowitą czy podwójną. Jeśli podwójne jest w porządku, być może postać też, i obaj moglibyśmy zaoszczędzić trochę bajtów.
mb7744

1

PowerShell, 77, 70 bajtów

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

Uwaga: Aby zobaczyć, że wyniki te są poprawnie pogrupowane (ponieważ wizualnie nie ma żadnych podziałów między zawartością każdej tablicy), możesz chcieć dołączyć | write-hostna końcu powyższej linii.

Podziękowanie

Dzięki:

  • TessellatingHeckler do oszczędzania 7 bajtów poprzez masowe refaktoryzację / przepisywanie do bardziej golfowego podejścia.

Poprzedni

77 bajtów

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

Fajnie dzięki. Musiałem uwzględnić opcję ,()for grouping (ponieważ dane wyjściowe były wyświetlane jako jedna ciągła tablica). To jest znacznie bardziej golfowy niż moja pierwotna próba; świetna robota!
JohnLBevan,

0

Groovy, 71 bajtów

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

Właśnie dowiedziałem się o groupBy po utworzeniu tego. Nie wiedziałem, że zbieranie nie jest moim jedynym wyborem.


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

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.