15
\$\begingroup\$

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 , 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]]
\$\endgroup\$
  • 2
    \$\begingroup\$ Could you clarify a bit what you mean by splitting? Does it matter the order of the original list when splitting? \$\endgroup\$ – Post Rock Garf Hunter Dec 21 '19 at 14:51
  • \$\begingroup\$ The order of the original list does not matter. I'm not quite sure how I can make "splitting" any clearer; the Example I/O may help you understand what I mean. \$\endgroup\$ – Corsaka Dec 21 '19 at 15:39
  • 7
    \$\begingroup\$ You can just mention that the order of the original list does not matter. The test cases do preserve order to some extent so they are not really helpful in the deduction. Plus a clear spec is always better than examples. \$\endgroup\$ – Post Rock Garf Hunter Dec 21 '19 at 16:26
  • 3
    \$\begingroup\$ Is it interpretator or interpreter? \$\endgroup\$ – S.S. Anne Dec 21 '19 at 23:07
  • 1
    \$\begingroup\$ Also, how big do the integers have to be? Can we restrict them to a certain size? \$\endgroup\$ – S.S. Anne Dec 21 '19 at 23:08

22 Answers 22

8
\$\begingroup\$

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]]
\$\endgroup\$
  • \$\begingroup\$ We had the same idea. I was sure there was a way to do it in 3. I’d thought of Ġị⁸Z but not of swapping the Z and . \$\endgroup\$ – Nick Kennedy Dec 21 '19 at 10:17
  • 1
    \$\begingroup\$ Yeah, I saw just after I posted - good job, I prepped a list-partition version, and then saw the examples. \$\endgroup\$ – Jonathan Allan Dec 21 '19 at 10:27
19
\$\begingroup\$

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.

\$\endgroup\$
12
\$\begingroup\$

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]]
\$\endgroup\$
  • 1
    \$\begingroup\$ You don't need to count the f= \$\endgroup\$ – Post Rock Garf Hunter Dec 21 '19 at 18:07
5
\$\begingroup\$

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  _  _ _ _ _ _ _  _ _
\$\endgroup\$
  • \$\begingroup\$ Peak J, I played around trying to get the transpose trick to work, but it’s bulky without this clever 0/inf trick \$\endgroup\$ – Jonah Dec 21 '19 at 21:09
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Japt, 3 bytes

ü y

Try it

Sorts & partitions by value and then transposes the result.

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

JavaScript (ES6), 59 bytes

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

Try it online!

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

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.

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

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

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.

\$\endgroup\$
  • \$\begingroup\$ 41 bytes and returns integers to boot! \$\endgroup\$ – Giuseppe Dec 24 '19 at 18:26
  • \$\begingroup\$ @Giuseppe Very nice! You should post it separately. (Along with an explanation, as I'm still unclear how it works!) \$\endgroup\$ – Robin Ryder Dec 25 '19 at 10:19
2
\$\begingroup\$

Pyth, 4 bytes

.T.g

Try it online!

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

Charcoal, 17 bytes

IE⌈Eθ№θιΦθ⁼№…θμλι

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

    θ               Input array
   E                Map over elements
     №              Count of
       ι            Current element in
      θ             Input array
  ⌈                 Maximum
 E                  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
I                   Cast to string
                    Implicitly print
\$\endgroup\$
1
\$\begingroup\$

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

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

J, 23 bytes

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

Try it online!

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice! {*} instead of .values saves 4 bytes. \$\endgroup\$ – nwellnhof Dec 24 '19 at 0:09
1
\$\begingroup\$

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!

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

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
}
\$\endgroup\$
  • \$\begingroup\$ Suggest *P-W?++P:printf("%d ",*D++=W,P=E,*P=*D) instead of *P==W?printf("%d ", W),*P=*D,*D++=W,P=E:++P \$\endgroup\$ – ceilingcat Dec 24 '19 at 18:28
1
\$\begingroup\$

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.

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

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

Burlesque, 6 bytes

rasgtp

Try it online!

ra # Read input as array
sg # Sort and group like values
tp # Transpose
\$\endgroup\$
0
\$\begingroup\$

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

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

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.

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