18
\$\begingroup\$

Task

Given a set of n unique elements and a multiset l of positive numbers that add up to n, find all the ways of partitioning those unique elements into disjoint sets with sizes given by the elements of l.

(A multiset is a set that allows repeated elements)

The point here is that we are taking everything in the output as sets, so order doesn't matter in any place.

This may be simpler to understand if you check some test cases below.

Input

The multiset l of positive integers that add up to n. Note that the elements in l may appear repeatedly. This might be given as

  • a list l = [1, 1, 2, 2, 3]
  • arguments to a function f(1, 1, 2, 2, 3)
  • or any other sensible way of representing a multiset

You may assume the representation of l is ordered.

You may also take a list/set/collection of n distinct integers, or you may generate it depending on the sum of the elements in l. If you generate it, you may use any n distinct integers for the set to be partitioned but your remaining code should work for any set of n integers. The set you use must be specified in your answer. Suggestions include:

  • a range starting in 0: [0, 1, ..., n-1]
  • a range starting in 1: [1, 2, ..., n]

Output

The different ways in which your collection can be split in sets with the given sizes. Your output should be unambiguous.

Reference implementation

You can find a vanilla python reference implementation here or you can try it online.

Test cases

I am using the set 0, ..., n-1 when the list adds up to n. In the TIO link, that list is given explicitly to my function.

After the ->, each line represents one possible way of splitting the set.

[1, 1, 1, 1, 1, 1, 1, 1] -> [
    [[0], [1], [2], [3], [4], [5], [6], [7]]
]

[3] -> [
    [[0, 1, 2]]
]

[1, 2] -> [
    [[0], [1, 2]]
    [[1], [0, 2]]
    [[2], [0, 1]]
]

[2, 2] -> [
    [[0, 1], [2, 3]]
    [[0, 2], [1, 3]]
    [[0, 3], [1, 2]]
]

[1, 1, 2] -> [
    [[0], [1], [2, 3]]
    [[0], [2], [1, 3]]
    [[0], [3], [1, 2]]
    [[1], [2], [0, 3]]
    [[1], [3], [0, 2]]
    [[2], [3], [0, 1]]
]

[1, 2, 2] -> [
    [[0], [1, 2], [3, 4]]
    [[0], [1, 3], [2, 4]]
    [[0], [1, 4], [2, 3]]
    [[1], [0, 2], [3, 4]]
    [[1], [0, 3], [2, 4]]
    [[1], [0, 4], [2, 3]]
    [[2], [0, 1], [3, 4]]
    [[2], [0, 3], [1, 4]]
    [[2], [0, 4], [1, 3]]
    [[3], [0, 1], [2, 4]]
    [[3], [0, 2], [1, 4]]
    [[3], [0, 4], [1, 2]]
    [[4], [0, 1], [2, 3]]
    [[4], [0, 2], [1, 3]]
    [[4], [0, 3], [1, 2]]
]

[2, 2, 2] -> [
    [[0, 1], [2, 3], [4, 5]]
    [[0, 1], [2, 4], [3, 5]]
    [[0, 1], [2, 5], [3, 4]]
    [[0, 2], [1, 3], [4, 5]]
    [[0, 2], [1, 4], [3, 5]]
    [[0, 2], [1, 5], [3, 4]]
    [[0, 3], [1, 2], [4, 5]]
    [[0, 3], [1, 4], [2, 5]]
    [[0, 3], [1, 5], [2, 4]]
    [[0, 4], [1, 2], [3, 5]]
    [[0, 4], [1, 3], [2, 5]]
    [[0, 4], [1, 5], [2, 3]]
    [[0, 5], [1, 2], [3, 4]]
    [[0, 5], [1, 3], [2, 4]]
    [[0, 5], [1, 4], [2, 3]]
]

