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
10
votes
7
answers
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,590
16
votes
19
answers
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
6
votes
7
answers
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
22
votes
8
answers
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, ...
- 39.2k
8
votes
6
answers
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
19
votes
9
answers
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.8k
7
votes
9
answers
330
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 ...
- 99k
21
votes
20
answers
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 ...
- 99k
16
votes
16
answers
1k
views
Divisible subset sums
Inspired by the recent 3Blue1Brown video
Consider, for some positive integer \$n\$, the set \$\{1, 2, ..., n\}\$ and its subsets. For example, for \$n = 3\$, we have
$$\emptyset, \{1\}, \{2\}, \{3\}, \...
- 50.1k
15
votes
28
answers
2k
views
There's more than one way to skin a set
Given a set of positive integers \$ S \$, output the set of all positive integers \$ n \$ such that \$ n \$ can be made by summing a subset of \$ S \$ in more than one different way, i.e., that are ...
- 24k
12
votes
24
answers
2k
views
Third Stirling numbers of the second kind
\$\left\{ n \atop k \right\}\$ or \$S(n, k)\$ is a way of referring to the Stirling numbers of the second kind, the number of ways to partition a set of \$n\$ items into \$k\$ non-empty subsets. For ...
- 50.1k
16
votes
17
answers
838
views
Square chunk my matrix
Your challenge is to write a function/program that takes a matrix of integers m and a number n as input and:
Splits m into n by n chunks
Replaces each chunk with the most common value in that chunk (...
- 39.2k
7
votes
1
answer
292
views
The number of tilings of a grid
Setup:
A block is any rectangular array of squares, specified by its dimensions \$(w,h)\$. A grid is any finite ordered list of blocks. For example, \$\lambda = ((3,2),(3,1),(1,2))\$ defines a grid.
...
- 171
42
votes
0
answers
2k
views
Topologically distinct ways of dissecting a square into rectangles
I was asked by OEIS contributor Andrew Howroyd to post a Code Golf Challenge to extend OEIS sequence A049021.
Would be super great to get a couple more terms for [...] A049021. Kind of thing [...] ...
- 8,689
27
votes
13
answers
6k
views
Is it a vampire number?
Repost and improvement of this challenge from 2011
A vampire number is a positive integer \$v\$ with an even number of digits that can be split into 2 smaller integers \$x, y\$ consisting of the ...
- 50.1k