Questions tagged [combinatorics]

For challenges involving combinatorics.

Filter by
Sorted by
Tagged with
18 votes
1 answer
699 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 ...
user avatar
15 votes
2 answers
755 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 ...
user avatar
4 votes
0 answers
73 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 ...
user avatar
  • 201
29 votes
4 answers
933 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 ...
user avatar
  • 11.4k
40 votes
45 answers
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 ...
user avatar
32 votes
7 answers
3k 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 ...
user avatar
  • 5,442
31 votes
15 answers
3k 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 ...
user avatar
  • 38.8k
30 votes
13 answers
4k 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. $$S_n(x) = \sum^n_{k=0}s_{n;k}x^n \text{ where } s_{n;k} = (-1)^k\binom n k (k+1)^n$$ The ...
user avatar
  • 207k
9 votes
1 answer
295 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, ...
user avatar
  • 23k
6 votes
2 answers
252 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 ...
user avatar
  • 5,992
27 votes
21 answers
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 ...
user avatar
  • 5,992
8 votes
15 answers
535 views

Evaluate the Binomial Coefficient [duplicate]

Given two nonnegative integers n,k such that 0 <= k <= n, return the binomial coefficient ...
user avatar
  • 43.1k
11 votes
7 answers
481 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). ...
user avatar
13 votes
14 answers
2k 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: ...
user avatar
  • 535
12 votes
3 answers
274 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. ...
user avatar
  • 2,974
17 votes
3 answers
6k 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 ...
user avatar
17 votes
1 answer
440 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 ...
user avatar
  • 891
8 votes
11 answers
868 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 ...
user avatar
  • 107
21 votes
20 answers
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 ...
user avatar
17 votes
15 answers
2k views

Compute the Eulerian number

The Eulerian number A(n, m) is the number of permutations of [1, 2, ..., n] in which exactly ...
user avatar
  • 16.4k
47 votes
8 answers
5k 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 ...
user avatar
  • 89.4k
18 votes
13 answers
2k 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 <...
user avatar
23 votes
27 answers
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 ...
user avatar
  • 461
28 votes
1 answer
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 ...
user avatar
  • 89.4k
12 votes
3 answers
399 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 ...
user avatar
  • 996
8 votes
1 answer
336 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 ...
user avatar
  • 5,442
23 votes
12 answers
3k views

Number of cycles of a permutation

Consider a permutation of the integers 1, ..., n, such as this one for n = 6: ...
user avatar
  • 100k
14 votes
14 answers
692 views

Verify Wolstenholme's theorem

Definition Wolstenholme's theorem states that: where a and b are positive integers and p ...
user avatar
  • 48.6k
13 votes
4 answers
816 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 ...
user avatar
23 votes
6 answers
875 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 ...
user avatar
  • 42.8k
6 votes
6 answers
837 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 ...
user avatar
13 votes
11 answers
3k 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, ...
user avatar
3 votes
2 answers
227 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 (...
user avatar
22 votes
18 answers
2k 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 ...
user avatar
  • 57.4k
6 votes
11 answers
2k 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 ...
user avatar
  • 179
10 votes
3 answers
323 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: ...
user avatar
  • 4,743
4 votes
29 answers
5k 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 ...
user avatar
  • 1,682
12 votes
3 answers
509 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 ...
user avatar
43 votes
21 answers
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 <...
user avatar
26 votes
23 answers
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; ...
user avatar
  • 3,145
8 votes
7 answers
361 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, ...
user avatar
  • 42.9k
7 votes
5 answers
184 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: ...
user avatar
  • 48.6k
12 votes
10 answers
1k 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 ...
user avatar
  • 11.2k
7 votes
8 answers
409 views

m-nomial coefficient

While the binomial coefficient are the coefficients of \$(1+x)^n\$, m-nomial coefficients are the coefficients of \$(1+x+x^2+...+x^{m-1})^n\$. For example, \$m(3,5,6)\$ is the coefficient of \$x^6\$ ...
user avatar
  • 48.6k
10 votes
2 answers
585 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 ...
user avatar
  • 43.4k
28 votes
3 answers
1k 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 ...
user avatar
  • 6,732
10 votes
13 answers
1k 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 ...
user avatar
  • 36.1k
9 votes
20 answers
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 ...
user avatar
  • 2,763
17 votes
5 answers
2k views

Chocolate numbers

Given an m by n chocolate bar, m,n positive, output the number of ways to break the bar into ...
user avatar
  • 61k
15 votes
1 answer
490 views

Same-color arithmetic progressions

Van der Waerden's theorem says that For any given positive integers r and k, there is some number ...
user avatar
  • 138k

1
4
5
6 7 8