Questions tagged [combinatorics]
For challenges involving combinatorics.
15
votes
3answers
498 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
1k 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
387 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 ...
4
votes
2answers
254 views
Find arrays with distinct subarray sums
Consider an array A of length n. The array contains only integers in the range 1 to ...
7
votes
1answer
752 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
4answers
429 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
156 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
456 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.
...
12
votes
2answers
273 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
12answers
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 ...
27
votes
4answers
726 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
1k 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
505 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 ...
14
votes
1answer
290 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 with their indices) fall on a polynomial of degree k.
That is,
No ...
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
288 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
790 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
773 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
435 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 ...
8
votes
6answers
417 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
227 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
862 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 ...
14
votes
5answers
313 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:
...
21
votes
3answers
759 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.
...
19
votes
13answers
2k views
Is it a shuffle?
Yesterday I asked this question about riffle shuffles. It seems that yesterdays question was a bit too hard so this question is a related but much easier task.
Today you are asked to determine if a ...
19
votes
23answers
2k views
Single swaps of an array
Inspired by Taken from a question at Stack Overflow.
The challenge
Given an integer n>1, output all arrays that can be obtained by swapping exactly two entries ...
18
votes
2answers
452 views
How many shuffles
A riffle shuffle is a type of shuffle where the deck is split into two partitions and the partitions are then spliced back together to create a new shuffled deck.
The cards are spliced together in ...
7
votes
4answers
200 views
Prefixless Palindromes
Write a program or function that takes N, and S and outputs the number of palindromes of length S you can build using an alphabet of size N such that any prefix of size between 2 and S-1 is not a ...
9
votes
4answers
260 views
Now we're thinking in n dimensions!
The question: Given an a number n ≥ 2, how many distinct pairs of points on an n-dimensional ...
16
votes
9answers
650 views
XKCD Calendar Facts
Inspiration. Posted with permission.
Print one of the possible XKCD calendar "facts":
You can get the raw text and structure from my APL reference implementation or from Explain XKCD's transcript (...
17
votes
10answers
2k views
Enumerate all possible grids of integers with constraints
Problem
Consider a square 3 by 3 grid of non-negative integers. For each row i the sum of the integers is set to be r_i. ...
19
votes
9answers
739 views
Hand patterns in a card game
A deck of cards is the Cartesian product of S suits and R ranks.
Many, though not all, card games use ...
5
votes
1answer
245 views
Bobby's Booby-Trapped Safe
Bobby's booby-trapped safe requires an n-digit code to unlock it. Alex has a probe which can test combinations without typing them onto the safe. The probe responds Fail if no individual digit is the ...
20
votes
8answers
871 views
Pick-flatten a list
Consider the process of "picking" a nested list. Picking is defined as follows:
If the argument is a list, take an element from the list at random (uniformly), and pick from that.
If the argument is ...
13
votes
10answers
543 views
Counting Fibonacci Orbits
If we define a Fibonacci-like sequence as fk(n) = (fk(n-1) + fk(n-2)) % k, for some integer k (where % is the modulo operator), the sequence will necessarily be cyclic, because there are only k2 ...
23
votes
5answers
504 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 ...
19
votes
7answers
891 views
Number of distinct non-empty subsequences of binary expansion
A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of 100 are ...
4
votes
0answers
193 views
Those annoying grasshoppers [closed]
The problem #6 of IMO 2009 reads:
Let a 1, a 2, a 3, ..., a n, be distinct positive integers and let T be a set of n-1positive integers not containing a 1+a 2+a 3+...+a n, A grasshopper is to ...
8
votes
6answers
359 views
Distinct Reversible Primitive Binary Necklaces
Introduction - What is a necklace?
A necklace is something that OEIS people are obsessed with. The OEIS challenge has like 5 necklace sequences.
A binary necklace of length ...
15
votes
16answers
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 ...
9
votes
16answers
653 views
Restricted Integer Partitions
Pk(n) means the amount of partitions of n into exactly k parts. Given n and ...
12
votes
3answers
837 views
How many ways can a road cross a river?
Imagine a straight river and a road that goes across the river n times through bridges. The road does not loop on itself and is infinitely long. This road would be considered an open meander. An open ...
16
votes
7answers
1k views
How many partitions contain only perfect squares?
Given a non-negative integer or a list of digits, determine in how many ways can the number be formed by concatenating square numbers, which may have leading zeroes.
Examples
...
9
votes
4answers
401 views
Maximum number of distinct substrings
Description
Given a length n, and an alphabet size k>0, your program must determine the number of strings with those ...
