Skip to main content

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.

Filter by
Sorted by
Tagged with
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 ...
Philippos's user avatar
  • 2,580
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 ...
bsoelch's user avatar
  • 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 ...
leo848's user avatar
  • 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, ...
emanresu A's user avatar
  • 38.8k
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 ...
matteo_c's user avatar
  • 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 ...
Rydwolf Programs's user avatar
7 votes
9 answers
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 ...
Wheat Wizard's user avatar
  • 98.8k
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 ...
Wheat Wizard's user avatar
  • 98.8k
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\}, \...
caird coinheringaahin g's user avatar
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 ...
pxeger's user avatar
  • 23.9k
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 ...
caird coinheringaahin g's user avatar
16 votes
17 answers
837 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 (...
emanresu A's user avatar
  • 38.8k
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. ...
AWO's user avatar
  • 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 [...] ...
Peter Kagey's user avatar
  • 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 ...
caird coinheringaahin g's user avatar
15 votes
14 answers
1k views

Split a number in every way possible way within a threshold

Task Given a positive integer number and a threshold, split into every possible way without generating any numbers above the threshold. Examples Input: 15008 Threshold: 400 Valid Output: ...
DanielMK's user avatar
  • 253
26 votes
21 answers
3k views

Split a number in every possible way

You task here is very simple: Given a positive integer n without leading zeroes as input, split it in all possible ways Examples Input->Output ...
ZaMoC's user avatar
  • 24.9k
20 votes
15 answers
1k views

(RGS 5/5) Computing the set of all set partitions with fixed sizes

Task Given a set of n unique elements and a multiset l of positive numbers that add up to n,...
RGS's user avatar
  • 14.1k
13 votes
3 answers
408 views

Counting the number of restricted forests on the Möbius ladder of length n

OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn. The Challenge The challenge is to write a program that takes an integer as an input ...
Peter Kagey's user avatar
  • 8,689
22 votes
2 answers
606 views

Partition a square grid into parts of equal area

This challenge is based on the following puzzle: You are given an n by n grid with n cells ...
Peter Kagey's user avatar
  • 8,689
18 votes
15 answers
2k views

Split a list into sized chunks, but not counting items failing predicate

Motivation: Sometimes certain items in a list don't count towards your totals. For example, counting plane passengers in rows, where babies sit on a parent's laps. Challenge: write a program to split ...
Tom Viner's user avatar
  • 443
0 votes
4 answers
206 views

Partition it into as few disjoint contiguous increasing subsequences as possible [closed]

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 substrings as possible, such that each substring ...
Optimus Prime's user avatar
14 votes
10 answers
844 views

Decomposing into primes

Given an integer n, return the number of ways that n can be written as a list of prime numbers. For example, 2323 can be written ...
rigged's user avatar
  • 1,543
9 votes
5 answers
451 views

Advent Challenge 6: Transport Dock Relabeling!

<< Prev Next >> Thanks to the PPCG community, Santa managed to sort his presents into the correct order for moving into the transportation dock. Unfortunately, the transportation dock signs are ...
hyper-neutrino's user avatar
  • 42.4k
8 votes
5 answers
237 views

Let's divide a lattice

Let's say we have a n × n lattice; we can then divide the lattice into two sections by drawing a line through the lattice. Everything to one side of the line is in one set and everything else in ...
Wheat Wizard's user avatar
  • 98.8k
16 votes
7 answers
1k views

How many partitions contain only perfect squares?

Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes. Examples ...
hyper-neutrino's user avatar
  • 42.4k
14 votes
6 answers
575 views

Cover a set with multiples

Lets take a set of integers greater than 1 and call it X. We will define S(i) to be the set of all members of X divisible by i where i > 1. Would like to choose from these subsets a group of sets ...
Wheat Wizard's user avatar
  • 98.8k
21 votes
4 answers
496 views

Rectangular difference

In this challenge, you are given two overlapping rectangles, and you need to calculate the rectangles created by removing one from the other. For example, if you remove the red rectangle from the ...
Nathan Merrill's user avatar
15 votes
2 answers
204 views

Find Subset Factors

Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example ...
Wheat Wizard's user avatar
  • 98.8k
11 votes
22 answers
2k views

Generate all Sublist Partitions

Given a non-empty list of integers, output every possible partitioning of the list where each partition is a non-empty sublist. So for the list [1, 2, 3, 4] the ...
mbomb007's user avatar
  • 23.4k
15 votes
23 answers
1k views

Count occurences of a set in a list

Given a non-empty set of strings and a list of strings, find out how many times the set occurs in the list, i.e. how many times you could create the set with items from the list. Every element from ...
Hugo G's user avatar
  • 289
24 votes
4 answers
617 views

Split a grid into a grid

Introduction There is a small village with nothing but a few houses and empty fields. The local bureaucrats want to divide the village into lots so that each lot contains exactly one house, and the ...
Zgarb's user avatar
  • 42.7k
31 votes
15 answers
3k views

List all multiplicative partitions of n

Given a positive number n, output all distinct multiplicative partitions of n in any convenient format. A multiplicative partition of n is a set of integers, all greater than one, such that their ...
orlp's user avatar
  • 39.1k
17 votes
3 answers
7k views

Dobble/SpotIt card generator

Introduction Dobble/SpotIt is a card game, where people have to spot same symbol on pair of cards in shortest time, indicate it and move to next pair. Each card has multiple symbols (8 in normal ...
Artur Biesiadowski's user avatar
24 votes
9 answers
744 views

Smallest number of contiguous monotonic subsequences

A monotonic subsequence is a sequence of numbers \$a_1, a_2, ..., a_n\$ such that $$a_1 \le a_2 \le ... \le a_n \\ \text{or} \\ a_1 \ge a_2 \ge ... \ge a_n$$ ...
shooqie's user avatar
  • 5,652
27 votes
2 answers
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 ...
hyper-neutrino's user avatar
  • 42.4k
24 votes
1 answer
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 ...
flawr's user avatar
  • 43.8k
23 votes
6 answers
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 ...
Peter Taylor's user avatar
  • 43.1k
26 votes
25 answers
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 ...
Adám's user avatar
  • 30.4k
8 votes
7 answers
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, ...
AdmBorkBork's user avatar
  • 43.5k
14 votes
12 answers
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 <...
AdmBorkBork's user avatar
  • 43.5k
10 votes
2 answers
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 ...
Nathan Merrill's user avatar
18 votes
1 answer
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.....
Not that Charles's user avatar
26 votes
6 answers
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 (...
Martin Ender's user avatar
10 votes
2 answers
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....
Zgarb's user avatar
  • 42.7k
19 votes
4 answers
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 ...
Adám's user avatar
  • 30.4k
10 votes
3 answers
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 ...
quintopia's user avatar
  • 4,138
15 votes
2 answers
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 ...
Zgarb's user avatar
  • 42.7k
26 votes
8 answers
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 ...
TanMath's user avatar
  • 1,423
17 votes
7 answers
3k views

Finding sum-free partitions

Executive summary Given input k, find a partition of integers 1 to n into ...
Peter Taylor's user avatar
  • 43.1k