[1, 2, 3] -> [
    [[0], [1, 2], [3, 4, 5]]
    [[0], [1, 3], [2, 4, 5]]
    [[0], [1, 4], [2, 3, 5]]
    [[0], [1, 5], [2, 3, 4]]
    [[0], [2, 3], [1, 4, 5]]
    [[0], [2, 4], [1, 3, 5]]
    [[0], [2, 5], [1, 3, 4]]
    [[0], [3, 4], [1, 2, 5]]
    [[0], [3, 5], [1, 2, 4]]
    [[0], [4, 5], [1, 2, 3]]
    [[1], [0, 2], [3, 4, 5]]
    [[1], [0, 3], [2, 4, 5]]
    [[1], [0, 4], [2, 3, 5]]
    [[1], [0, 5], [2, 3, 4]]
    [[1], [2, 3], [0, 4, 5]]
    [[1], [2, 4], [0, 3, 5]]
    [[1], [2, 5], [0, 3, 4]]
    [[1], [3, 4], [0, 2, 5]]
    [[1], [3, 5], [0, 2, 4]]
    [[1], [4, 5], [0, 2, 3]]
    [[2], [0, 1], [3, 4, 5]]
    [[2], [0, 3], [1, 4, 5]]
    [[2], [0, 4], [1, 3, 5]]
    [[2], [0, 5], [1, 3, 4]]
    [[2], [1, 3], [0, 4, 5]]
    [[2], [1, 4], [0, 3, 5]]
    [[2], [1, 5], [0, 3, 4]]
    [[2], [3, 4], [0, 1, 5]]
    [[2], [3, 5], [0, 1, 4]]
    [[2], [4, 5], [0, 1, 3]]
    [[3], [0, 1], [2, 4, 5]]
    [[3], [0, 2], [1, 4, 5]]
    [[3], [0, 4], [1, 2, 5]]
    [[3], [0, 5], [1, 2, 4]]
    [[3], [1, 2], [0, 4, 5]]
    [[3], [1, 4], [0, 2, 5]]
    [[3], [1, 5], [0, 2, 4]]
    [[3], [2, 4], [0, 1, 5]]
    [[3], [2, 5], [0, 1, 4]]
    [[3], [4, 5], [0, 1, 2]]
    [[4], [0, 1], [2, 3, 5]]
    [[4], [0, 2], [1, 3, 5]]
    [[4], [0, 3], [1, 2, 5]]
    [[4], [0, 5], [1, 2, 3]]
    [[4], [1, 2], [0, 3, 5]]
    [[4], [1, 3], [0, 2, 5]]
    [[4], [1, 5], [0, 2, 3]]
    [[4], [2, 3], [0, 1, 5]]
    [[4], [2, 5], [0, 1, 3]]
    [[4], [3, 5], [0, 1, 2]]
    [[5], [0, 1], [2, 3, 4]]
    [[5], [0, 2], [1, 3, 4]]
    [[5], [0, 3], [1, 2, 4]]
    [[5], [0, 4], [1, 2, 3]]
    [[5], [1, 2], [0, 3, 4]]
    [[5], [1, 3], [0, 2, 4]]
    [[5], [1, 4], [0, 2, 3]]
    [[5], [2, 3], [0, 1, 4]]
    [[5], [2, 4], [0, 1, 3]]
    [[5], [3, 4], [0, 1, 2]]
]

[1, 1, 4] -> [
    [[0], [1], [2, 3, 4, 5]]
    [[0], [2], [1, 3, 4, 5]]
    [[0], [3], [1, 2, 4, 5]]
    [[0], [4], [1, 2, 3, 5]]
    [[0], [5], [1, 2, 3, 4]]
    [[1], [2], [0, 3, 4, 5]]
    [[1], [3], [0, 2, 4, 5]]
    [[1], [4], [0, 2, 3, 5]]
    [[1], [5], [0, 2, 3, 4]]
    [[2], [3], [0, 1, 4, 5]]
    [[2], [4], [0, 1, 3, 5]]
    [[2], [5], [0, 1, 3, 4]]
    [[3], [4], [0, 1, 2, 5]]
    [[3], [5], [0, 1, 2, 4]]
    [[4], [5], [0, 1, 2, 3]]
]

