Questions tagged [combinatorics]
For challenges involving combinatorics.
249
questions
14
votes
1answer
327 views
+50
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 ...
13
votes
6answers
402 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 ...
6
votes
3answers
198 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 ...
17
votes
2answers
561 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 symmetries ...
16
votes
14answers
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 ...
21
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 ...
32
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, ...
8
votes
1answer
193 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 ...
-1
votes
3answers
228 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 ...
12
votes
2answers
548 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 ...
3
votes
1answer
214 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 ...
16
votes
11answers
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. ...
1
vote
0answers
87 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).
...
35
votes
21answers
5k 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 ...
13
votes
3answers
370 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 ...
20
votes
8answers
822 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-...
6
votes
2answers
297 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 ...
6
votes
2answers
565 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 ...
13
votes
6answers
315 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 ...
6
votes
5answers
309 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 ...
17
votes
1answer
288 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 ...
16
votes
4answers
707 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 ...
18
votes
9answers
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 ...
10
votes
3answers
445 views
Arbitrary Randomness (Speed edition)
Given integer n, calculate a set of n random unique integers in range 1..n^2 (inclusive) ...
26
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 ...
5
votes
2answers
297 views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
9
votes
1answer
825 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 ...
0
votes
5answers
479 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
4answers
157 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 ...
11
votes
3answers
478 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 ...
9
votes
12answers
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
3answers
391 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 ...
19
votes
11answers
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 ...
28
votes
4answers
798 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 ...
13
votes
12answers
1k 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]]...
16
votes
27answers
3k 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 "...
10
votes
22answers
2k 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 ...
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)\$. ...
9
votes
4answers
515 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 ...
16
votes
1answer
325 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 ...
3
votes
2answers
75 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:
...
16
votes
1answer
296 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 ...
8
votes
17answers
827 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:
...
17
votes
8answers
826 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 ...
14
votes
8answers
446 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 ...
7
votes
6answers
427 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 ...
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 ...
12
votes
4answers
230 views
Compute number of matrices with appropriate sums
When multiplying monomials in the Milnor basis for the Steenrod algebra, part of the algorithm involves enumerating certain "allowable matrices".
Given two lists of nonnegative integers r1, ... ,rm ...
14
votes
16answers
878 views
Mod 2 Multinomial coefficients
quintopia has posted here a challenge to compute multinomial coefficients (some of the text here is copied from there). There is a fun algorithm to compute multinomial coefficients mod 2.
Given a ...
13
votes
5answers
327 views
Integer triangles with perimeter less than n
Definition
An "integer triangle" is one with integer coordinates. For example the following triangle is an integer triangle:
...
