Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
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 ...
Bubbler's user avatar
  • 75.2k
10 votes
6 answers
635 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 ...
Simd's user avatar
  • 2,780
13 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 ...
Aiden Chow's user avatar
  • 13.1k
10 votes
7 answers
573 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 ...
guest4308's user avatar
  • 377
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) = \...
alephalpha's user avatar
  • 47.6k
5 votes
3 answers
397 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 ...
Mardoxx's user avatar
  • 181
10 votes
3 answers
328 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\$ ...
Karl's user avatar
  • 621
0 votes
1 answer
274 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, ...
Kyle Sharp's user avatar
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 ...
bigyihsuan's user avatar
  • 9,218
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. ...
Huỳnh Trần Khanh's user avatar
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}\$ ...
Jonathan Allan's user avatar
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 ...
Parcly Taxel's user avatar
  • 3,717
10 votes
6 answers
740 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 ...
Bubbler's user avatar
  • 75.2k
20 votes
10 answers
898 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) ...
Jonathan Allan's user avatar
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 ...
Peter Kagey's user avatar
  • 8,659
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, ...
Aiden4's user avatar
  • 2,445
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 ...
Parcly Taxel's user avatar
  • 3,717
5 votes
2 answers
272 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 ...
Parcly Taxel's user avatar
  • 3,717
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 ...
Domenico's user avatar
  • 2,263
7 votes
5 answers
336 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 &...
2FaceMan's user avatar
  • 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: \$...
pxeger's user avatar
  • 23.5k
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 ...
emanresu A's user avatar
  • 37.3k
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 \$ ...
dingledooper's user avatar
  • 22.6k
5 votes
0 answers
253 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 ...
Ginger's user avatar
  • 5,430
11 votes
14 answers
703 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 ...
Wheat Wizard's user avatar
  • 97.8k
15 votes
13 answers
984 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 ...
pxeger's user avatar
  • 23.5k
7 votes
1 answer
238 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 ...
Wheat Wizard's user avatar
  • 97.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
14 votes
3 answers
864 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 ...
loopy walt's user avatar
  • 16.6k
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 ...
pxeger's user avatar
  • 23.5k
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 ...
trotzt's user avatar
  • 311
15 votes
4 answers
595 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 ...
Parcly Taxel's user avatar
  • 3,717
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, ...
caird coinheringaahin g's user avatar
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 ...
Peter Kagey's user avatar
  • 8,659
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 ...
pxeger's user avatar
  • 23.5k
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 ...
Ginger's user avatar
  • 5,430
20 votes
3 answers
979 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-...
Bubbler's user avatar
  • 75.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(...
emanresu A's user avatar
  • 37.3k
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^...
pxeger's user avatar
  • 23.5k
16 votes
14 answers
970 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 ...
alephalpha's user avatar
  • 47.6k
9 votes
3 answers
582 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 ...
user avatar
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 ...
Peter Kagey's user avatar
  • 8,659
20 votes
2 answers
822 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). ...
Bubbler's user avatar
  • 75.2k
25 votes
77 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 ...
Nirvana's user avatar
  • 359
9 votes
7 answers
503 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\}, \{...
caird coinheringaahin g's user avatar
15 votes
6 answers
531 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 ...
Bubbler's user avatar
  • 75.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 ...
caird coinheringaahin g's user avatar
19 votes
3 answers
389 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 ...
Peter Kagey's user avatar
  • 8,659
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 ...
Bubbler's user avatar
  • 75.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 \\ \...
pxeger's user avatar
  • 23.5k

1
2 3 4 5
8