Integer Interpretator

Question

The Challenge

Given a finite list of integers, split it into the fewest partitions possible such that no partition contains a number more than once.

Rules

Input can be in any format and any order.

Output can be in any format, as long as it's clear that each group is separate.

This is code-golf, so lowest score wins!

Example I/O

Input: [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2]
Output: [[1,2],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1]]

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

Input: [5,9,12,5,2,71,23,4,7,2,6,8,2,4,8,9,0,65,4,5,3,2]
Output: [[5,9,12,2,71,23,4,7,6,8,0,65,3],[5,4,8,9,2],[4,5,2],[2]]

Answer 1

Jelly, 3 bytes

ĠZị

A monadic Link accepting a list, which yields a shortest set-wise partition such that each part is a set.

Try it online!

How?

ĠZị - Link: list, L                      e.g. [8,2,4,2,9,4,1]
Ġ   - group indices of L by their values      [[7],[2,4],[3,6],[1],[5]]
 Z  - transpose                               [[7,2,3,1,5],[4,6]]
  ị - index into L                            [[1,2,4,8,9],[2,4]]

Answer 2

Python 2, 50 bytes

l=input()
while l:s=set(l);print s;map(l.remove,s)

Try it online!

Repeatedly prints the unique of elements of the list, then removes one of each such element. A rare imperative use of map.

Answer 3

Haskell, 39 bytes

First we collect all equal elements in separate lists using sort and then group. By transposeing the resulting list of lists we get at most one of each of those elements in the resulting lists.

import Data.List
f=transpose.group.sort

Try it online!

Example

                     [1,2,3,2,4,2,1,5] --input
                sort$[1,2,3,2,4,2,1,5] --[1,1,2,2,2,3,4,5]
          group.sort$[1,2,3,2,4,2,1,5] --[[1,1],[2,2,2],[3],[4],[5]]
transpose.group.sort$[1,2,3,2,4,2,1,5] --[[1,2,3,4,5],[1,2],[2]]

Answer 4

J, 20 17 bytes

_<@-."1~0|:1%%/.~

Try it online!

             %      divide 1 by each, 0 becomes infinity
              /.~   group equal values, every group gets padded with zeroes
           1%       invert back
        0|:         transpose
_<@-."1~            remove the infinities, put each row in a box

I suspect 0|:1%%/.~ is acceptable, we get

5 9 12 2 71 23 4 7 6 8 0 65 3
5 9  _ 2  _  _ 4 _ _ 8 _  _ _
5 _  _ 2  _  _ 4 _ _ _ _  _ _
_ _  _ 2  _  _ _ _ _ _ _  _ _

Answer 5

Jelly, 4 bytes