This is the fifth and final challenge of the RGS Golfing Showdown. If you want to participate in the competition, you have 96 hours to submit your eligible answers. Remember there is still 300 reputation in prizes! (See 6 of the rules)

Also, as per section 4 of the rules in the linked meta post, the "restricted languages" for this third challenge are only Sledgehammer, J and Mathematica so submissions in these languages are not eligible for the final prize. But they can still be posted!!

Final prize

If you want to be considered for the final prize, at the end of your answer to this challenge please add a link to the eligible submissions you want to be considered for your final score, as well as the scores those answers got! This way it will be slightly easier for me to keep track of everything. Thanks!

This is still a regular challenge, so enjoy!

\$\endgroup\$
  • \$\begingroup\$ For the first test case why isn't [[0],[1],[2],[3],[4],[5],[7],[6]] valid? \$\endgroup\$ – Expired Data Mar 11 at 11:28
  • 2
    \$\begingroup\$ @ExpiredData My understanding is that the output is a multiset as well, so this would just be a different representation of the same output -- and that would be valid as long as you return only one of them. \$\endgroup\$ – Arnauld Mar 11 at 11:36
  • 1
    \$\begingroup\$ @Arnauld thanks for your feedback. Tbh ordering the representation of l isn't of interest. I say we can assume the representation of l is ordered. \$\endgroup\$ – RGS Mar 11 at 13:25

15 Answers 15

5
\$\begingroup\$

05AB1E, 9 bytes

œεI£€{{}ê

Try it online!

œ           # permutations of the [0, ..., n-1] input
 ε     }    # for each permutation:
  I£        #  cut it in parts of lengths given by the second input
    €{      #  sort each part
      {     #  sort the list of parts
        ê   # sort and uniquify the list of lists of parts
|improve this answer|||||
\$\endgroup\$
  • 4
    \$\begingroup\$ Dang, you make it look so simple!.. :D \$\endgroup\$ – Kevin Cruijssen Mar 11 at 13:59
  • \$\begingroup\$ Hey there, are you competing for the final prize of the RGS Golfing Showdown? If so, please include links to the answers of the previous challenges you want to submit! Thanks :) \$\endgroup\$ – RGS Mar 14 at 22:58
  • 1
    \$\begingroup\$ @RGS no, i'm not. \$\endgroup\$ – Grimmy Mar 15 at 3:07
5
\$\begingroup\$

Python 3, 123 118 114 112 bytes

Input: set s representing a list of n unique elements, and an iterable l representing the multiset.

Output: a set of all partitions, where each partition is a tuple of tuples of elements (aka output is a set of tuples of tuples).

lambda s,l:{(*sorted(p),)for p in product(*(combinations(s,i)for i in l))if{*sum(p,p)}>s}
from itertools import*

Try it online!

Approach

Step 1: For each element i of the multiset l, we find all combinations of i elements of s. We then find the Cartesian products of them. This is the list of candidate partitions.
For example: for l = [1,2], s = ABC, we first find all combinations

  • of 1 element: A, B, C
  • of 2 elements: AB, AC, BC

The candidate partitions are the Cartesian product of the above list of combinations:

[A,AB]
[A,AC]
[A,BC]
[B,AB]
[B,AC]
[B,BC]
[C,AB]
[C,AC]
[C,BC]

Step 2: Filter out the invalid partitions (partitions that do not add up to s).
For the above example, only the following partitions are kept:

[A,BC]
[B,AC]
[C,AB]

Code breakdown

lambda s,l:
{
  (*sorted(p),)                     # convert partition to a sorted tuple (of tuples)
  for p in product(                 # for each candidate partition
    *(combinations(s,i)for i in l)
  )
  if{*sum(p,p)}>s                   # keep only if partition add up to s
}                              # put everything in a set to filter out duplicates

Each partition is stored as a sorted tuple of sorted tuple. This ensure no duplicate in the final result.

{*sum(p,p)}>s checks if a candidate partition is valid (aka contains all element in s). This work by putting all elements in the partition and some extra elements into a set, then check if the set is a superset of s.

For example: for s={0,1,2,3} and valid partition p=((0,1),(2,3)):
sum(p,p) evaluates to ((0,1),(2,3),0,1,2,3), which when converted into set is a superset of s.

For s={0,1,2,3} and invalid partition p=((0,1),(1,2)):
sum(p,p) evaluates to ((0,1),(1,2),0,1,2), which when converted into set becomes {0,1,2,(0,1),(1,2)}, not a superset of s.

|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6),  158 156  141 bytes

