Skip to main content

Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
52 votes
50 answers
4k views

Count sums of two squares

Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers ...
44 votes
69 answers
10k views

Generate Pascal's triangle

Pascal's triangle is generated by starting with a 1 on the first row. On subsequent rows, the number is determined by the sum of the two numbers directly above it to the left and right. To ...
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 ...
19 votes
23 answers
2k views

How many partitions do I have?

The partition number of a positive integer is defined as the number of ways it can be expressed as a sum of positive integers. In other words, the number of integer partitions it has. For example, the ...
5 votes
1 answer
290 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 ...
16 votes
10 answers
1k views

Total number of topological sorts

For a given DAG (directed acyclic graph), each of its topological sorts is a permutation of all vertices, where for every edges (u,v) in the DAG, u appears before v in the permutation. Your task is to ...
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 ...
23 votes
32 answers
3k views

Code-Golf: Permutations

Write a function that takes as input a set of integers (can be a list, array or any other container with distinct numbers), and outputs the list of all its permutations. Python (95 chars): ...
19 votes
3 answers
535 views

What is the fastest safe way down a mountain?

Intro Help! I'm stuck on a snow-covered mountain and I need to get down as fast as possible, preferably without dying. I have a map showing how high each part of the mountain is above the normal ...
12 votes
8 answers
1k views

Chess960 position generator

Context Chess960 (or Fischer Random Chess) is a variant of chess invented and advocated by former World Chess Champion Bobby Fischer, publicly announced on June 19, 1996 in Buenos Aires, Argentina. ...
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 ...
23 votes
39 answers
3k views

Print all colorings of a 3x3 grid

You have a 3x3 grid. Each cell can be colored black or white. Display all 512 of these colorings. Fewest bytes wins. You can display the grids in any formation as long as they are visually separated ...
41 votes
51 answers
6k views

Every word from babab to zyzyz

Your task is to write a program that will output a readable list of every five letter words with the structure: consonant - vowel - consonant - vowel - consonant The output should be sorted ...
28 votes
4 answers
2k views

Never trust a mastermind

You probably know the game mastermind: The player tries to guess a code of 4 slots, with 8 possible colors - no duplicates this time. Let's call those colors A through H, so possible solutions could ...
20 votes
6 answers
845 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\...
5 votes
3 answers
405 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 ...
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-...
10 votes
6 answers
643 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 ...
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 ...
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 ...
10 votes
7 answers
581 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 ...
15 votes
4 answers
602 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 ...
5 votes
2 answers
280 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 ...
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 ...
31 votes
19 answers
3k views

Motzkin Numbers

The nth Motzkin Number is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0. Here's an illustration of these paths ...
22 votes
19 answers
2k views

Calculate the partitions of N

Your challenge is simple: GIven an integer N, ouput every list of positive integers that sums to N. For example, if the input was 5, you should output ...
17 votes
18 answers
2k views

Computing a specific coefficient in a product of polynomials

Generator functions This gives the context for why this challenge came to life. Feel free to ignore. Generator functions are a nice way of encoding the solution to a problem of combinatorics. You ...
42 votes
0 answers
2k 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 [...] ...
27 votes
37 answers
2k views

Sign-Swapping Sums

Given a nonempty list of positive integers \$(x, y, z, \dots)\$, your job is to determine the number of unique values of \$\pm x \pm y \pm z \pm \dots\$ For example, consider the list \$(1, 2, 2)\$. ...
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) = \...
14 votes
35 answers
1k views

All non-ordered pairs between the elements of an array

Task: Return an array with all possible pairs between the elements of an array. Example From a=["a", "b", "c", "d"]; return ...
20 votes
36 answers
2k views

Mathematical Combination

Write a program that takes an input such as: n,k which then computes: $$\binom n k = \frac {n!} {k!(n-k)!}$$ and then prints the result. A numerical example: ...
11 votes
3 answers
572 views

Count arrays that make unique sets

This question has a similar set up to Find an array that fits a set of sums although is quite different in its goals. Consider an array A of length ...
14 votes
2 answers
1k views

Count how many distance sequences are far from all others

The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. Let P be a binary string of ...
53 votes
4 answers
2k views

Extending OEIS: Counting Diamond Tilings

I promise, this will be my last challenge about diamong tilings (for a while, anyway). On the bright side, this challenge doesn't have anything to do with ASCII art, and is not a code golf either, so ...
28 votes
47 answers
4k views

Shortest power set implementation

Problem definition Print out the powerset of a given set. For example: [1, 2, 3] => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] Each element is to ...
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 ...
43 votes
57 answers
8k views

Catalan Numbers

The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics. The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as <...
11 votes
5 answers
621 views

Arbitrary Randomness (Speed edition)

Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
7 votes
2 answers
522 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 ...
11 votes
3 answers
610 views

Compute OEIS A005434

The task is to compute OEIS A005434 as quickly as possible. Consider a binary string S of length n. Indexing from ...
16 votes
2 answers
424 views

Permutations such that no k+2 points fall on any polynomial of degree k

Description Let a permutation of the integers {1, 2, ..., n} be called minimally interpolable if no set of k+2 points (together ...
14 votes
2 answers
923 views

Counting generalized polyominoes

This challenge will have you count pseudo-polyforms on the snub square tiling. I think that this sequence does not yet exist on the OEIS, so this challenge exists to compute as many terms as possible ...
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 ...
10 votes
3 answers
330 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\$ ...
10 votes
8 answers
2k views

Enumerate all binary trees with n nodes

Given an integer n, enumerate all possible full binary trees with n internal nodes. (Full binary trees have exactly 2 children on every internal node). The tree structure should be output as a pre-...
14 votes
1 answer
661 views

Circular robot instructions

This challenge is based on Project Euler problem 208. Also related to my Math Stack Exchange question, Non-self-intersecting "Robot Walks". You have a robot that moves in arcs which are \$1/...
0 votes
1 answer
282 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, ...
15 votes
8 answers
732 views

Decorate Pascal's Triangle

Although what is a Pascal's triangle is well-known and we already can generate it, the task is now different: Output \$n\$ first lines of the Pascal's triangle as colored bricks. Color number is ...
20 votes
1 answer
763 views

Acyclic orientations of an n-dimensional cube

The goal of this challenge is to check and extend the OEIS sequence A334248: Number of distinct acyclic orientations of the edges of an n-dimensional cube. Take an n-dimensional cube (if n=1, this is ...

1
2 3 4 5
8