Questions tagged [combinatorics]
For challenges involving combinatorics.
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
698 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)\$. ...
8
votes
4answers
492 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
282 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
74 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
281 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
768 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
763 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
433 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
409 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
225 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
853 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
304 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
674 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
448 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
259 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
630 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
690 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
240 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
856 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
534 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
502 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
831 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
191 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 ...
7
votes
6answers
355 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
628 views
Restricted Integer Partitions
Pk(n) means the amount of partitions of n into exactly k parts. Given n and ...
11
votes
3answers
789 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
358 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 ...
15
votes
6answers
1k views
BASKETBALL FRVR?
You might already be familiar with the game: Basketball FRVR in facebook. There are two types of score you can make:
A virgin-shot:(we call it so in our country :D) When the ball enters the basket ...
11
votes
3answers
321 views
Lyndon word factorization
Background
A Lyndon word is a non-empty string which is strictly lexicographically smaller than all its other rotations. It is possible to factor any string uniquely as the concatenation of Lyndon ...
11
votes
27answers
759 views
All non-ordered pairs between the elements of an array
Task:
Return an array with all possible pairs between the elements of an array.
Example
From a=["a", "b", "c", "d"]; return ...
10
votes
2answers
406 views
Compute OEIS A005434
The task is to compute OEIS A005434 as quickly as possible.
Consider a binary string S of length n. Indexing from ...
12
votes
13answers
988 views
How many ways to write numbers as sums of squares?
Task
Given two integers d and n, find the number of ways to express n as a sum of ...
7
votes
3answers
124 views
Rooting for Trees With the Right Nodes
Background
A rooted tree is an acyclic graph such that there is exactly one path from one node, called the root, to each other node. A node v is called the parent ...
10
votes
1answer
541 views
Roll to see all sides!
Let's say you have a 20-sided die. You start rolling that die and have to roll it a few dozen times before you finally roll all 20 values. You wonder, how many rolls do I need before I get a 50% ...
14
votes
12answers
984 views
Finding approximate correlations
Consider a binary string S of length n. Indexing from 1, we can compute the Hamming ...
14
votes
2answers
160 views
Find Subset Factors
Let's imagine we have a finite set of positive integers. This set can be represented as a line of dots where each integer present in the set is filled in like a scantron or punch card. For example ...
14
votes
0answers
324 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 ...
14
votes
9answers
574 views
Find the Odd odds
Given an unordered collection of positive integers by any reasonable input method, return all of the sub-collections that have an odd number of odd elements (i.e. have an odd total).
This is code-...
