For challenges involving combinatorics.
6
votes
4answers
48 views
Compute the Eulerian number
The Eulerian number A(n, m) is the number of permutations of [1, 2, ..., n] in which exactly m elements are greater than the previous element. These are also called rises. For example, if n = 3, there ...
42
votes
9answers
2k 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 ...
13
votes
12answers
778 views
Inverse permutation index
Introduction
The lexicographical permutations of a list with n elements can be numbered from 0 to n! - 1. For example, the 3! = 6 permutations of (1,2,3) would be (1,2,3), (1,3,2), (2,1,3), (2,3,1), (...
22
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 1 to n whose sum is n. For example, given input n = 4, ...
12
votes
3answers
285 views
Verify a ballot triangle
A ballot number, which we'll label B, is the number of ways of arranging the numbers from 1 through B(B+1)/2 into a triangle, such that each row and column is in any increasing order. The first four ...
6
votes
1answer
208 views
Count blocks in a 2D grid
Challenge description
Let's define an W x H grid as a two-dimensional array of length H whose each subarray is of length W. Example: a 2x3 grid (. character used as a blank):
..
..
..
A unit is a ...
21
votes
12answers
1k views
Number of cycles of a permutation
Consider a permutation of the integers 1, ..., n, such as this one for n = 6:
[5,2,4,3,6,1]
If you view the permutation as a mapping from [1,2,3,4,5,6] to [5,2,4,3,6,1], the permutation can be ...
11
votes
10answers
541 views
Verify Wolstenholme's theorem
Definition
Wolstenholme's theorem states that:
where a and b are positive integers and p is prime, and the big parentheses thingy is Binomial coefficient.
Task
To verify that, you will be given ...
11
votes
4answers
211 views
Coin Change Problem Enumeration Using N Coins And Each Denomination
The coin change problem is very well documented. Given an infinite supply of coins of denominations x_1 to x_m you need to find the number of combinations which add up to y. For example, given x = {1,...
23
votes
5answers
723 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
d_1 * d_2 * ... * d_k = n
Each positive integer has a unique prime factorisation, but in general they ...
6
votes
6answers
783 views
Is case sensitivity important? Part II: reality check
In this question Tom learned that, in general, there are many motivations to choose to include case sensitivity in his programming language, because the possible combinations for a variable name are ...
13
votes
11answers
2k views
Is case sensitivity important?
Tom is going to implement a new programming language of his invention. But before actually starting working on it, he wants to know whether his language should be case sensitive or not.
On one hand, ...
2
votes
2answers
216 views
Marching Through A City
There is a parade marching through a city! There are 3 main groups of marchers: the (B)and, Poster (C)arriers, and (F)lag Holders. Also, every (P)oliceman in the whole city is on duty.
Flag holders (...
20
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
[1, 1, 1, 1, 1]
[1, 1, 1, 2]
[1, 1, 3]
[1, 2, 2]...
5
votes
11answers
853 views
Recursion bracketed; or Dyck words generation
We already have challenges to check if a string of brackets is fully matched and to count the number of balanced strings. It remains for us to generate these strings, but it will not be so easy…
A ...