Takes input as (a)(r), where \$a\$ is the representation of the input set \$l\$ as an ordered array, and \$r\$ is the range \$[1,2,...,n]\$.

Prints the results.

a=>r=>(F=(k,m,o=[],p,s=[],n=a[k])=>n?s[n-1]?F(++k,m,[...o,s],a[k]-n?0:s[0]):r.map(i=>i<p|m>>i&1||F(k,m|1<<i,o,i,[...s,i])):console.log(o))(0)

Try it online!

Commented

a =>                      // a[] = ordered representation of the input set
r => (                    // r[] = range [1, 2, ..., n]
  F = (                   // F is a recursive function taking:
    k,                    //   k = index of the current entry in a[]
    m,                    //   m = bitmask of values already assigned in the output
    o = [],               //   o[] = output
    p,                    //   p = either 0 or a previous value (as a lower bound)
    s = [],               //   s[] = array representing the current set
    n = a[k]              //   n = k-th entry in a[]
  ) =>                    //
    n ?                   // if n is defined:
      s[n - 1] ?          //   if the current set is not full:
        F(                //     do a recursive call:
          ++k,            //       increment k
          m,              //       pass m unchanged
          [...o, s],      //       append s[] to o[]
          a[k] - n ? 0    //       set p to 0 if the next set has a different size
                   : s[0] //       or to s[0] if it has the same size
        )                 //     end of recursive call
      :                   //   else:
        r.map(i =>        //     for each value i in the range r[]:
          i < p |         //       abort if i is less than p
          m >> i & 1 ||   //       or the i-th bit is already set in m
          F(              //       otherwise, do a recursive call:
            k,            //         pass k unchanged
            m | 1 << i,   //         set the i-th bit in m
            o,            //         pass o unchanged
            i,            //         set p to i
            [...s, i]     //         append i to s[]
          )               //       end of recursive call
        )                 //     end of map()
    :                     // else:
      console.log(o)      //   leaf node: print o[]
)(0)                      // initial call to F with k = 0

Previous answers

  • RGS 1/5 - JavaScript, 37 bytes
  • RGS 2/5 - CP-1610 machine code, 28 bytes (or 27.5)
  • RGS 3/5 - JavaScript, 79 bytes
  • RGS 4/5 - JavaScript, 206 bytes

Total score: 491 bytes

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for your JS submission. I take it you don't want to be considered in the final leaderboard? \$\endgroup\$ – RGS Mar 11 at 16:40
  • \$\begingroup\$ @RGS Not that it really matters, but I've added links to my previous entries. \$\endgroup\$ – Arnauld Mar 11 at 17:08
3
\$\begingroup\$

Wolfram Language (Mathematica), 63 bytes

Uses the range [1,2,...,n]

Union[Sort/@(Sort/@#~TakeList~a&/@Permutations@Range@Tr[a=#])]&

Try it online!

|improve this answer|||||
\$\endgroup\$
3
+100
\$\begingroup\$

Jelly, 16 15 13 bytes

Œ!ṁ€R}Ṣ€Ṣ¥€ṢQ

-2 bytes thanks to @NickKennedy by golfing the loose link to an inline one with }.

