Questions tagged [combinatorics]
For challenges involving combinatorics.
274
questions
48
votes
8answers
4k 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 ...
46
votes
44answers
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 ...
46
votes
2answers
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 ...
43
votes
19answers
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 <...
39
votes
8answers
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 ...
38
votes
45answers
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 ...
38
votes
10answers
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 ...
36
votes
47answers
6k 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 ...
35
votes
52answers
7k 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 ...
35
votes
21answers
6k 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 ...
33
votes
23answers
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
6answers
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 ...
31
votes
7answers
2k 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 ...
30
votes
17answers
2k 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 ...
30
votes
7answers
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 ...
29
votes
3answers
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 ...
28
votes
11answers
3k 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.
The Sidi polynomials have several interesting properties, but so do their coefficients. The ...
28
votes
20answers
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 ...
28
votes
20answers
3k 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 ...
28
votes
14answers
1k 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 ...
27
votes
23answers
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; ...
27
votes
17answers
2k 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 ...
27
votes
18answers
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 ...
27
votes
10answers
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.
...
27
votes
4answers
852 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 ...
27
votes
1answer
990 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 ...
26
votes
6answers
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 (...
26
votes
3answers
813 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 ...
26
votes
2answers
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
votes
1answer
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 ...
25
votes
24answers
2k 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 ...
25
votes
24answers
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 ...
25
votes
1answer
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 ...
24
votes
34answers
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)\$. ...
24
votes
1answer
740 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 ...
23
votes
27answers
2k views
List all ordered partitions of n
The challenge is to list all ordered partitions (composition (combinatorics)) of a given positive integer n. These are the lists of numbers from ...
23
votes
25answers
6k views
Bernoulli Numbers
The Bernoulli numbers (specifically, the second Bernoulli numbers) are defined by the following recursive definition:
Where denotes a combination.
Given a nonnegative integer ...
23
votes
27answers
2k views
Rearranging the sequence
Introduction
Let's observe the following sequence (non-negative integers):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
For example, let's take the ...
23
votes
12answers
2k views
Number of cycles of a permutation
Consider a permutation of the integers 1, ..., n, such as this one for n = 6:
...
23
votes
26answers
2k views
Find The Rank Of A Word
Definition
The rank of a word is defined as the position of the word when all the possible permutations (or arrangements) of its letters are arranged alphabetically, like in a dictionary, no matter ...
23
votes
15answers
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 ...
23
votes
14answers
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 ab-1 is a prime number.
Given integers a and b, return nCr(a, b).
Specifically, you must ...
23
votes
6answers
855 views
Partial factorisations of a positive integer
A collection of positive integers d_1 d_2 ... d_k is a factorisation of a positive integer n if
...
23
votes
5answers
529 views
Determine How many Wheels There Are
Non-math explanation
This is an explanation that is meant to be approachable regardless of your background. It does unfortunately involve some math, but should be understandable to most people with a ...
22
votes
43answers
3k 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 ...
22
votes
15answers
1k 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
...
22
votes
10answers
2k views
Count the number of shortest paths to n
This code challenge will have you compute the number of ways to reach \$n\$ starting from \$2\$ using maps of the form \$x \mapsto x + x^j\$ (with \$j\$ a non-negative integer), and doing so in the ...
22
votes
3answers
833 views
Loop It
Note: The title of this question should be "Loop It", but because title needs to be at least 15 characters, there are some invisible spaces. This note is such that the challenge can be searched for.
...
22
votes
6answers
1k 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,...
22
votes
2answers
795 views
Can you cast the spell?
In Magic: the Gathering, mages (known as "planeswalkers") battle each other by casting spells. Spells cost mana. Five colors of mana exist: White, Blue, Black, Red, and Green, represented as {W}, {U}, ...
