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
13
votes
3answers
363 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 ...
17
votes
1answer
281 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 ...
17
votes
15answers
1k 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 ...
0
votes
4answers
149 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 ...
14
votes
10answers
808 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 ...
9
votes
5answers
400 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 ...
8
votes
5answers
202 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 ...
16
votes
7answers
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 ...
14
votes
6answers
521 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 ...
20
votes
4answers
363 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 ...
14
votes
2answers
165 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 ...
11
votes
19answers
910 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 ...
15
votes
23answers
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 ...
22
votes
4answers
537 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 ...
26
votes
15answers
1k 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 ...
15
votes
3answers
4k 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 ...
23
votes
8answers
603 views

Smallest number of contiguous monotonic subsequences

Challenge description A monotonic subsequence is a sequence of numbers [a1, a2, ..., an] such that ...
26
votes
2answers
1k 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 ...
22
votes
1answer
1k 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 ...
23
votes
6answers
829 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 ...
26
votes
22answers
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 ...
8
votes
7answers
331 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, ...
15
votes
11answers
525 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 <...
10
votes
2answers
302 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 ...
18
votes
1answer
471 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.....
26
votes
6answers
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 (...
10
votes
2answers
244 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....
15
votes
3answers
233 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 ...
10
votes
3answers
231 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 ...
16
votes
2answers
412 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 ...
24
votes
6answers
541 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 ...
17
votes
7answers
1k views

Finding sum-free partitions

Executive summary Given input k, find a partition of integers 1 to n into ...
15
votes
4answers
456 views

Chunky palindromes

Palindromes are fun, but some of the other strings are starting to feel left out. We can turn those strings into chunky palindromes by splitting them up into palindromic arrays of chunks. For example,...
16
votes
1answer
489 views

Cut a pizza into identical slices

This is what I thought this question was going to be, before I fully read it. A group of code golfers walk into The Nineteenth Bite Pizzeria and order a pizza. It comes in an irregular shape, made of ...
42
votes
8answers
2k views

Dennis, Doorknob, Martin Büttner, Chris Jester-Young - Pizzeria!

Programming Puzzles & Code Golf is about to get a new moderator, Dennis! This challenge is a tribute to him and our other active (or recently active) moderators: Doorknob, Martin Büttner, and ...
12
votes
2answers
444 views

Pair Capacitors

Capacitors are notorious for being manufactured with high tolerances. This is acceptable in many cases, but some times a capacity with tight tolerances is required. A common strategy to get a capacity ...
5
votes
1answer
272 views

all non-empty sublists partitionings of a list

I had to write a code for finding all non-empty sublists partitionings of a list: ...
19
votes
13answers
1k views

Refined Partitions

Consider an array of integers: [1, 0, 9, 1, 3, 8] There are a lot of ways to partition this list into consecutive sublists. Here are three: ...
11
votes
6answers
332 views

Maximum Concatenated Product

We are given a list of integers p1, ..., pk (not necessarily distinct) where each has a value between 1 and 9, inclusive. Using each of the p1, ..., pk exactly once, we can form concatenations of ...
7
votes
5answers
816 views

The Partition Problem - Sorting Stacks of Boxes

Just last night I was reading a book which had a chapter on the Partition Problem; the Partition Problem is basically about splitting a set of numbers into two smaller sets of equal size. To ...
17
votes
7answers
619 views

Sorted Lexical Partition of a Number

The challenge is really simple: given a number, you split its digits into an array of smaller numbers such that the resulting numbers are non-decreasing. The catch is that you have to split it such ...
6
votes
3answers
529 views

Compute the Join and Meet of Partitions

Background In this challenge, a partition of a set S means a collection of nonempty subsets of S, which are mutually disjoint ...
17
votes
10answers
3k views

Partition a map of water flows

This is a challenge on the internet asked by Palantir Technologies in their interviews. A group of farmers has some elevation data, and we’re going to help them understand how rainfall flows over ...
9
votes
5answers
491 views

Partitions of a list

The answer to this question is much too long Your challenge is to write a partitioning function in the smallest number of characters. Input example ...