Try it online.

Explanation:

Œ!ṁ€R}Ṣ€Ṣ¥€ṢQ  # Main link taking two list arguments
               # i.e. left=[0,1,2,3,4]; right=[1,2,2]
Œ!             #  Get all permutations of the (implicit) left argument
               #   i.e. [0,1,2,3,4] → [[0,1,2,3,4],[0,1,2,4,3],...,[4,3,2,1,0]]
     }         #  Turn a monad into a dyad by using the right argument:
    R          #   Create a range of each inner integers
               #    i.e. [1,2,2] → [1,[1,2],[1,2]]
  ṁ€           #   And mold each permutation based on that
               #    i.e. [3,0,2,4,1] and [1,[1,2],[1,2]] → [3,[0,2],[4,1]]
          €    #  Map,
         ¥     #  using the previous two links as dyad:
      Ṣ€       #   Sort each inner-most list
               #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[4,[2,3],[0,1]]]
        Ṣ      #   Then sort each inner list
               #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,1],[2,3],4]]
           Ṣ   #  And after the map, sort the outer list
               #   → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,4],[1,3],2]]
            Q  #  And uniquify it
               #   → [[0,[1,2],[3,4]],[0,[1,3],[2,4]],...,[[0,4],[1,3],2]]
               #  (after which the result is output implicitly)

Original 16 15 bytes answer:

⁹R⁸ṁ
Œ!çṢ€Ṣɗ€ṢQ

First (semi-complex) Jelly answer, so can definitely be golfed.. I probably can't find the builtins I'm looking for, since I have the feeling there should be a builtin for ⁹R⁸ṁ similar as 05AB1E's £.
Port of the approach used by @Grimmy in his 05AB1E answer.

Try it online.

Explanation:

⁹R⁸ṁ        # Define a link taking two list arguments
            # i.e. left=[1,2,2]; right=[3,0,2,4,1]
⁹           #  Use the left argument
 R          #  And create a range of each inner integers
            #   i.e. [1,2,2] → [1,[1,2],[1,2]]
  ⁸         #  Then take the right argument
   ṁ        #  And mold it based on the earlier list
            #   i.e. [3,0,2,4,1] and [1,[1,2],[1,2]] → [3,[0,2],[4,1]]

Œ!çṢ€Ṣɗ€ṢQ  # Main link taking two list arguments
            # i.e. left=[0,1,2,3,4]; right=[1,2,2]
Œ!          #  Get all permutations of the (implicit) left argument
            #   i.e. [0,1,2,3,4] → [[0,1,2,3,4],[0,1,2,4,3],...,[4,3,2,1,0]]
       €    #  Map,
      ɗ     #  using the previous three links as dyad:
  ç         #   Apply the link we defined above,
            #   which uses this main-link's right as left argument for the helper-link
            #    → [[0,[1,2],[3,4]],[0,[1,2],[4,3]],...,[4,[3,2],[1,0]]]
   Ṣ€       #   Sort each inner-most list
            #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[4,[2,3],[0,1]]]
     Ṣ      #   Then sort each inner list
            #    → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,1],[2,3],4]]
        Ṣ   #  And after the map, sort the outer list
            #   → [[0,[1,2],[3,4]],[0,[1,2],[3,4]],...,[[0,4],[1,3],2]]
         Q  #  And uniquify it
            #   → [[0,[1,2],[3,4]],[0,[1,3],[2,4]],...,[[0,4],[1,3],2]]
            #  (after which the result is output implicitly)

And not that it matters, but my other RGS Golfing Showdown answers are:

