Questions tagged [combinatorics]
For challenges involving combinatorics.
374
questions
12
votes
9
answers
1k
views
How many ways can you make change?
The "third type of Euler Transform" takes an integer sequence that gives the number of objects of a given weight and outputs a sequences that gives the number of multisets of objects that ...
- 8,811
18
votes
5
answers
1k
views
Ways to paint a backbone on a tree
Say I have some unlabelled tree graph:
I'll define a "backbone" as a path on a graph that can't be extended - both its ends are at terminal vertices. There are three ways to overlay a ...
- 41.6k
5
votes
1
answer
311
views
Dishonest dungeon staff
This is a joint post with https://puzzling.stackexchange.com/questions/126255/dishonest-dungeon-staff
You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal ...
- 151
21
votes
4
answers
2k
views
Avoiding Loops!
Given a collection of coloured laces, what would be the probability, \$P\$, that Alice won't create any loops if, until impossible, they tie two uniformly chosen, free lace ends of differing colours ...
- 109k
14
votes
13
answers
1k
views
Counting rankings
There is a competition with \$n\$ participants in total. Alice is one of the participants. The outcome of the competition is given as a ranking per participant with a possibility of ties; e.g. there ...
- 78.2k
10
votes
6
answers
645
views
Robinson Schensted correspondence
[The explanations of the algorithm come from here. I recommend reading it for a beautiful description of the algorithm.]
This challenge is to implement the Robinson Schensted correspondence.
Input
A ...
- 3,153
14
votes
10
answers
1k
views
Expected number of rounds for this labeling scheme
Task
Here is an interesting math problem:
Let's say that there are \$n\$ indistinguishable unlabeled objects in a bin. For every "round", pull \$k\$ objects randomly out of the bin with ...
- 14k
10
votes
7
answers
591
views
List all words following a pattern
This challenge is to list out all possible words which are built from a pattern of syllables. Words are composed by joining syllables together. Syllables are composed of a number of vowels with some ...
- 1,215
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) = \...
- 49.4k
5
votes
3
answers
420
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
335
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
291
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 ...
- 10.4k
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,188
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}\$ ...
- 109k
13
votes
17
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,935
10
votes
6
answers
755
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 ...
- 78.2k
20
votes
10
answers
905
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) ...
- 109k
20
votes
7
answers
3k
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,811
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,485
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,935
5
votes
2
answers
292
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,935
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,333
7
votes
5
answers
341
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:
\$...
- 24.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 ...
- 41.6k
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.8k
5
votes
0
answers
260
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,780
11
votes
14
answers
721
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 ...
- 99.6k
15
votes
13
answers
1k
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 ...
- 24.2k
7
votes
1
answer
240
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 ...
- 99.6k
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
14
votes
3
answers
868
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 ...
- 16.7k
25
votes
9
answers
1k
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 ...
- 24.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
618
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,935
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, ...
- 50.1k
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,811
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 ...
- 24.2k
5
votes
0
answers
127
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,780
20
votes
3
answers
1k
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-...
- 78.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(...
- 41.6k
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^...
- 24.2k
16
votes
14
answers
975
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 ...
- 49.4k
9
votes
3
answers
588
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,811
20
votes
2
answers
832
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). ...
- 78.2k
28
votes
86
answers
5k
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 ...
- 389
9
votes
7
answers
508
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\}, \{...
- 50.1k
15
votes
6
answers
533
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 ...
- 78.2k