Questions tagged [combinatorics]
For challenges involving combinatorics.
353
questions
6
votes
2
answers
176
views
Generate a Kirkman triple system
Given a universe of \$v\$ elements, a Kirkman triple system is a set of \$(v-1)/2\$ classes each having \$v/3\$ blocks each having three elements, so that
every pair of elements appears in exactly ...
- 833
18
votes
9
answers
1k
views
Cryptic Multiplications
Given two non-negative integers e.g. 27, 96 their multiplication expression would be 27 x 96 = 2592.
If now each digits is ...
- 2,153
7
votes
4
answers
270
views
Generate number set with conditions using n numbers
Generate \$T=\{T_1,...,T_x\}\$, the minimum number of \$k\$-length subsets of \$\{1,...,n\}\$ such that every \$v\$-length subset of \$\{1,...,n\}\$ is a subset of some set in \$T\$
Here, \$n > k &...
- 179
19
votes
23
answers
2k
views
Every possible pairing
Given an positive even integer \$ n \$, output the set of "ways to pair up" the set \$ [1, n] \$. For example, with \$ n = 4 \$, we can pair up the set \$ \{1, 2, 3, 4\} \$ in these ways:
\$...
- 22.6k
17
votes
13
answers
1k
views
Enumerate all pure sets
In set theory, a set is an unordered group of unique elements. A pure set is either the empty set \$\{\}\$ or a set containing only pure sets, like \$\{\{\},\{\{\}\}\}\$.
Your challenge is to write a ...
- 31.9k
21
votes
24
answers
3k
views
Consecutive coin flips
This is a cross-post of a problem I posted to anarchy golf: http://golf.shinh.org/p.rb?tails
Given two integers \$ n \$ and \$ k \$ \$ (0 \le k \le n) \$, count the number of combinations of \$ n \$ ...
- 18.6k
5
votes
0
answers
247
views
Sort my Cups︎︎︎︎︎︎︎︎︎︎ [closed]
I have a set of colored plastic cups. They come in four colors: green, yellow, pink, and blue. When I put them on my shelf, I like to stack them in a certain pattern. Your job is, given a list of any ...
- 3,500
12
votes
14
answers
652
views
Increasing permutation trees
For this challenge a "binary tree" is a rooted tree where each node has 0 children (leaf) or 2. The children of a node are unordered, meaning that while you might draw the tree with left ...
- 90.3k
15
votes
13
answers
770
views
Count alternating permutations
An alternating permutation is a permutation of the first \$ n \$ integers \$ \{ 1 ... n \} \$, such that adjacent pairs of values in the permutation alternate between increasing and decreasing (or ...
- 22.6k
7
votes
1
answer
224
views
Find run ascending lists faster
In this question I asked you to determine if a run ascending list could be made. It was code-golf so naturally most the answers are very slow. But what if we want it to be fast. In this challenge I ...
- 90.3k
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\}, \...
- 48.1k
14
votes
3
answers
844
views
Sniff out biased random permutations
The brilliant engineers at <enter company you love to hate> have struck again. This time they've "revolutionised" the generation of random permutations. "Every great invention is ...
- 9,258
25
votes
9
answers
930
views
Generate all groupings
Let's define a grouping as a flat list, which is either:
just 0
2 groupings followed by the literal integer 2
3 groupings ...
- 22.6k
21
votes
14
answers
1k
views
Verify a Superpowerset
A superpowerset (analogous to superpermutation) on \$n\$ symbols is a string over the alphabet \$\{1,2,...,n\}\$ such that every subset of \$\{1,2,...,n\}\$ appears as a substring (in some order). For ...
- 311
15
votes
4
answers
537
views
Output a Steiner quadruple system
A Steiner quadruple system \$SQS(n)\$ is a collection of subsets (blocks) of size 4 of a set \$S\$ of size \$n\$ such that every subset of \$S\$ of size 3 is in exactly one block. It is easy to show ...
- 833
16
votes
13
answers
1k
views
Square-free words of a length
A square-free word is a word consisting of arbitrary symbols where the pattern \$XX\$ (for an arbitrary non-empty word \$X\$) does not appear. This pattern is termed a "square". For example, ...
- 48.1k
31
votes
14
answers
2k
views
Iterate your way to a fraction
I recently learned from a comment by MathOverflow user pregunton that it is possible to enumerate all rational numbers using iterated maps of the form \$f(x) = x+1\$ or \$\displaystyle g(x) = -\frac ...
- 8,117
16
votes
13
answers
1k
views
Number of complete rhyme schemes
A rhyme scheme is the pattern of rhymes at the end of the lines in a poem. They are typically represented using letters, like ABAB. We consider two rhyme schemes ...
- 22.6k
5
votes
0
answers
125
views
Matching fuzzies [closed]
Introduction
Congratulations! You've been selected to do research a a newly discovered animal called a fuzzy, a docile, simple creature that strongly resembles a cotton ball. Fuzzies love to be near ...
- 3,500
18
votes
2
answers
632
views
Counting universal n-ary logic gates
Background
A classical logic gate is an idealized electronic device implementing a Boolean function, i.e. one that takes a certain number of Boolean inputs and outputs a Boolean. We only consider two-...
- 66.1k
28
votes
25
answers
2k
views
Converge to a number
Your challenge is to, given a positive integer n, count up to each digit of it, giving the effect of converging on it.
Basically, count up to the first digit of n by its place value (\$⌊\log_{10}\left(...
- 31.9k
17
votes
11
answers
2k
views
Write a number in overflowed binary
We all know how binary conversion works: the sequence of bits
$$ b_1, b_2, ..., b_{n-1}, b_n $$
encodes the number
$$ b_1 \times 2^{n-1} + b_2 \times 2^{n-2} + ... + b_{n-1} \times 2^1 + b_n \times 2^...
- 22.6k
16
votes
14
answers
960
views
AoCG2021 Day 5: Balancing sleigh with lots of trunks
Part of Advent of Code Golf 2021 event. See the linked meta post for details.
The story continues from AoC2015 Day 24, Part 2.
Here's why I'm posting instead of Bubbler
To recap: Santa gives you the ...
- 37.5k
10
votes
3
answers
556
views
rank and unrank arrays of integers
Consider all arrays of \$\ell\$ non-negative integers in the range \$0,\dots,m\$. Consider all such arrays whose sum is exactly \$s\$. We can list those in lexicographic order and assign an ...
user7467
15
votes
7
answers
3k
views
Make S + S + ... + S as Large as Possible!
Let \$S \subset \mathbb N_{\geq0}\$ be a subset of the nonnegative integers, and let $$
S^{(k)} = \underbrace{S + S + \dots + S}_{k\ \textrm{times}} = \{ a_1 + a_2 + \dots + a_k : a_i \in S\}.
$$
For ...
- 8,117
21
votes
2
answers
783
views
Lean golf: Pascal vs. Fibonacci
The Pascal's triangle and the Fibonacci sequence have an interesting connection:
Source: Math is Fun - Pascal's triangle
Your job is to prove this property in Lean theorem prover (Lean 3 + mathlib). ...
- 66.1k
24
votes
66
answers
4k
views
Implement the hyperfactorial
The objective
Given the non-negative integer \$n\$, output the value of the hyperfactorial \$H(n)\$. You don't have to worry about outputs exceeding your language's integer limit.
Background
The ...
- 349
9
votes
7
answers
492
views
Distinct Subset Sums: Extending A276661
Consider the integer set \$S = \{3, 5, 6, 7\}\$. If we list all \$2^n\$ subsets of \$S\$ (its powerset) and calculate their sums, we get
$$
\mathcal{P}(S) = \{\emptyset, \{3\}, \{5\}, \{6\}, \{7\}, \{...
- 48.1k
15
votes
6
answers
523
views
Counting maximal domino placements
Background
A maximal domino placement (MDP) on a rectangular grid is a non-overlapping placement of zero or more dominoes, so that no more dominoes can be added without overlapping some existing ...
- 66.1k
19
votes
19
answers
5k
views
What's my PIN number?
My PIN number is 1077, but that's too difficult to remember. I know from muscle memory that it's a digit, followed by a different digit, then followed by two of the same digit, which is different to ...
- 48.1k
19
votes
3
answers
378
views
A multiple of n in every base!
In November 2019, Alon Ran published a particularly lovely sequence in the OEIS, A329126:
\$a(n)\$ is the lexicographically earliest string of digits which yields a multiple of \$n\$ when read in any ...
- 8,117
14
votes
3
answers
305
views
Counting uniquely solvable polylinks
Related: Counting polystrips
Background
Link-a-Pix is a puzzle on a rectangular grid, where the objective is to reveal the hidden pixel art by the following rules:
Connect two cells with number N ...
- 66.1k
23
votes
13
answers
1k
views
Generalised multi-dimensional chess knight's moves
Multi-dimensional chess is an extension of normal chess that is played on an 8x8x8x8... "board".
In normal 2D chess, a knight's move is a movement by a vector of \$ \begin{bmatrix} \pm 2 \\ \...
- 22.6k
10
votes
7
answers
402
views
Combinatorial Pipes
You're a plumber working on a house, and there's some pipes that must be connected at weird angles. You have 8°, 11.25°, 22.5°, 45°, and 90° fittings at your disposal, and you want to use as few as ...
- 131
7
votes
1
answer
482
views
Compute the size of intersections of sets
Input
A positive integer N representing the size of the problem and four positive integers v, x, y, z.
Output
This is what your code should compute. Consider a set of N distinct integers and consider ...
user7467
25
votes
19
answers
1k
views
Just Enough Ones
Challenge
Given a positive integer \$n\$, count the number of \$n\times n\$ binary matrices (i.e. whose entries are \$0\$ or \$1\$) with exactly two \$1\$'s in each rows and two \$1\$'s in each column....
- 6,256
13
votes
5
answers
309
views
No More Jockeys - CodeGolf Version
This challenge is inspired by the game No More Jockeys.
The input is a list of tuples of natural numbers (potentially including 0), in some appropriate input format. Starting with player 0 and ...
- 3,247
15
votes
2
answers
395
views
Connecting the Dots: Counting n²-gons in the n×n Grid
The recent volume of MAA's Mathematics Magazine had an article "Connecting the Dots: Maximal Polygons on a Square Grid" by Sam Chow, Ayla Gafni, and Paul Gafni about making (very convex) \$n^...
- 8,117
13
votes
8
answers
1k
views
How often will this test fail?
Preamble
There was a unit test in our codebase which was shuffling a string of length \$52\$ formed from the set of letters \$[A-Z]+[A-Z]\$ and then using the first \$20\$ characters of that shuffled ...
- 93.9k
22
votes
3
answers
547
views
Sticky polyhexes
Background
A polyhex of size \$n\$ is a contiguous shape made from joining \$n\$ unit regular hexagons side-by-side. As an example, the following image (from Wikipedia) contains all 7 distinct ...
- 66.1k
8
votes
3
answers
391
views
Patterns in Permutations
This fastest-code challenge is based partly on this MSE question and exists to extend some OEIS sequences, and create others. If I extend or create sequences based on this challenge, I'll link to this ...
- 8,117
9
votes
2
answers
283
views
Counting polydominoes
Background
A polyomino of size \$n\$ is a contiguous shape made from joining \$n\$ unit squares side by side. A domino is a size-2 polyomino.
A polydomino of size \$2n\$ is defined as a polyomino of ...
- 66.1k
2
votes
0
answers
81
views
Find the number of parenthesis combinations [duplicate]
For example, given 3 sets of parenthesis, you have:
()()()
((()))
()(())
(())()
(()())
= 5 possible combinations.
Challenge
Program must:
• Take 1 number as an ...
18
votes
7
answers
1k
views
Matching ABACABA-type patterns
(This challenge is related to the challenge "Generate the Abacaba sequence.")
Zimin words (also called "sesquipowers") are an important idea in the subject of "combinatorics ...
- 8,117
40
votes
0
answers
1k
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,117
7
votes
11
answers
492
views
Constrained integer partition
Challenge
In this challenge, all numbers are in \$\mathbb{N}_0\$.
Create a function or program that, when given a number \$N\$ and a tuple of \$k\$ numbers \$(n_i)\$ (all ≤ \$N\$), returns the number ...
- 785
18
votes
5
answers
976
views
Count all binary relations
A binary relation on a set \$X\$ is simply a subset \$S \subseteq X \times X\$; in other words, a relation is a collection of pairs \$(x,y)\$ such that both \$x\$ and \$y\$ are in \$X\$. The number of ...
- 8,117
17
votes
2
answers
525
views
Count unrooted, unlabeled binary trees of n nodes
An unrooted binary tree is an unrooted tree (a graph that has single connected component and contains no cycles) where each vertex has exactly one or three neighbors. It is used in bioinformatics to ...
- 66.1k
20
votes
5
answers
791
views
The Caged Circles
This problem will have you analyzing circles drawn on the grid, with the gridlines drawn at integer values of \$x\$ and \$y\$.
Let \$\varepsilon\$ be a very small number (think, \$\varepsilon = 0.0001\...
- 8,117
4
votes
2
answers
399
views
Minimal Pairing
Your program should take two lists, where each entry (a positive integer) represents the number of members of some group, as input. These lists will have the same sum but may have different lengths.
...
- 3,247