Questions tagged [combinatorics]
For challenges involving combinatorics.
372
questions
5
votes
1
answer
306
views
Dishonest dungeon staff
This is a joint post with https://puzzling.stackexchange.com/questions/126255/dishonest-dungeon-staff
You are faced with the difficult task to set up a dungeon for adventurers. However you made a deal ...
- 151
21
votes
4
answers
2k
views
Avoiding Loops!
Given a collection of coloured laces, what would be the probability, \$P\$, that Alice won't create any loops if, until impossible, they tie two uniformly chosen, free lace ends of differing colours ...
- 108k
14
votes
13
answers
1k
views
Counting rankings
There is a competition with \$n\$ participants in total. Alice is one of the participants. The outcome of the competition is given as a ranking per participant with a possibility of ties; e.g. there ...
- 77.5k
10
votes
6
answers
645
views
Robinson Schensted correspondence
[The explanations of the algorithm come from here. I recommend reading it for a beautiful description of the algorithm.]
This challenge is to implement the Robinson Schensted correspondence.
Input
A ...
- 3,098
14
votes
10
answers
1k
views
Expected number of rounds for this labeling scheme
Task
Here is an interesting math problem:
Let's say that there are \$n\$ indistinguishable unlabeled objects in a bin. For every "round", pull \$k\$ objects randomly out of the bin with ...
- 13.7k
10
votes
7
answers
587
views
List all words following a pattern
This challenge is to list out all possible words which are built from a pattern of syllables. Words are composed by joining syllables together. Syllables are composed of a number of vowels with some ...
- 1,053
19
votes
14
answers
2k
views
Rook Polynomials
In combinatorics, the rook polynomial \$R_{m,n}(x)\$ of a \$m \times n\$ chessboard is the generating function for the numbers of arrangements of non-attacking rooks. To be precise:
$$R_{m,n}(x) = \...
- 48.7k
5
votes
3
answers
411
views
Valid python function invocation signatures
Background
In Python, function arguments are defined within the parentheses following the function name in the function definition. There are different ways to present function arguments, and they can ...
- 181
10
votes
3
answers
332
views
Representing a number as an unordered list of smaller numbers
Suppose we want to encode a large integer \$x\$ as a list of words in such a way that the decoder can recover \$x\$ regardless of the order in which the words are received. Using lists of length \$k\$ ...
- 621
0
votes
1
answer
285
views
Generate all possible equations from a list of numbers [closed]
This is my first codegolf post so let me know if I have missed anything. Thanks :)
Description
You are given a list of numbers with 2 < n <= 6 length i.e. [1, ...
- 21
12
votes
15
answers
1k
views
The number of solutions to Hertzsprung's Problem
Hertzprung's Problem (OEIS A002464) is the number of solutions to a variant of the Eight Queens Puzzle, where instead of placing \$n\$ queens, you place \$n\$ rook-king fairy pieces (can attack like ...
- 10.2k
13
votes
11
answers
2k
views
String Concatenate
You are given a string \$s\$ of characters from a to z. Your task is to count how many unique strings of length \$n\$ you can make by concatenating multiple prefixes of the string \$s\$ together.
...
- 1,188
16
votes
8
answers
2k
views
We're gonna need a bigger podium!
If \$R\$ runners were to run a race, in how many orders could they finish such that exactly \$T\$ runners tie?
Challenge
Given a positive integer \$R\$ and a non-negative integer \$0\leq T\leq {R}\$ ...
- 108k
13
votes
17
answers
1k
views
A Fine sequence with fine interpretations
The ubiquitous Catalan numbers \$C_n\$ count the number of Dyck paths, sequences of up-steps and down-steps of length \$2n\$ that start and end on a horizontal line and never go below said line. Many ...
- 3,845
10
votes
6
answers
752
views
CGAC2022 Day 13: Santa's gift and the laser lock, Part 2
Part of Code Golf Advent Calendar 2022 event. See the linked meta post for details.
You successfully route the laser into the sensor, but nothing happens.
"What?" Frustrated, you flip the ...
- 77.5k