Questions tagged [combinatorics]
For challenges involving combinatorics.
353
questions
14
votes
1
answer
618
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/...
- 8,117
15
votes
8
answers
624
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 ...
- 1,212
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
16
votes
1
answer
407
views
Counting symmetric grid chains
Notation and definitions
Let \$[n] = \{1, 2, ..., n\}\$ denote the set of the first \$n\$ positive integers.
A polygonal chain is a collection of connected line segments.
The corner set of a ...
- 8,117
16
votes
6
answers
766
views
Roman Numeral Counting
Roman numerals can be (mostly) written in a one column format, because each letter intersects the top and the bottom of the line. For example: I, or 1 intersects ...
- 3,583
8
votes
3
answers
251
views
Multigraphs with a given degree sequence
This challenge will give you an input of a degree sequence in the form of a partition of an even number. Your goal will be to write a program that will output the number of loop-free labeled ...
- 8,117
17
votes
2
answers
866
views
Number of distinct tilings of an n X n square with free n-polyominoes
The newest "nice" OEIS sequence, A328020, was just published a few minutes ago.
Number of distinct tilings of an n X n square with free n-polyominoes.
This sequence counts tilings up to ...
- 8,117
18
votes
14
answers
1k
views
Permutations in Disguise
Given a \$n\$-dimensional vector \$v\$ with real entries, find a closest permutation \$p\$ of \$(1,2,...,n)\$ with respect to the \$l_1\$-distance.
Details
If it is more convenient, you can use ...
- 43.1k
23
votes
10
answers
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 ...
- 8,117
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, ...
11
votes
1
answer
249
views
Compute my Sacred Geometry [closed]
In the tabletop RPG named Pathfinder, there is a feat that characters can take called Sacred Geometry, which allows a character who has it to buff their spells in exchange for doing some math: to use ...
- 211
0
votes
3
answers
241
views
Find all a, b, c, d, e, such that a + b + c + d + e = 1000 with no more than 3 loops [closed]
The rule is:
a, b, c, d, e is an integer from 0 to 1000, no relation between ...
- 1,217
14
votes
2
answers
773
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 ...
- 8,117
4
votes
1
answer
230
views
Multiplication in the Steenrod Algebra
Here's yet another Steenrod algebra question. Summary of the algorithm: I have a procedure that replaces a list of positive integers with a list of lists of positive integers. You need to repeatedly ...
- 2,085
17
votes
11
answers
1k
views
Generate basis elements of the Steenrod algebra
The Steenrod algebra is an important algebra that comes up in algebraic topology. The Steenrod algebra is generated by operators called "Steenrod squares," one exists for each positive integer i. ...
- 2,085
2
votes
0
answers
95
views
Finding row wise sum of transpose of hv-convex binary matrix [closed]
I'm stuck on a problem involving the Gale-Ryser Theorem. The problem's input gives me the row-wise sum of an hv-convex binary matrix(n*m).
...
- 121
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
13
votes
3
answers
402
views
Counting the number of restricted forests on the Möbius ladder of length n
OEIS sequence A020872 counts the number of restricted forests on the Möbius ladder Mn.
The Challenge
The challenge is to write a program that takes an integer as an input ...
- 8,117
20
votes
8
answers
911
views
Cycles on the torus
Challenge
This challenge will have you write a program that takes in two integers n and m and outputs the number non-...
- 8,117
6
votes
2
answers
332
views
Buy the most appropriate items
A store is having a big sale.
If your price reaches $199 or more, you can reduce it by $100.
You can buy each product only once.
Here's an example list of products: (in order to simplify, the names of ...
- 173
6
votes
2
answers
874
views
Check if all vowels exist in pairs of strings [closed]
Your program should find the number of string pairs (pairs of 2) that contain all vowels (a e i o u), when given an integer N and ...
- 173
14
votes
6
answers
361
views
Unique Brick Tilings Within A Rectangle
I was browsing Stackoverflow and saw this question about tiling an MxN rectangle, and I thought it would be great for golfing. Here is the task.
Given the dimension M and N, write a program that ...
- 721
6
votes
5
answers
391
views
Generate the k-ary necklaces of length n
The set of necklaces is the set of strings, where two strings are considered to be the same necklace if you can rotate one into the other. Your program will take nonnegative integers ...
- 7,079
21
votes
2
answers
480
views
Partition a square grid into parts of equal area
This challenge is based on the following puzzle: You are given an n by n grid with n cells ...
- 8,117
16
votes
4
answers
827
views
Number of \$n\$-carbon alkanes
Given a positive number \$n\$, find the number of alkanes with \$n\$ carbon atoms, ignoring stereoisomers; or equivalently, the number of unlabeled trees with \$n\$ nodes, such that every node has ...
- 36.2k
20
votes
9
answers
2k
views
Partitioning the grid into triangles
Goal
The goal of this challenge is to produce a function of n which computes the number of ways to partition the n X 1 grid into ...
- 8,117
11
votes
3
answers
522
views
Arbitrary Randomness (Speed edition)
Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
- 11.2k
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
5
votes
2
answers
624
views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
user9207
10
votes
1
answer
912
views
Count arrays that are really unique
This is a follow up to Count arrays that make unique sets . The significant difference is the definition of uniqueness.
Consider an array A of length ...
user9207
-1
votes
5
answers
561
views
Fastest algorithm to output array containing all integers in range excluding duplicate digits
Input is a single integer in ascending digit order.
The only valid inputs are:
12
123
1234
...
6
votes
4
answers
163
views
Seeking Substantial Subcollections
(thanks to @JonathanFrech for the title)
Challenge
Write a program or function that, given a collection of positive integers \$S\$ and a positive integer \$n\$, finds as many non-overlapping ...
- 49.3k
11
votes
3
answers
537
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 ...
user9207
9
votes
12
answers
1k
views
Different combinations possible
Problem
Given a value n, imagine a mountain landscape inscribed in a reference (0, 0) to (2n, 0).
There musn't be white spaces between slopes and also the mountain musn't descend below the x axis.
...
17
votes
3
answers
457
views
Removing points from a triangular array without losing triangles
I have a combinatorics problem that I'd like to put on the OEIS—the problem is that I don't have enough terms. This code challenge is to help me compute more terms, and the winner will be the user ...
- 8,117
20
votes
11
answers
2k
views
Socket - Plug compatibility
Traveling with electronics is always fun, especially when you need an adapter to charge them. Your challenge is to make planning a trip a little easier by checking if a given plug will be compatible ...
- 2,222
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
14
votes
12
answers
2k
views
Fun with strings and numbers
Here's a programming puzzle for you:
Given a list of pairs of strings and corresponding numbers, for example, [[A,37],[B,27],[C,21],[D,11],[E,10],[F,9],[G,3],[H,2]]...
- 383
16
votes
27
answers
4k
views
The Unique Padlock PIN List!
Introduction
In a private chat, a friend of mine apparently recently stumbled across a security system which has the following two restrictions on its valid pins:
Each digit must be unique (that is &...
- 3,263
11
votes
25
answers
3k
views
Cartesian product of a list with itself n times
When given a a list of values and a positive integer n, your code should output the cartesian product of the list with itself n ...
- 437
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
9
votes
4
answers
567
views
Count the number of ways of putting balls into bins
In this task you are given an odd number of white balls and the same number of black balls. The task is to count all the ways of putting the balls into bins so that in each bin there is an odd number ...
user9206
16
votes
1
answer
369
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 ...
- 8,117
3
votes
2
answers
79
views
Count stacking sequences [duplicate]
Given a list of stack heights, calculate the number of ways those heights could have been arrived at by stacking blocks one at a time. Shortest code wins.
Test cases:
...
- 3,195
20
votes
2
answers
524
views
Counting polystrips
Polystrips are a subset of polyominoes conforming to the following rules:
each piece consist of 1 or more cells
no cell can have more than two neighbours
the cells should not enclose a hole
Free ...
- 20.6k
11
votes
19
answers
1k
views
Sum of combinations with repetition
Write the shortest code you can solving the following problem:
Input:
An integer X with 2 <= X and X <= 100
Output:
...
- 219
18
votes
8
answers
938
views
Conjugate permutations
A permutation of size n is a reordering of the first n positive integers. (meaning each integer appears once and exactly once). Permutations can be treated like functions that change the order of a ...
- 89.4k
14
votes
8
answers
482
views
Deranged Rearrangements
Your task is to write a computer program such that when it is cut up into lines (split on the newline character) every arrangement of the lines will output a different number between 1 and n! (where n ...
- 89.4k
7
votes
6
answers
439
views
Alice's Tea Party
There are n places set around a circular table. Alice is sat on one of them. At each place, there's a cake. Alice eats her cake, but it doesn't taste very nice. Then the Mad Hatter comes in. He gives ...
- 2,723
24
votes
26
answers
3k
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 if ...
- 4,920