Total score: 466 bytes

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ A solid 1st submission and a solid final submission! Then a lot of really interesting submissions, only not in competitive languages. Does this make sense? \$\endgroup\$ – RGS Mar 11 at 16:42
  • \$\begingroup\$ My alternative 10 byter is what I think you were going for. However, I found a slightly shorter solution using combinations. \$\endgroup\$ – Nick Kennedy Mar 11 at 19:07
  • \$\begingroup\$ @NickKennedy Are you sure yours are correct, though? You seem to have more outputs than I have. \$\endgroup\$ – Kevin Cruijssen Mar 11 at 19:57
  • 1
    \$\begingroup\$ Happy with you using it. I’ll check why you’re getting a different answer for mine. \$\endgroup\$ – Nick Kennedy Mar 11 at 20:07
  • 1
    \$\begingroup\$ @KevinCruijssen fixed at a cost of 3 bytes. Mine originally only worked where the set lengths were unique. \$\endgroup\$ – Nick Kennedy Mar 11 at 21:49
3
\$\begingroup\$

Jelly, 12 bytes

œcŒpFQƑ$ƇṢ€Q

Try it online!

A dyadic link taking the list of \$n\$ integers as the left argument and the list of set lengths as the right. Returns a list of lists.

Thanks to @KevinCruijssen for pointing out an omission in my original answer.

Previous RGS submissions:

  1. Jelly 12 bytes
  2. BBC BASIC V 92 bytes
  3. Jelly 37 bytes
  4. R 128 bytes
  5. Jelly 12 bytes (this post)

Total: 281 bytes

|improve this answer|||||
\$\endgroup\$
3
+200
\$\begingroup\$

Jelly, 12 bytes

œcŒpṢ€FQƑ$ƇQ

Try it online!


Overal RGS admissible competition entries:

RGS 1/5 - Jelly, 7
RGS 2/5 - Husk, 22
RGS 3/5 - Jelly, 36
RGS 4/5 - MATL, 26 *
This: 12

Total = 103 bytes

* Might be 25, but I haven't proven that the 25 would never yield multiple results

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Interesting that we converged in almost the same answer again. I added the Ṣ€Q to my original 9-byter without seeing yours! \$\endgroup\$ – Nick Kennedy Mar 11 at 21:55
  • \$\begingroup\$ Oh, nice; I tried œ!Œp for a while but then realised œcŒp would do some of the filtering for me for free. \$\endgroup\$ – Jonathan Allan Mar 11 at 22:07
  • 1
    \$\begingroup\$ @KevinCruijssen thanks, I've fixed the link \$\endgroup\$ – Jonathan Allan Mar 12 at 15:10
  • 1
    \$\begingroup\$ Congratulations on winning the RGS competition, I hope you had some fun! \$\endgroup\$ – RGS Mar 29 at 19:36
2
\$\begingroup\$

05AB1E, 18 17 bytes

œ€.œ€`€€{ʒ€gQ}€{Ù

Try it online!, or verify some test cases


Explanation

                                     - Takes input of the numbers [1..N]
œ                                    - Permutations of this list
 €.œ                                 - Partitions of each of these permutations
    €`                               - Flatten these 1 level
      €€{                            - Sort the lists in each list in each partition
        ʒ                            - Filter the partitions 
          €g                         - Where the size of the sub partitions...
            Q}                       - Equal to the second input (l)
              €{Ù                    - Sort and uniquify these
                                     - Output implicitly

Submissions for consideration

(4/5) Sledgehammer 6 bytes

(3/5) 05AB1E 38 bytes

(2/5) C# 76 bytes

(1/5) 05AB1E 6 bytes

Total = 143

|improve this answer|||||
\$\endgroup\$
  • 3
    \$\begingroup\$ As of now, your code doesn't work! Consider this test case, where should only be 3 outputs but your code returns 6, because it is considering the orderings of the small sets of size 2. Please ping me when you fix this! :) \$\endgroup\$ – RGS Mar 11 at 9:15
  • 1
    \$\begingroup\$ @ExpiredData For starters you can remove the trailing }, so you're indeed correct yours is easier shortened. ;p \$\endgroup\$ – Kevin Cruijssen Mar 11 at 10:04
  • \$\begingroup\$ @Arnauld is this solution working now? \$\endgroup\$ – Expired Data Mar 11 at 11:40
  • 1
    \$\begingroup\$ @ExpiredData Yes, I think so! \$\endgroup\$ – Arnauld Mar 11 at 11:44
  • 1
    \$\begingroup\$ Hey there, just to let you know that you placed 3rd in the RGS! \$\endgroup\$ – RGS Mar 15 at 12:22