¹ƙ`Z

Try it online!

A monadic link that takes a list of integers and returns a list of lists of integers. Simply groups identical numbers and then transposes.

Answer 6

Japt, 3 bytes

ü y

Try it

Sorts & partitions by value and then transposes the result.

Answer 7

JavaScript (ES6), 59 bytes

a=>a.map(o=n=>b[i=o[n]=-~o[n],--i]=[...b[i]||[],n],b=[])&&b

Try it online!

Answer 8

Haskell, 54 bytes

(a:b)%n|elem n a=a:b%n|s<-n:a=s:b
_%n=[[n]]
foldl(%)[]

Try it online!

We define a function % which takes a single number and adds it to a partition scheme and we fold it across the input starting with an empty partition scheme.

Answer 9

Perl 6, 30 bytes

{roundrobin map &[xx],.Bag.kv}

Try it online!

Inspired by the Jelly answers.

Explanation

{                            }  # Anonymous block
                      .Bag      # Convert to Bag (multiset)
                          .kv   # Key-value sequence
            map &[xx],  # Repeat each key n times
 roundrobin  # Transpose

Old solution, 32 bytes

{(.Bag,{$_∖.Set}...^!*)>>.Set}

Try it online!

Explanation

{                            }  # Anonymous block
      ,         ...^    # Create sequence
  .Bag                  # starting with input converted to Bag (multiset)
       {$_∖.Set}        # Decrease weights by one each iteration
                    !*  # Until bag is empty
 (                    )>>.Set  # Convert all bags to sets

Answer 10

R, 54 bytes

for(i in 1:max(t<-table(scan())))print(names(t)[t>=i])

Try it online!

Builds a table of the counts of the values. For input 1 3 4 2 6 5 1 8 3 8, this gives

t = 1 2 3 4 5 6 8 
    2 1 2 1 1 1 2 

where the first row is names(t) (the different values in the input) and the second is the counts in t.

Then in the for loop, at iteration i, print only the names corresponding to counts ≥i.

Answer 11

Pyth, 4 bytes

.T.g

Try it online!

Answer 12

Red, 67 61 bytes

func[b][until[print a: unique b foreach e a[alter b e]b =[]]]

Try it online!

Inspired by xnor's Python answer - don't forget to upvote it!

This was a rare opportunity to use alter- If a value is not found in a series, append it; otherwise, remove it

Answer 13

Charcoal, 17 bytes

ＩＥ⌈Ｅθ№θιΦθ⁼№…θμλι

Try it online! Link is to verbose version of code. Explanation:

    θ               Input array
   Ｅ                Map over elements
     №              Count of
       ι            Current element in
      θ             Input array
  ⌈                 Maximum
 Ｅ                  Map over implicit range
         θ          Input array
        Φ           Filter elements where
           №        Count of
               λ    Current element in
             θ      Input array
            …       Truncated to length
              μ     Inner index
          ⁼         Is equal to
                ι   Outer index
Ｉ                   Cast to string
                    Implicitly print

Answer 14

J, 23 bytes

(}:,(~:</.])&>@{:)^:_@<

Try it online!

Answer 15

C (gcc) with -m32 flag, 231 213 210 bytes

Thanks to ceilingcat (-21 bytes) for the suggestions.

The function goes through the list of values and builds a reverse list of the unique values, incrementing its count on a match. After the list has been built, the function then goes through the list again, printing any values that have a non-zero count and decrementing the count: It repeats this until all values have a zero count.

g(v,c,p)int*v,*p;{int*i=p,w[3]={p,*v,!c};if(c){for(;i&&i[1]-w[1];i=*i);2[i=i?i:w]++;g(++v,--c,p=i-w?p:i);}else for(;w[2];p=*w)for(w[2]=!puts("");p;p=*p)p[2]?printf("\t%d",p[1]),p[2]-=w[2]=1:0;}f(v,c){g(v,c,0);}

Try it online!

Answer 16

Perl 6, 25 bytes

*.classify({%.{$_}++}){*}

Try it online!

Groups each element of the input by how many times it has appeared in the sequence so far, then take only the values

Answer 17

C (gcc), 114 bytes

W;*P;S(D,E)int*D,*E;{do for(P=D;P<E;*P==W?printf("%d ", W),*P=*D,*D++=W,P=E:++P);while(++W);puts("");D-E&&S(D,E);}

This solution takes a while to run because it iterates over all possible integer values from -2^31 to 2^31-1. Here is a TIO link to a slightly longer solution that runs a lot faster, the only difference is, that it uses short instead of int. Groups are separated by line breaks.

Try it online!

How does it work?

For every possible integer value
    if value in array
        print value
        remove found value entry from list
print endline
if array is not empty
    recursively call function on remaining array

int W;
int *P;

S(int* D, int* E)
{
    // this loop will run once for every possible integer value
    do
    {
        // search for the integer value W
        for(P=D;P<E;++P)
            // if the value is found
            if (*P == W)
            {
                // output the value, can happen only once per integer value
                printf("%d ", W);
                // overwrite the found value with the first value of the array
                // because we have to output the first value later
                *P = *D;
                // reduce the size of the remaining array by one
                D++;
                // jump out of for loop to seach for next possible value of W
                P = E;
            }
    }
    while(++W); // after the while loop W==0 again

    puts("");   // output new line

    if (D!=E)
        S(D,E); // if end is not reached, search again in ramaining array
}

Answer 18

R, 41 bytes

split(sort(s<-scan()),sequence(table(s)))

Try it online!

Like Robin Ryder's answer, this makes use of table to get counts of the unique elements in the input.

A fuller explanation to follow.

Answer 19

05AB1E, 4 bytes

{γζþ

Try it online or verify all test cases.

Explanation:

{     # Sort the (implicit) input-list
      #  i.e. [5,9,12,5,2,71,23,4,7,2,6,8,2,4,8,9,0,65,4,5,3,2]
      #   → [0,2,2,2,2,3,4,4,4,5,5,5,6,7,8,8,9,9,12,23,65,71]
 γ    # Group it into chunks of the same subsequent value
      #  → [[0],[2,2,2,2],[3],[4,4,4],[5,5,5],[6],[7],[8,8],[9,9],[12],[23],[65],[71]]
  ζ   # Zip/transpose; swapping rows/columns, with a space character as filler by default
      #  → [[  0, 2,   3,   4,   5,   6,   7,   8,   9,  12,  23,  65,  71],
      #     [' ', 2, ' ',   4,   5, ' ', ' ',   8,   9, ' ', ' ', ' ', ' '],
      #     [' ', 2, ' ',   4,   5, ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '],
      #     [' ', 2, ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ']]
   þ  # Remove all spaces by only keeping digits
      #  → [[0,2,3,4,5,6,7,8,9,12,23,65,71],[2,4,5,8,9],[2,4,5],[2]]
      # (after which the result is output implicitly)

Answer 20

Burlesque, 6 bytes

rasgtp

Try it online!

ra # Read input as array
sg # Sort and group like values
tp # Transpose

Answer 21

C++ (clang), 230 ... 201 198 bytes

#import<ios>
#import<queue>
#import<regex>
#import<set>
void f(std::vector<int>v){for(;v.size();puts(""))for(int e:std::set<int>(&v[0],&*v.end()))printf("%d ",e),v.erase(find(v.begin(),v.end(),e));}

Try it online!

Basic port of @xnor's algorithm without the clever stuff.

Saved 11 bytes thanks to @ErikF!!!
Saved 8 bytes thanks to @ceilingcat!!!

Answer 22

Zsh, 58 bytes

for x (${(u)@})<<<$x&&argv[$@[(i)$x]]=
<<<"
${*:+`$0 $@`}"

Try it online!

Yay, recursion! For each element $x of (u)nique ${@}rguments, print it, and set the first (i)nstance of it to the empty string.

Finally, print a newline as a list delimiter, and if the remaining arguments are nonempty, substitute $0 $@, which is this program, called with all remaining nonempty elements.