Soit une liste d'entiers positifs sans ordre particulier et pouvant contenir des doublons. Écrivez un programme ou une fonction qui génère une liste d'entiers positifs (dont l'ordre n'est pas important) de telle sorte que la fusion de et aboutit à la plus petite liste qui peut être entièrement divisée en plages identiques d'entiers , où est le plus grand élément deM L M [ 1 .. i ] i $L$$M$$L$$M$$[1..i]$$i$$L$

Exemple

Soit L = [5,3,3,2,7]. L'élément maximal de Lest 7. Le plus grand nombre de fois qu'un entier spécifique se produit est 2( 3apparaît 2 fois). Par conséquent, nous devons afficher la liste Mqui permettra de terminer Lafin que nous puissions construire des 2plages d'entiers de 1à 7.

Par conséquent, nous devons sortir M = [1,1,2,4,4,5,6,6,7], de sorte que chaque entier de 1à 7apparaisse 2fois.

Entrées et sorties

• Utilisez quelque chose dans votre langue qui ressemble aux listes. La structure de données utilisée pour l'entrée et la sortie doit être la même.
• La liste d'entrée ne contiendra que des entiers positifs.
• La liste d'entrée ne sera pas vide.
• Vous ne pouvez pas supposer que la liste d'entrée est triée.
• L'ordre dans la liste de sortie est sans importance.

Cas de test

Input                  Output
[1]                    []
[7]                    [1, 2, 3, 4, 5, 6]
[1, 1, 1]              []
[1, 8]                 [2, 3, 4, 5, 6, 7]
[3, 3, 3, 3]           [1, 1, 1, 1, 2, 2, 2, 2]
[5, 2, 4, 5, 2]        [1, 1, 3, 3, 4]
[5, 2, 4, 5, 5]        [1, 1, 1, 2, 2, 3, 3, 3, 4, 4]
[5, 3, 3, 2, 7]        [1, 1, 2, 4, 4, 5, 6, 6, 7]

Notation

Il s'agit de code-golf , donc la réponse la plus courte en octets l'emporte.

Gelée , 9 octets

Enregistré 1 octet grâce à Jonathan Allan . Le pied de page appelle le lien principal, trie le résultat pour qu'il corresponde aux cas de test et formate la sortie sous forme de grille.

RṀẋLƙ`Ṁœ-

Essayez-le en ligne! ou Découvrez une suite de tests!

Alternatives

ṀRẋLƙ`Ṁœ-
RṀẋṢŒɠṀƊœ-
ṀRẋṢŒɠṀƊœ-
LƙɓṀRẋṀœ-⁸
LƙɓRṀẋṀœ-⁸

Essayez l'un d'entre eux en ligne!

Explication

ṀRẋLƙ`Ṁœ- Programme complet. N = entrée.
ṀR Plage de 1 à max (N): [1 ... max (N)]
   Lƙ` Longueur de la carte sur des groupes formés d'éléments identiques.
  ẋ Répétez la plage T fois, pour chaque T dans le résultat de ce qui précède.
      Ṁ Maximum. En gros, obtenez la plage de répétition max (^^) fois.
       œ- Différence multiset avec N.

Perl 6 , 37 33 octets

-4 octets grâce à nwellnhof!

{^.keys.max+1 xx.values.max∖$_}

Essayez-le en ligne!

Bloc de code anonyme qui prend un sac et renvoie un sac de valeurs.

Explication:

{                             } # Anonymous code block
 ^.keys.max+1  # Create a range from 1 to the maximum value of the list
              xx  # Multiply the list by:
                .values.max      # The amount of the most common element
                           ∖$_   # Subtract the original Bag

R , 59 49 48 octets

rep(s<-1:max(L<-scan()),max(y<-table(c(L,s)))-y)

Essayez-le en ligne!

Python 2 , 86 83 80 72 octets

def f(l):m=range(1,max(l)+1)*max(map(l.count,l));map(m.remove,l);print m

Essayez-le en ligne!

05AB1E , 17 16 17 octets

