Questions tagged [combinatorics]
For challenges involving combinatorics.
259
questions
9
votes
5answers
1k views
Count the number of Hamming distance sequences
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
Let P be a binary string of ...
13
votes
2answers
975 views
Count how many distance sequences are far from all others
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
Let P be a binary string of ...
13
votes
16answers
1k views
Number of string permutations that are palindromes
Your input will be a string consisting of small english letters.
Your task is to determine the number of distinct permutations of the original string that are a palindrome.
The input string has up ...
12
votes
1answer
350 views
Stable marriage problem
Background
Suppose that there are 2*n people to be married, and suppose further that each person is attracted to exactly n ...
20
votes
3answers
355 views
Rafting Problem (Knapsack variant)
First puzzle from me, suggestions for improvement gladly received!
The scenario is;
You work as a manager for a whitewater rafting company. Every morning, you are given a list of bookings, and you ...
19
votes
5answers
2k views
Necklace splitting problem
Background
I was inspired by 3Blue1Brown's recent video about the necklace splitting problem (or as he calls it, the stolen necklace problem) and its relationship to the Borsuk-Ulam theorem.
In this ...
17
votes
1answer
639 views
Hold'em or Fold'em?
Your friend invited you to a high-stakes poker game at the last minute and, as a computer scientist, you've decided to use your skills to gain an edge on the game. Your task will be, given ...
9
votes
0answers
388 views
Total Derangement (Difficulty Level: Hard)
The problem: Write a function which, given a cycle length n and a number of cycles m, where 'm' is within ...
3
votes
0answers
68 views
Code Golf - Print all unique ways of writing a number as a sum with a lexical order [duplicate]
I found about Code Golf after writing this program and decided to post the rules here so you can try it out too. I saw this, which is a less restrictive version of my question. I've got a bit more ...
26
votes
3answers
812 views
Arranging Bubbles
Note, challenge copied from question asked at math.stackexchange.
Recently, I attained quite some skill at blowing bubbles. At first I would blow bubbles like this:
But then things started getting ...
38
votes
45answers
6k views
Every word from babab to zyzyz
Your task is to write a program that will output a readable list of every five letter words with the structure:
consonant - vowel - consonant - vowel - consonant
The output should be sorted ...
31
votes
7answers
2k views
Longest domino chain
Challenge description
Dominoes is a game played with tiles with two values on it - one on the left, one on the right, for example [2|4] or ...
28
votes
14answers
1k views
List all multiplicative partitions of n
Given a positive number n, output all distinct multiplicative partitions of n in any convenient format.
A multiplicative partition of n is a set of integers, all greater than one, such that their ...
28
votes
11answers
3k views
Absolute Sums of Sidi Polynomial Coefficients
Background
The Sidi polynomial of degree n – or the (n + 1)th Sidi polynomial – is defined as follows.
The Sidi polynomials have several interesting properties, but so do their coefficients. The ...
9
votes
1answer
224 views
Number of prime knots with n crossings
A prime knot is:
a non-trivial knot which cannot be written as the knot sum of two non-trivial knots.
Explanation of a knot-sum: put the two knots adjacent,
... then draw two lines between them, ...
5
votes
1answer
209 views
Straight Chain Alk*nes without Order
This is much like my earlier challenge, except, this time, order doesn't matter.
A straight-chain alk*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or ...
28
votes
20answers
1k views
Number of Straight-Chain Alk*nes of given length
A straight-chain alk*ne is defined as a sequence of carbon atoms connected by single (alkane), double (alkene), or triple bonds (alkyne), (implicit hydrogens are used.) Carbon atoms can only form 4 ...
8
votes
15answers
417 views
Evaluate the Binomial Coefficient [duplicate]
Given two nonnegative integers n,k such that 0 <= k <= n, return the binomial coefficient
...
11
votes
7answers
441 views
Sum digits till Square
Given is any integer x > 0 and any base y > 3.
Sum all digits of x (if written in the set base).
Multiply this by the highest possible digit (is always base -1).
...
13
votes
14answers
1k views
Generate all combinations of given list of elements, sorted
Make a code that takes a list and a number as input, and generates all possible combinations with the length of the number. For example, with the list {0,1} and the number 2:
...
12
votes
3answers
254 views
Convert a sample to an index
We are putting balls into a fixed number a bins. These bins begin empty.
Empty bin (a=4): 0 0 0 0
And one by one we add balls to the bins.
...
15
votes
3answers
5k views
Dobble/SpotIt card generator
Introduction
Dobble/SpotIt is a card game, where people have to spot same symbol on pair of cards in shortest time, indicate it and move to next pair. Each card has multiple symbols (8 in normal ...
18
votes
1answer
430 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 ...
8
votes
11answers
846 views
Ordered list of binary sequences of multiple dimensions
Given a positive integer n, output the 2^n binary sequences of length n sorted in the ...
21
votes
20answers
6k 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 ...
17
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 ...
48
votes
8answers
4k 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 ...
asked Oct 13 '16 at 20:27
Post Rock Garf Hunter
54.8k12 gold badges178 silver badges395 bronze badges
17
votes
13answers
1k 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 <...
23
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 ...
26
votes
1answer
2k 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 ...
asked Aug 22 '16 at 20:38
Post Rock Garf Hunter
54.8k12 gold badges178 silver badges395 bronze badges
12
votes
3answers
339 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 ...
7
votes
1answer
272 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 ...
23
votes
12answers
2k views
Number of cycles of a permutation
Consider a permutation of the integers 1, ..., n, such as this one for n = 6:
...
14
votes
14answers
665 views
Verify Wolstenholme's theorem
Definition
Wolstenholme's theorem states that:
where a and b are positive integers and p ...
13
votes
4answers
582 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 ...
23
votes
6answers
855 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
...
6
votes
6answers
824 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
225 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 (...
22
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
...
5
votes
11answers
1k 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
300 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: ...
3
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
461 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 ...
43
votes
19answers
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 <...
27
votes
23answers
2k views
Case Permutation
Who needs to compare things case insensitively when you're able to generate every permutation of uppercase and lowercase? No one! That's the answer. No one does. Your task is to achieve this feat; ...
8
votes
7answers
334 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, ...
5
votes
3answers
160 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:
...
12
votes
10answers
823 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 ...
7
votes
8answers
380 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....
