Questions tagged [set-partitions]

For challenges related to the subdivision of a set into smaller disjoint sets. This also includes the subdivision of ordered collections like lists, and non-discrete sets like intervals. Challenges should carefully define the partition concept being used.

62 questions
Filter by
Sorted by
Tagged with
1k views

Night hike partitioning

We want to go on a night hike with the youth group, but of course not everyone has their torch, even though we told them we planned to split up. What options are there for group formation if n teens ...
• 2,580
2k views

Find the fairest partition of a list

Given a list of positive integers, partition the list into two sublists such that the absolute value of the difference of the sums over the two sublists is minimal. The output of the program should be ...
• 6,035
3k views

Help, I can't bloody well memorize this number!

The Brits aren't exactly known for being good at memorizing stuff. That's why scientists need newspaper articles to find those who are, and that's why it shouldn't be a surprise that they forget more ...
• 637
2k views

Write a set as a union of ranges

In this challenge, we define a range similarly to Python's range function: A list of positive integers with equal differences between them. For example, ...
• 38.8k
224 views

Minimum partition with non-empty intersections

Given a set of intervals $\mathcal{I} = \{I_1, \ldots, I_m\}$, where each interval $I_j$ is represented by its bounds $(a_j, b_j)$, find a partition $\mathcal{T}$ of $\mathcal{I}$ of minimal ...
• 6,480
1k views

Is this substring list ambiguous?

Given a set of substrings, such as [ca, ar, car, rd], it's possible to create infinitely many strings by concatting them together. Some examples of this for the ...
• 18.7k
329 views

Incomparable partitions

A partition of a list $A$ is a way of splitting $A$ up into smaller parts, concretely it is list of lists that when concatenated gives back $A$. For example ...
• 98.8k
2k views

Cut along the lines

In this challenge you will take as input a non-empty list of binary values (these can be booleans or integers on the range 0-1), you should output all the ways to partition the list into non-empty ...
• 98.8k
1k views

• 5,652
2k views

Arranging arbitrary rectangles to fill a space

Can these rectangles fill a rectangular space? Given a bunch of rectangles, you are asked whether or not they can be arranged to fill a rectangular space. Specs Given a bunch of arbitrary ...
• 42.4k
3k views

Solve Grid-Tangram

The Tangram is a dissection puzzle made from seven shapes: Five differently sized triangles, a parallelogram and a square. Given a shape, the goal is recreating the shape using all the pieces and ...
• 43.8k
887 views

Partial factorisations of a positive integer

A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if ...
• 43.1k
2k views

Interquartile Mean

Task Given (by any means) a sorted floating point dataset, return (by any means and within 1‰ of the correct value) the interquartile mean. One possible algorithm Discard the lowest and highest ...
• 30.4k
372 views

Largest Distinctly Sum-Free Partition

related and inspired by -- Finding sum-free partitions A set A is defined here as being distinctly sum-free if 1) it consists of at least three elements, ...
• 43.5k
619 views

Ravenity of Cube Distance Numbers

Inspired by this Numberphile entry Background The cube distance numbers of an integer n are defined here as the set of integers that are x³ distance away for a given x. For a simple example, with <...
• 43.5k
431 views

Partition a list!

In this challenge, you need to partition a list, where partitions have a max size, a min size, and a preferred size. I'll be using the notation (min,pref,max) to ...
• 14.5k
530 views

Count the ASCII hamantaschen!

Today is Purim on which one custom is to give out triangle-shaped cookies with filling called hamantaschen (singular: hamantasch). Another custom is to drink heavily. I'm not the most perfect baker.....
• 1,955
1k views

Enumerate rhyme schemes

A "rhyme scheme" is a string of letters a to z, such that the first occurrences of the characters are in ascending order (...
• 197k
285 views

The absent-minded linguist

Background Your friend, a linguist, has recorded and analyzed some simple conversation snippets in various languages. Being quite absent-minded, they have forgotten which language each snippet was in....
• 42.7k
327 views

Remove letters while keeping strings unique

Inspired by this wonderful (based on the number of views and votes) challenge, which, in my humble opinion, has way too few answers. Given (by any means) a list of strings, return (by any means) a ...
• 30.4k
362 views

Find the Intersection of 2 Sets in Unioned Interval Notation

Find the Intersection of 2 Sets in Unioned Interval Notation Given two sets of real numbers described as the union of intervals, output a description of the intersection of these two sets as a union ...
• 4,138
665 views

Partition into increasing subsequences

Specification This challenge is simple to state: your input is a non-empty array of nonnegative integers, and your task is to partition it into as few increasing subsequences as possible. More ...
• 42.7k
667 views

Decimal concatenation of squares

Premise One night, I was just contemplating on numbers. I found out about something unique about numbers like 7, 10, 12, 13, and more. They are squares of squares! Meaning, that when squared, are ...
• 1,423