2
\$\begingroup\$

Japt -Q, 13 bytes

á £V®Xj0Z ñ
â

Try it

Submissions

(1/5) Japt, 9 bytes

(2/5) CJam, 23 bytes

(3/5) Japt, 40 or 41 bytes (I don't know which one to use, I'm not sure if the 40 byte one is valid)

(4/5) Magma, 34 bytes

Total Score: 120 (or maybe 119)

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

J, 47 bytes

[:~.~:@I.(/:(#,])&.>)@(<@/:~;.1)"1[:(!A.&i.])+/

Try it online!

I entirely missed the Portuguese one, so I'm out of the final prize anyway.

And J is not so good for handling non-rectangular arrays.

How it works

[:~.~:@I.(/:(#,])&.>)@(<@/:~;.1)"1[:(!A.&i.])+/

[:(!A.&i.])+/    NB. all permutations of 0..n-1
           +/    NB. sum of l, i.e. the value of n
  (   &i.])      NB. array of 0..n-1
   !  &i.        NB. array of 0..n!-1
    A.           NB. (0..n!-1)-th permutations of 0..n-1

~:@I.    NB. cut vector (1 2 3 -> 1 1 0 1 0 0)
   I.    NB. for each number k at index i, k copies of i
         NB. e.g. 1 2 3 -> 0 1 1 2 2 2
~:@      NB. nub sieve; does each item appear for the first time?

(/:(#,])&.>)@(<@/:~;.1)"1    NB. cut, sort each item, and sort each row
                       "1    NB. on each row...
             (     ;.1)    NB. cut to the lengths of l
                           NB. e.g. 1 1 0 (f;.1) 0 1 2 -> (f 0)(f 1 2)
              <@/:~        NB. sort each item and enclose
(          )@     NB. then...
 /:               NB. sort the row by...
   (   )&.>       NB. the result applied to each item x...
    #,]           NB. the length of x, followed by x itself
                  NB. that is, sort by lengths then content

[:~.    NB. finally, remove duplicate rows to get the answer
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Husk, 14 bytes

u→SġÖȯLuΣmOΠMṖ

Try it online!

...I feel like the →SġÖȯLuΣ (last-entry-of hook group-by sort-by compose length deduplicate concatenated) should be XȯLuΣ where X is "maximals-by-predicate", saving 3 bytes, but I can't seem to find such a high-level-function. Maybe I'm being blind?

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Are you going to compete for the final prize? \$\endgroup\$ – RGS Mar 12 at 12:35
  • \$\begingroup\$ Yep, thanks - I've updated my Jelly answer. \$\endgroup\$ – Jonathan Allan Mar 12 at 13:48
  • \$\begingroup\$ Hey there, just to let you know that you won the RGS! \$\endgroup\$ – RGS Mar 15 at 12:20
1
\$\begingroup\$

GAP, 145 127 105 bytes

f:={l,c}->(i->Orbit(SymmetricGroup(c),Set(l,n->Set([1..n],k->NextIterator(i))),OnSetsSets))(Iterator(c));

Try it online!

This is absurdly long, but I like computing the answer as an orbit of a group action. I have mixed feelings about creating the first element using an Iterator...

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ What is the "first element" and the "Iterator"? If that Iterator(PositiveIntegers) is just "a list of the first positive integers" to be the elements of the set of sets, you can take it as input. \$\endgroup\$ – RGS Mar 12 at 10:16
  • \$\begingroup\$ @RGS By "first element" I mean the expression Set(l,n->Set([1..n],k->NextIterator(i))) which e.g. for input [1,1,4] computes [[1],[2],[3,4,5,6]]. It is the starting point for the Orbit computation, The Iterator i here is an object that on each call of NextIterator gives me the next unused positive integer. \$\endgroup\$ – Christian Sievers Mar 12 at 10:30
1
\$\begingroup\$

Pyth, 20 bytes

{SMfqQlMTSMMs./M.pUs

Try it online!

Explanation

{SMfqQlMTSMMs./M.pUsQ # full program (Q=input, last one is implicit)
                  UsQ # range(sum(Q))
                .p    # get all permutations
            s./M      # for each permutation, get all partitions, concatenate to one list
         SMM          # sort each list in each partition
   f                  # keep only the partitions T where
    qQ                # Q ==
      lMT             #      map each list in a partition T to its length
 SM                   # now sort the filtered partitions
{                     # and deduplicate
|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

R (with partitions library), 86 bytes

function(l,n)lapply(partitions::listParts(n),function(x)if(all(lengths(x)==l))show(x))

Try it online at RDRR!

Assumes that l is sorted in decreasing order. Will print a lot of fluff after the answer, so I advise to call invisible(f(l, n)) rather than f(l, n).

The function listParts lists all the partitions of 1:n; they are then filtered to keep only those whose lengths match the values of l.

Previous submissions, all in R (not that R is a competitive language!):

  1. 38 bytes
  2. 73 bytes (also SPL, 398 bytes)
  3. 111 bytes
  4. 68 bytes

Total: 376 bytes

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 95 bytes

⊞υE⊕⌈θE№θι⟦⟧Fη«≔υζ≔⟦⟧υFζFLκF∨⊕⌕§κλ⟦⟧№θλ¿‹L§§κλμλ⊞υEκ⎇⁻ξλνEν⎇⁻ρμπ⁺π⟦ι⟧»≔⟦⟧ζFυ«≔⟦⟧εFιFκ⊞ελ⊞ζε»⪫ζ¶

Try it online! Link is to verbose version of code. I don't often get to use the r variable; I think this might be only the second time ever. Takes the set counts and unique entries as arguments. Explanation:

⊞υE⊕⌈θE№θι⟦⟧

Make a list of lists of sets (also actually lists), where each element of that list will have a number of sets equal to the count of occurrences of that index in the input set counts, and push that list to the predefined empty list, which is now technically a list of lists of lists of lists.

Fη«

Loop over the unique entries.

≔υζ≔⟦⟧υ

Move the list of lists of lists of sets into a temporary variable so that it can be cleared to accumulate the results of this pass.

Fζ

Loop over each list of lists of sets from the previous pass.

FLκ

Loop over each possible set count.

F∨⊕⌕§κλ⟦⟧№θλ

Loop over each set, but if there is more than one empty set then stop at the first.

¿‹L§§κλμλ

Ignore this set if it's full.

⊞υEκ⎇⁻ξλνEν⎇⁻ρμπ⁺π⟦ι⟧

Construct a new list of lists of sets by replacing the one at the current set count with a new list of sets constructed by replacing the current set by union with the current unique entry. This is done to ensure that the new lists are all clones.

»≔⟦⟧ζFυ«≔⟦⟧εFιFκ⊞ελ⊞ζε»

Flatten each list of lists of sets in the resulting list into a list of sets.

⪫ζ¶

Output the list of lists of sets in a human-readable manner. (This only costs 1 byte, so I think it's fair.)

Submission history:

(1/5) Charcoal, 19 bytes (Retina 0.8.2, 68 bytes)

(2/5) Charcoal, 31 bytes (Retina, 74 bytes)

(3/5) vi, 48 bytes (Charcoal, 50 bytes; Batch, 265 bytes)

(4/5) Charcoal, 41 bytes

(5/5) Charcoal, 95 bytes

Total score: 234 bytes

Total Charcoal score: 236 bytes

Wooden Spoon score: 543 bytes

|improve this answer|||||
\$\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.