Questions tagged [combinatorics]
For challenges involving combinatorics.
366
questions
19
votes
14
answers
2k
views
Rook Polynomials
In combinatorics, the rook polynomial \$R_{m,n}(x)\$ of a \$m \times n\$ chessboard is the generating function for the numbers of arrangements of non-attacking rooks. To be precise:
$$R_{m,n}(x) = \...
- 45.6k
5
votes
3
answers
319
views
Valid python function invocation signatures
Background
In Python, function arguments are defined within the parentheses following the function name in the function definition. There are different ways to present function arguments, and they can ...
- 181
10
votes
3
answers
319
views
Representing a number as an unordered list of smaller numbers
Suppose we want to encode a large integer \$x\$ as a list of words in such a way that the decoder can recover \$x\$ regardless of the order in which the words are received. Using lists of length \$k\$ ...
- 621
0
votes
1
answer
267
views
Generate all possible equations from a list of numbers [closed]
This is my first codegolf post so let me know if I have missed anything. Thanks :)
Description
You are given a list of numbers with 2 < n <= 6 length i.e. [1, ...
- 21
12
votes
15
answers
1k
views
The number of solutions to Hertzsprung's Problem
Hertzprung's Problem (OEIS A002464) is the number of solutions to a variant of the Eight Queens Puzzle, where instead of placing \$n\$ queens, you place \$n\$ rook-king fairy pieces (can attack like ...
- 8,258
13
votes
11
answers
2k
views
String Concatenate
You are given a string \$s\$ of characters from a to z. Your task is to count how many unique strings of length \$n\$ you can make by concatenating multiple prefixes of the string \$s\$ together.
...
- 1,180
16
votes
8
answers
2k
views
We're gonna need a bigger podium!
If \$R\$ runners were to run a race, in how many orders could they finish such that exactly \$T\$ runners tie?
Challenge
Given a positive integer \$R\$ and a non-negative integer \$0\leq T\leq {R}\$ ...
- 102k
13
votes
15
answers
1k
views
A Fine sequence with fine interpretations
The ubiquitous Catalan numbers \$C_n\$ count the number of Dyck paths, sequences of up-steps and down-steps of length \$2n\$ that start and end on a horizontal line and never go below said line. Many ...
- 3,707
10
votes
6
answers
735
views
CGAC2022 Day 13: Santa's gift and the laser lock, Part 2
Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
You successfully route the laser into the sensor, but nothing happens.
"What?" Frustrated, you flip the ...
- 73.2k
20
votes
10
answers
893
views
Counting Stripey Bracelets
A bracelet consists of a number, \$\mathit{N}\$, of beads connected in a loop. Each bead may be any of \$\mathit{C}\$ colours. Bracelets are invariant under rotation (shifting beads around the loop) ...
- 102k
20
votes
7
answers
2k
views
The smallest area of a convex grid polygon
I got an email from Hugo Pfoertner, an Editor-in-Chief at the On-Line Encyclopedia of Integer Sequences, with a terrific idea for a fastest-code challenge, which will also help verify or expand the ...
- 8,649
15
votes
14
answers
2k
views
Find a word in the dictionary of all possible words
Given an alphabet represented as a nonempty set of positive integers, and a word made up of symbols from that alphabet, find that word's position in the lexicographically ordered set of all words, ...
- 2,435
15
votes
10
answers
1k
views
Count Futoshiki row solutions
Futoshiki is a logic puzzle where an \$n×n\$ Latin square must be completed based on given numbers and inequalities between adjacent cells. Each row and column must contain exactly one of each number ...
- 3,707
5
votes
2
answers
257
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 ...
- 3,707
19
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,253
7
votes
5
answers
328
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
24
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:
\$...
- 23.2k
17
votes
15
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 ...
- 34.8k
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 \$ ...
- 22.2k
5
votes
0
answers
252
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 ...
- 5,390
11
votes
14
answers
695
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 ...
- 95.7k
15
votes
13
answers
894
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 ...
- 23.2k
7
votes
1
answer
237
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 ...
- 95.7k
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\}, \...
- 49.3k
14
votes
3
answers
860
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 ...
- 15.6k
25
votes
9
answers
981
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 ...
- 23.2k
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
575
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 ...
- 3,707
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, ...
- 49.3k
31
votes
17
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,649
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 ...
- 23.2k
5
votes
0
answers
126
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 ...
- 5,390
17
votes
2
answers
724
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-...
- 73.2k
32
votes
30
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(...
- 34.8k
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^...
- 23.2k
16
votes
14
answers
969
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 ...
- 45.6k
9
votes
3
answers
574
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,649
20
votes
2
answers
814
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). ...
- 73.2k
25
votes
74
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 ...
- 359
9
votes
7
answers
501
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\}, \{...
- 49.3k
15
votes
6
answers
529
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 ...
- 73.2k
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 ...
- 49.3k
19
votes
3
answers
387
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,649
14
votes
3
answers
309
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 ...
- 73.2k
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 \\ \...
- 23.2k
10
votes
7
answers
410
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
2
answers
520
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
24
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,236
13
votes
5
answers
314
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,559