For challenges involving combinatorics.
8
votes
0answers
103 views
Fewest disk writes to defrag multiple files
Introduction
A disk is a linear container with blocks indexed 0 through size-1.
A file is a named list of block indexes used by that file.
An example filesystem is expressed like this:
15 ALPHA=3,...
21
votes
20answers
5k views
A penny saved is a penny
...counted!
You will pass your program a variable which represents a quantity of money in dollars and/or cents and an array of coin values. Your challenge is to output the number of possible ...
16
votes
15answers
2k 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
8answers
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 ...
15
votes
13answers
820 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, ...
23
votes
1answer
957 views
Figure Out the Android Lock Pattern
Lets say you saw your friend enter his or her password into their Android phone. You don't remember how they made the pattern but you remember what the pattern looks like. Being the concerned friend ...
12
votes
3answers
286 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
221 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
235 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
729 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
785 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
218 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
868 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 ...
10
votes
3answers
279 views
Ways to get to the number
Given the input of the first number and the second number (both positive integers, zero exluded), determine in how many ways could you make the second out of the first, using following actions: +1,+2 ...
2
votes
29answers
4k views
The handshake problem
The handshake problem is the classic problem that for n people in a room, if they all shake hands, what's the total number of handshakes that occur.
You code should take an input of any number and ...
12
votes
3answers
361 views
Generalized Birthday Problem
Tonight, my fiancée took me out to dinner to celebrate my birthday. While we were out, I heard Happy Birthday sung to 5 different guests (including myself), in a restaurant full of 50 people. This got ...
35
votes
16answers
3k views
Has My Pie Been Bisected?
Write a program or function that takes in a nonempty list of positive integers. You may assume it is input in a reasonable convenient format such as "1 2 3 4" or [1, 2, 3, 4].
The numbers in the ...
7
votes
7answers
292 views
Largest Distinctly Sum-Free Partition
related and inspired by -- Finding sum-free partitions
A set A is defined here as being distinctly sum-free if
1) it consists of at least three elements, |A| ≥ 3, and
2) its distinct self-sum A + A ...
5
votes
3answers
142 views
Find the number of ways to choose `n` objects from `r` objects with repetition so that every object has a matching neighbour
For example, if n is 5 and r is 2, it would mean the number of lists below:
[1,1,1,1,1]
[1,1,1,2,2]
[1,1,2,2,2]
[2,2,1,1,1]
[2,2,2,1,1]
[2,2,2,2,2]
which is 6.
If n is 4 and r is 3:
[1,1,1,1]
[1,1,...
12
votes
10answers
622 views
Permutations with Indistinguishable Items
Given a list of integers, output the number of permutations of the integers, with indistinguishable permutations counted once. If there are n integers, and each group of indistinguishable numbers has ...
7
votes
8answers
361 views
m-nomial coefficient
While binomial coefficient is the coefficient of (1+x)**n, m-nomial coefficient is the coefficient of (1+x+x**2+...+x**(m-1))**n.
For example, m(3,5,6) is the coefficient of x**6 in the expansion of (...
10
votes
2answers
424 views
Tic-tac-toe with only crosses as quick as possible
As per Luke's request and Peter Taylor's addition to this challenge.
Introduction
Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only ...
27
votes
3answers
852 views
Stuffing primes in a box
Your task is write a program or function that can fill a given rectangle with
prime numbers. The width and height of the rectangle will be the input. The
output must be a list of height strings ...
10
votes
12answers
784 views
Generate combinations with replacement
List all of the combinations with replacement (or combinations with repetition) of size k from a set of n elements.
A combination with replacement is an unordered multiset that every element in it ...
11
votes
20answers
2k views
Output the Military Order [duplicate]
In almost every row nowadays, the people tends to order themselves as militaries would do.
Challenge
Suppose 4 people where:
person 1 has priority against person 2, 3 and 4,
person 2 has priority ...
17
votes
5answers
1k views
Chocolate numbers
Given an m by n chocolate bar, m,n positive, output the number of ways to break the bar into mn 1 by 1 pieces where each break occurs on a gridline.
Order is important. Pieces are also ...
15
votes
1answer
373 views
Same-color arithmetic progressions
Van der Waerden's theorem says that
For any given positive integers r and k, there is some number N such
that if the integers {1, 2, ..., N} are colored, each with one of r
different colors, ...
21
votes
19answers
1k views
Rearranging the sequence
Introduction
Let's observe the following sequence (non-negative integers):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
For example, let's take the first three numbers. These are 0, 1, 2. ...
24
votes
6answers
749 views
Enumerate rhyme schemes
A "rhyme scheme" is a string of letters a to z, such that the first occurrences of the characters are in ascending order (without gaps), starting from a. For example (with first occurrences marked):
...
7
votes
5answers
750 views
Hypercube sides
Your goal is to output all the "sides" (corners, edges, faces, etc.) of an N-dimensional unit hypercube, where N is non-negative. A "side" is defined as any (N-M)-dimension surface embedded in N-...
22
votes
11answers
935 views
Compute the multinomial coefficient
Time for another easy challenge in which all can participate!
The multinomial theorem states:
The expression in parentheses is the multinomial coefficient, defined as:
Allowing the terms ki to ...
0
votes
0answers
79 views
How many ways are there to achieve a winning score in American Football? [duplicate]
[I decided to salvage Ben Reich's question How many unique ways are there to achieve a score in Football? but it ended up being so different that it's only suitable as its own question not spliced ...
31
votes
6answers
1k views
Tic-tac-toe with only crosses
Introduction
Everyone knows the game tic-tac-toe, but in this challenge, we are going to introduce a little twist. We are only going to use crosses. The first person who places three crosses in a row ...
17
votes
9answers
430 views
Counting Fountains
A fountain is arrangement of coins in rows so that each coin touches two coins in the row below it, or is in the bottom row, and the bottom row is connected. Here's a 21 coin fountain:
Your challenge ...
17
votes
9answers
769 views
Sums of prime factors
2013 has the prime factorization 3*11*61. 2014 has the prime factorization 2*19*53. An interesting property regarding these factorizations is that there exist distinct primes in the factorizations of ...
26
votes
13answers
2k views
Motzkin Numbers
The nth Motzkin Number is the number of paths from (0, 0) to (n, 0) where each step is of the form (1, -1), (1, 0) or (1, 1), and the path never goes below y = 0.
Here's an illustration of these ...
15
votes
8answers
685 views
Minimum number of numbers to sum to exactly n
First question here, don't yell at me if this is a duplicate or a bad challenge.
Introduction
I thought of this challenge myself, and it seems to be a good basic puzzle for beginner code-golfers. It ...
15
votes
11answers
536 views
Find the sets of sums
I've enjoyed reading this site; this is my first question. Edits are welcome.
Given positive integers n and m, compute all ordered partitions of m into exactly n parts positive integer parts, and ...
32
votes
39answers
5k views
Catalan Numbers
The Catalan numbers (OEIS) are a sequence of natural numbers often appearing in combinatorics.
The nth Catalan number is the number of Dyck words (balanced strings of parenthesis or brackets such as ...
19
votes
21answers
3k views
Bernoulli Numbers
The Bernoulli numbers (specifically, the second Bernoulli numbers) are defined by the following recursive definition:
Where denotes a combination.
Given a nonnegative integer m as input, output the ...
38
votes
38answers
3k views
Count sums of two squares
Given a non-negative number n, output the number of ways to express n as the sum of two squares of integers n == a^2 + b^2 (OEIS A004018). Note that a and b can be positive, negative, or zero, and ...
9
votes
4answers
270 views
Rearrangement Inequality
Background
The Rearrangement Inequality is an inequality that is based on rearranging numbers. If I have two lists of numbers of the same length, x0, x1, x2...xn-1 and y0, y1, y2...yn-1 of the same ...
17
votes
6answers
305 views
Enumerating N-Dimensional Vectors
Given a positive integer k > 1 and a non-negative integer i, generate a k-tuple (or k-dimensional vector) of non-negative integers. For every k, the map from ℕ to ℕk, must be bijective. That is, ...
17
votes
7answers
798 views
Finding sum-free partitions
Executive summary
Given input k, find a partition of integers 1 to n into k sum-free subsets for the largest n you can within 10 minutes.
Background: Schur numbers
A set A is sum-free if its self-...
18
votes
2answers
767 views
The Combinatorics of Transistor
The video game Transistor features a very interesting ability system. You collect 16 "Functions" which you can use in 16 different slots. What's interesting is that there are 3 types of slots and ...