¢Z¹ZLŠŠи{ðý¹vyõ.;

-1 octet grâce à @ Mr.Xcoder .
+1 octet après avoir corrigé le bogue.

Peut-être que je regarde complètement au-delà, mais 05AB1E a-t-il même a supprimer tous les éléments de la liste b de la liste a .. (EDIT: Ce n'est pas le cas ..) Je sais comment supprimer tous les plusieurs fois, mais pas une fois chacun .. (différence multiset)

Peut certainement être joué au golf. Pas vraiment content, tbh .. Je vais voir si je peux jouer au golf avant d'ajouter une explication. EDIT: Ajout d'une explication ..

Essayez-le en ligne ou vérifiez tous les cas de test .

Explication:

¢         # Get the occurrences for each item in the (implicit) input-List
          #  i.e. [5,3,3,2,7] → [1,2,2,1,1]
 Z        # And get the maximum
          #  i.e. [1,2,2,1,1] → 2
¹Z        # Also get the maximum from the input-list itself
          #  i.e. [5,3,3,2,7] → 7
  L       # And create a list in the range [1, max]
          #  i.e. 7 → [1,2,3,4,5,6,7]
ŠŠ        # Two triple-swaps so the stack order becomes:
          # trash we don't need; ranged list; occurrence max
  и       # Repeat the ranged list the occurence amount of times
          #  i.e. [1,2,3,4,5,6,7] and 2 → [1,2,3,4,5,6,7,1,2,3,4,5,6,7]

          #Now the work-around bit because 05AB1E lacks a builtin for multiset difference..
{         # Sort the list
          #  i.e. [1,2,3,4,5,6,7,1,2,3,4,5,6,7] → [1,1,2,2,3,3,4,4,5,5,6,6,7,7]
 ðý       # Join this list by spaces
          #  i.e. [1,1,2,2,3,3,4,4,5,5,6,6,7,7] → '1 1 2 2 3 3 4 4 5 5 6 6 7 7'
   ¹v     # Loop `y` over the input-List:
     yõ.; # Replace every first occurrence of `y` with an empty string
          #  i.e. '1 1 2 2 3 3 4 4 5 5 6 6 7 7' and 3 → '1 1 2 2  3 4 4 5 5 6 6 7 7'

R , 59 55 octets

En utilisant le vecsetspackage, nous pouvons en réduire la longueur. Avec glnous pouvons obtenir la sortie commandée. Cela ne fonctionne pas dans TIO. Suivant le style de solution de @ digEmAll (plutôt intelligent) sans définition de fonction, cela peut être considéré comme une solution de 55 octets.

vecsets::vsetdiff(c(gl(m<-max(L<-scan()),sum(L==m))),L)

f=function(x){scan<-function()x
vecsets::vsetdiff(c(gl(m<-max(L<-scan()),sum(L==m))),L)
}

f(c(1))                # expected: integer(0)
f(c(7))                # expected: c(1, 2, 3, 4, 5, 6)
f(c(1, 1, 1))          # expected: integer(0)
f(c(1, 8))             # expected: c(2, 3, 4, 5, 6, 7)
f(c(3, 3, 3, 3))       # expected: c(1, 1, 1, 1, 2, 2, 2, 2)
f(c(5, 2, 4, 5, 2))    # expected: c(1, 1, 3, 3, 4)
f(c(5, 2, 4, 5, 5))    # expected: c(1, 1, 1, 2, 2, 3, 3, 3, 4, 4)

JavaScript (ES6), 98 octets

Cela s'est avéré assez difficile à jouer au golf en dessous de 100 octets. Il pourrait y avoir une meilleure approche.

a=>(a.map(o=M=m=n=>m=(c=o[M=n<M?M:n,n]=-~o[n])<m?m:c),g=k=>k?o[k]^m?[...g(k,o(k)),k]:g(k-1):[])(M)

Essayez-le en ligne!

Comment?

Nous parcourons d'abord le tableau d'entrée a[]pour recueillir les données suivantes:

• M = élément le plus élevé trouvé dans le tableau d'entrée
• m = le plus grand nombre d'occurrences du même élément
• o[n] = nombre d'occurrences de n

Notez que oest principalement défini comme une fonction, mais l'objet sous-jacent est également utilisé pour stocker le nombre d'occurrences.

a.map(                      // a[] = input array()
  o =                       // o = callback function of map()
  M = m =                   // initialize m and M to non-numeric values
  n =>                      // for each value n in a[]:
    m = (                   //   this code block will eventually update m
      c = o[                //     c = updated value of o[n]
        M = n < M ? M : n,  //     update M to max(M, n)
        n                   //     actual index into o[]
      ] = -~o[n]            //     increment o[n]
    ) < m ?                 //   if o[n] is less than m:
      m                     //     let m unchanged
    :                       //   else:
      c                     //     set it to c
)                           // end of map()

Nous utilisons ensuite la fonction récursive g()pour construire la sortie.

(g = k =>                   // k = current value
  k ?                       // if k is not equal to 0:
    o[k] ^ m ?              //   if o[k] is not equal to m:
      [ ...g(k, o(k)),      //     increment o[k] and do a recursive call with k unchanged
        k ]                 //     append k to the output
    :                       //   else:
      g(k - 1)              //     do a recursive call with k - 1
  :                         // else:
    []                      //   stop recursion
)(M)                        // initial call to g() with k = M

Haskell, 72 octets

import Data.List
f l=(last(sortOn(0<$)$group$sort l)>>[1..maximum l])\\l

Essayez-le en ligne!

            sort l      -- sort input list
       group            -- group identical elements
   sortOn(0<$)          -- sort by length
 last                   -- take the last element, i.e. the list
                        -- of the most common element
      >>[1..maximum l]  -- replace each of it's elements
                        -- with the list [1..maximum l]
  \\l                   -- remove elements of the input list

Brachylog , 18 17 octets

⌉⟦₁;Ij₎R⊇p?;.cpR∧

Essayez-le en ligne!

1 octet enregistré grâce à @Kroppeb.

Explication

⌉                  Take the largest element in the Input
 ⟦₁                 Construct the range [1, …, largest element in the Input]
   ;Ij₎R            Juxtapose that range to itself I times, I being unknown; 
                       call the result R
       R⊇p?         The Input must be an ordered subset of R, up to a permutation
          ?;.c      Concatenate the Input and the Output 
                       (the Output being unknown at this point)
              pR    This concatenation must result in R, up to a permutation
                ∧   (Find a fitting value for the Output that verifies all of this)

Java 10, 186 octets

import java.util.*;L->{Integer m=0,f=0,t;for(int i:L){m=i>m?i:m;f=(t=Collections.frequency(L,i))>f?t:f;}var r=new Stack();for(;m>0;m--)for(t=f;t-->0;)if(!L.remove(m))r.add(m);return r;}

Essayez-le en ligne.

Explication:

import java.util.*;   // Required import for Collections and Stack
L->{                  // Method with Integer-list as both parameter and return-type
  Integer m=0,        //  Max, starting at 0
          f=0,        //  Max frequency, starting at 0
          t;          //  Temp integer
  for(int i:L){       //  Loop over the input-List
    m=i>m?i:m;        //   If the current item is larger than the max, set it as new max
    f=(t=Collections.frequency(L,i))>f?t:f;}
                      //   If the current frequency is larger than the max freq, set it as new max
  var r=new Stack();  //  Result-List
  for(;m>0;m--)       //  Loop the maximum in the range [m,0)
    for(t=f;t-->0;)   //   Inner loop the frequency amount of times
      if(!L.remove(m))//    Remove `m` from the input list
                      //    If we were unable to remove it:
        r.add(m);     //     Add it to the result-List
  return r;}          //  Return the result-List

Husk , 12 octets

1 octet enregistré grâce à BWO .

S-§*oḣ▲(▲Ṡm#

Essayez-le en ligne!

MATL , 24 21 octets

X>:GS&Y'X>yGhS&Y'q-Y"

Essayez-le en ligne!

MATL , 14 octets

L'entrée est un vecteur colonne, avec ;comme séparateur.

llXQtn:yX>b-Y"

Essayez-le en ligne! Ou vérifiez tous les cas de test (ceci s'affiche --après chaque sortie afin que la sortie vide puisse être identifiée).

Explication

Considérez la saisie [5; 2; 4; 5; 5]comme exemple.

llXQ     % Implicit input. Accumarray with sum. This counts occurrences
         % of each number, filling with zeros for numbers not present
         % STACK: [0; 1; 0; 1; 3]
tn:      % Duplicate, number of elements, range
         % STACK: [0; 1; 0; 1; 3], [1 2 3 4 5]
yX>      % Duplicate from below, maximum of array
         % STACK: [0; 1; 0; 1; 3], [1 2 3 4 5], 3 
b        % Bubble up
         % STACK: [1 2 3 4 5], 3, [0; 1; 0; 1; 3] 
-        % Subtract, element-wise
         % STACK: [1 2 3 4 5], [3; 2; 3; 2; 0] 
Y"       % Repelem (run-length decode). Implicit display
         % STACK: [1 1 1 2 2 3 3 3 4 4]

Pyth , 13 octets

.-*SeSQeSlM.g

Essayez-le ici! ou Découvrez une suite de tests!

Fusain , 19 octets

Ｆ…·¹⌈θＥ⁻⌈Ｅθ№θκ№θιＩι

Essayez-le en ligne! Le lien est vers la version détaillée du code. Aurait été de 16 octets si les entiers avaient été non négatifs au lieu de positifs. Explication:

     θ              First input
    ⌈               Maximum
 …·¹                Inclusive range starting at 1
Ｆ                   Loop over range
          θ         First input
         Ｅ          Loop over values
            θ       First input
             κ      Inner loop value
           №        Count occurrences
        ⌈           Maximum
               θ    First input
                ι   Outer loop value
              №     Count occurrences
       ⁻            Subtract
      Ｅ             Map over implicit range
                  ι Current value
                 Ｉ  Cast to string
                    Implicitly print on separate lines

APL (Dyalog Classic) , 18 17 octets

∊{⊂⍳⌈/⍵}~¨∘↓∘⍉⊣¨⌸

Essayez-le en ligne!

les usages ⎕io←1

Prolog (SWI) , 211 octets

Cela fait un moment que je n'ai pas programmé à Prolog. Peut certainement être joué au golf plus loin, mais j'ai un examen pour étudier hahaha.

Code

f(L,X):-max_list(L,M),f(L,M,[],X,M).
f([],0,_,[],_).
f(L,0,_,A,M):-f(L,M,[],A,M).
f([],I,H,[I|A],M):-N is I-1,f(H,N,[],A,M).
f([I|R],I,H,A,M):-append(H,R,S),f(S,I,[],[I|A],M).
f([H|R],I,G,A,M):-f(R,I,[H|G],A,M).

Essayez-le en ligne!

Version non golfée

f(List, Result) :- 
    max_list(List, MaxIndex), 
    f(List, MaxIndex, [], Result, MaxIndex).

f([], 0, _, [], _).

f(List, 0, _, Acc, MaxIndex) :- 
    f(List, MaxIndex, [], Acc, MaxIndex).

f([], Index, History, [Index | Acc], MaxIndex) :- 
    NewIndex is Index - 1, f(History, NewIndex, [], Acc, MaxIndex).

f([Index | Remaining], Index, History, Acc, MaxIndex) :-
    append(History, Remaining, Result),
    f(Result, Index, [], [Index | Acc], MaxIndex).

f([Head | Remaining], Index, History, Acc, MaxIndex) :- 
    f(Remaining, Index, [Head | History], Acc, MaxIndex).

Clojure, 94 octets

#(for[F[(frequencies %)]i(range 1(+(apply max %)1))_(range(-(apply max(vals F))(or(F i)0)))]i)

C ++, 234 octets

#include<vector>
#include<map>
using X=std::vector<int>;
X f(X x){int q,z;q=z=0;std::map<int,int>y;X o;
for(auto i:x)++y[i];for(auto i:y)q=q>i.second?q:i.second;
for(;++z<=y.rbegin()->first;)for(;y[z]++<q;)o.push_back(z);return o;}

(Les sauts de ligne dans le corps de la fonction sont pour la lisibilité).

La fonction prend et retourne un vecteur d'entiers. Il utilisestd::map pour trouver l'élément max de la liste d'entrée et aussi pour compter les occurrences de chaque élément distinct.

Explication:

// necessary includes. Note that each of these is longer than whole Jelly program!
#include <vector>
#include <map>

// this type occurs three times in the code
using X = std::vector<int>;

// The function
X f (X x)
{
   // initialize some variables
   int q, z; // q will hold the max count
   q = z = 0;
   std::map <int, int> y; // The map for sorting
   X o; // The output vector

   // Populate the map, effectively finding the max element and counts for all of them
   for (auto i : x)
       ++y[i];

   // find the max count
   for (auto i : y)
       q = q > i.second ? q : i.second;

   // Populate the output vector

   // Iterate all possible values from 1 to the max element (which is the key at y.rbegin ())
   // Note that z was initialized at 0, so we preincrement it when checking the condition
   for (; ++z <= y.rbegin ()->first;)
       // for each possible value, append the necessary quantity of it to the output
       for(; y[z]++ < q;)
           o.push_back (z);

   return o;
}

Gaia , 12 octets

::⌉┅¤:C¦⌉&¤D

Essayez-le en ligne!

C (gcc) , 177 octets

L'entrée et la sortie se font via stdin et stdout. Les deux tableaux sont limités à 2 ^ 15 éléments, mais ils peuvent atteindre 2 ^ 99 éléments.

f(j){int n=0,m=0,i=0,a[1<<15],b[1<<15]={0};for(;scanf("%i",&a[i])>0;i++)j=a[i],m=j>m?j:m,b[j-1]++;for(i=m;i--;)n=b[i]>n?b[i]:n;for(i=m;i--;)for(j=n-b[i];j--;)printf("%i ",i+1);}

Avec une mise en forme:

f(j){
  int n=0, m=0, i=0, a[1<<15], b[1<<15]={0};
  for(;scanf("%i",&a[i])>0;i++) j=a[i], m=j>m?j:m, b[j-1]++;
  for(i=m;i--;) n=b[i]>n?b[i]:n;
  for(i=m;i--;) for(j=n-b[i];j--;) printf("%i ",i+1);
}

Essayez-le en ligne!