Questions tagged [combinatorics]
For challenges involving combinatorics.
353
questions
51
votes
2
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 ...
- 194k
50
votes
47
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 ...
- 138k
47
votes
8
answers
5k
views
Determine if a coin system is Canonical
The Cashier's Algorithm is an algorithm for making change in the minimal number of coins that works quite well for most currency systems. However like most greedy algorithms it is not without its ...
- 89.4k
43
votes
21
answers
3k
views
Has My Pie Been Bisected?
Write a program or function that takes in a nonempty list of positive integers. You may assume it is input in a reasonable convenient format such as "1 2 3 4" or <...
- 88.2k
42
votes
64
answers
9k
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 ...
- 7,672
40
votes
45
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 ...
- 491
40
votes
54
answers
7k
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 ...
- 11k
40
votes
8
answers
3k
views
Lazy battleship placement
Imagine the following scenario: you are playing battleships with a friend but decide to cheat. Rather than moving a ship after he shoots where your ship used to be, you decide not to place any ships ...
- 9,472
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
39
votes
10
answers
5k
views
The Urinal Protocol
Background
The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in this xkcd ...
- 2,919
35
votes
21
answers
8k
views
Amount of permutations on an NxNxN Rubik's Cube
Introduction:
A 3x3x3 Rubik's Cube has \$43,252,003,274,489,856,000\$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually ...
- 107k
33
votes
23
answers
4k
views
Brute-force the switchboard
The other day, our team went to an escape room. One of the puzzles involved a board of six mechanical switches where you had to find the correct combination of on and off in order to unlock a box, ...
32
votes
6
answers
2k
views
Tic-tac-toe with only crosses
Introduction
Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only going to use crosses. The first person who places three crosses in a row ...
- 43.4k
32
votes
7
answers
3k
views
Longest domino chain
Challenge description
Dominoes is a game played with tiles with two values on it - one on the left, one on the right, for example [2|4] or ...
- 5,442
31
votes
17
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 ...
- 41.4k
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
31
votes
15
answers
3k
views
List all multiplicative partitions of n
Given a positive number n, output all distinct multiplicative partitions of n in any convenient format.
A multiplicative partition of n is a set of integers, all greater than one, such that their ...
- 38.8k
30
votes
13
answers
4k
views
Absolute Sums of Sidi Polynomial Coefficients
Background
The Sidi polynomial of degree \$n\$ – or the \$(n + 1)\$th Sidi polynomial – is defined as follows.
$$S_n(x) = \sum^n_{k=0}s_{n;k}x^n \text{ where } s_{n;k} = (-1)^k\binom n k (k+1)^n$$
The ...
- 207k
30
votes
7
answers
4k
views
Which Friends characters were really the best friends?
The six main cast members of the American sitcom Friends all agreed that they would be paid the same salary throughout the run of the series (after season 2, at least). But that doesn't mean that they ...
- 88.2k
29
votes
31
answers
3k
views
Deranged !Combinatorics: Compute the Subfactorial
The subfactorial or rencontres numbers (A000166) are a sequence of numbers similar to the factorial numbers which show up in the combinatorics of permutations. In particular the nth subfactorial !n ...
- 194k
29
votes
18
answers
7k
views
Don't repeat yourself in Rock-Paper-Scissors
Upon the rumor that Codegolf will have a Rock-Paper-Scissors tournament you look into the topic of square-free words. A word made of the letters R, ...
- 1,717
29
votes
20
answers
4k
views
Vampire Compatibility
A little known fact about vampires is that they must drink the blood of victim that has a compatible donor blood type. The compatibility matrix for vampires is the same as the regular red blood cell ...
- 69.4k
29
votes
4
answers
933
views
Arranging Bubbles
Note, challenge copied from question asked at math.stackexchange.
Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this:
But then things started getting ...
- 11.4k
29
votes
4
answers
1k
views
Smallest region of the plane that contains all free n-ominoes
On Math Stack Exchange, I asked a question about the smallest region that can contain all free n-ominos.
I'd like to add this sequence to the On-Line Encyclopedia of Integer Sequences once I have ...
- 8,117
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.6k
28
votes
3
answers
1k
views
Stuffing primes in a box
Your task is write a program or function that can fill a given rectangle with
prime numbers. The width and height of the ...
- 6,732
28
votes
1
answer
2k
views
Figure Out the Android Lock Pattern
Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend ...
- 89.4k
27
votes
45
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 ...
- 371
27
votes
21
answers
1k
views
Number of Straight-Chain Alk*nes of given length
A straight-chain alk*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or triple bonds (alkyne), (implicit hydrogens are used.) Carbon atoms can only form 4 ...
- 5,992
27
votes
17
answers
3k
views
Compute the multinomial coefficient
Time for another easy challenge in which all can participate!
The multinomial theorem states:
The expression in parentheses is the multinomial coefficient, defined as:
Allowing the terms ki to ...
- 4,087
27
votes
17
answers
1k
views
Sums of prime factors
2013 has the prime factorization 3*11*61. 2014 has the prime factorization 2*19*53. An interesting property regarding these ...
- 7,219
27
votes
10
answers
1k
views
Hook length product
A Young diagram is an arrangement of boxes in left-justified rows and top-justified columns. For each box, all the spaces above it and to its left are occupied.
...
- 138k
27
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 ...
- 763
27
votes
2
answers
1k
views
Golf me some cash from the ATM
The task is simple. Get me some 1000, 500 and 100 notes.
How ? you might ask. Don't worry, ...
- 26.3k
27
votes
1
answer
1k
views
Find Diffy Games
A fun game to play if you are bored is the Diffy Game. It is a one player game that is pretty simple and can consume a good deal of your time.
The Diffy game works like as follows: You start with a ...
- 89.4k
26
votes
10
answers
3k
views
The square root of the square root of the square root of the…
This code-golf challenge will give you an integer n, and ask you to count the number of positive integer sequences \$S = (a_1, a_2, \dots, a_t)\$ such that
\$a_1 + ...
- 8,117
26
votes
23
answers
2k
views
Case Permutation
Who needs to compare things case insensitively when you're able to generate every permutation of uppercase and lowercase? No one! That's the answer. No one does. Your task is to achieve this feat; ...
- 3,145
26
votes
24
answers
3k
views
Arbitrary Randomness
Randomness is fun. Challenges with no point are fun.
Write a function that, given integer input n, will output a set (unordered, unique) of exactly ...
- 11.2k
26
votes
6
answers
1k
views
Enumerate rhyme schemes
A "rhyme scheme" is a string of letters a to z, such that the first occurrences of the characters are in ascending order (...
- 194k
26
votes
2
answers
2k
views
Extend the most recent "nice" OEIS sequence: stepping stone puzzle on a grid
Today Neil Sloane of the OEIS sent out an email asking for a confirmation of the current terms, and computation of some larger terms of the latest OEIS sequence A337663 with the keyword "nice&...
- 8,117
26
votes
6
answers
2k
views
The Coin Problem
Background
The official currency of the imaginary nation of Golfenistan is the foo, and there are only three kinds of coins in circulation: 3 foos, 7 foos and 8 foos.
One can see that it's not ...
- 42.2k
26
votes
8
answers
2k
views
Generate the shortest De Bruijn
A De Bruijn sequence is interesting: It is the shortest, cyclic sequence that contains all possible sequences of a given alphabet of a given length. For example, if we were considering the alphabet A,...
- 14.2k
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
25
votes
14
answers
3k
views
Reuse your code!
In this challenge we try to solve two important problems at once. They are:
Given integers \$a\$ and \$b\$, tell if \$a^b-1\$ is a prime number.
Given integers \$a\$ and \$b\$, return \$a\choose b\$.
...
- 5,067
25
votes
9
answers
905
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.2k
25
votes
1
answer
2k
views
Android Lock Screen
Intro
You are sitting in a board room at the end of a long table. You look around and see Tim Cook, the Apple Board of Directors, the ghost of Steve Jobs, and Jack Donaghy. Apple has called this ...
- 351
25
votes
1
answer
823
views
Maximal discrepancy-2 sequence with minimal entropy
Background
As noted in the PPCG challenge Compress a maximal discrepancy-2 sequence – which inspired this challenge – the authors of the paper Computer-Aided Proof of Erdős Discrepancy Properties ...
- 207k
24
votes
62
answers
3k
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
24
votes
34
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)\$. ...
- 15.1k
24
votes
16
answers
3k
views
Triangular domino tiling of an almost regular hexagon
Background
An almost regular hexagon is a hexagon where
all of its internal angles are 120 degrees, and
pairs of the opposite sides are parallel and have equal lengths (i.e. a zonogon).
The ...
- 64.8k