All Questions
Tagged with combinatorics algorithms
337
questions with no upvoted or accepted answers
5
votes
0
answers
131
views
Analysis of sorting Algorithm with probably wrong comparator?
It is an interesting question from an Interview, I failed it.
An array has $n$ different elements $[A_1 , A_2, ..., A_n]$ （random order）.
We have a comparator $C$, but it has a probability $p$ to ...
- 61
5
votes
0
answers
148
views
$n$ solutions Sudoku
Is there an algorithm which can calculate a $9 \times 9$ Sudoku with non-trivial $n$ possible solutions?
So if you play it you can play it for example 4 times? So if you play it there's a choice in ...
- 163
5
votes
0
answers
297
views
Is there a way to figure out the minimum number of participants or maximum number of rounds in my tournament style?
I just finished hosting a Euchre tournament at work that was meant to get people to meet other people in the company. This is the third time I've hosted this type of tournament. The first two times, ...
- 151
5
votes
0
answers
152
views
Nice puzzle: Creating a binary word using weights and scales
You are given $N$ weights where for each $i \in \{1,2,...,n\}$, the $i$-th weight weighs $i$ pounds. You are given an $N$-binary-word that's formed by $L$'s and $R$'s and scales. You need to provide ...
- 51
5
votes
1
answer
333
views
Swapping and handshakes with neighbours in a circle
$N$ people are at a party and decide to play a cooperative game. They begin by standing in a circle. The game proceeds in turns. In each turn, one person is chosen to perform one of the following ...
- 659
4
votes
0
answers
103
views
Reducing column ranges of a matrix
I'm looking for an algorithm to reduce the sum of column ranges in a sparse integer matrix by subtracting $1$ from all nonzero elements in a subset of the rows.
Let $R = 1, \ldots, m$ and $C = 1, \...
- 146
4
votes
0
answers
159
views
Finding simple algorithm to combine students into different groups
I'd like to find an algorithm as simple as possible to solve the problem below.
The same seven students will each day be divided and meet into two groups, one with four students and one with three. ...
- 41
4
votes
0
answers
159
views
Minimizing floor space needed to store $N$ unit cubes, subject to two placement rules
There is a store room which has only three sides all touching each other perpendicularly, the sides can be defined as: two infinitely large walls and one infinitely large floor.
There are $N$ cubes ...
- 61
4
votes
1
answer
195
views
Combinations of red and black balls
Given $N$ Identical Red balls and $M$ Identical Black balls, in how many ways we can arrange them such that not more than $K$ adjacent balls are of same color.
Example : For $1$ Red ball and $1$ ...
- 41
4
votes
1
answer
110
views
Algorithm for partitioning graph edges into n-cycles (small number of vertices, say 60)
So we have a graph with a small number of vertices (can be limited to as little as 20 if making this algorithm is hard). Lots of edges though, it is probably a 2 or at most 8 partite graph.
I'm ...
- 311
4
votes
0
answers
80
views
Combinatorics of sets
Let us take an $n \in \mathbb{N}$ . Consider $S=${${\text{1,2,3,}\cdots \text{n}}$} .
Call a subset of $S$ to be X-sum-friendly if the sum of the elements of this subset is $X$ where $X \in \mathbb{...
- 63
4
votes
0
answers
310
views
Find the number of simple labeled graphs which have no isolated vertices
Find the number of simple labeled graphs on n vertices which have no isolated vertices? Compute the result for n=13
Total number of simple labeled graphs = $2^{n \choose 2}$.
How to remove vertices ...
- 860
4
votes
0
answers
81
views
How many $3 \times 3$ squares are there such that the four sub-$2 \times 2$ squares have a certain sum?
Given $a, b, n \in \mathbb{N}$, how many ways are there to choose numbers $s_i$, $\ a <= s_i < b$, $\ 0 \leq i < 9$, such that $ n = s_0+s_1+s_3+s_4 = s_1+s_2+s_4+s_5 = s_3+s_4+s_6+s_7 = s_4+...
- 165
4
votes
0
answers
93
views
Counting the number of partitions that are a distance d away from a fixed partition.
Given a positive integer $N \in \mathbb{Z}^{\geq 0}$ let $Partitions(N)$ denote the set of all partitions of $N$, where a tuple $\left(f_1,\ldots,f_N \right)$ is a partition of $N$ if $\sum_{i=1}^N ...
- 41
4
votes
0
answers
95
views
partitions of finite set in same-size parts having at most one element in common
Given $g \ge 2$, $k \ge 1$ and a population of $p = kg$ workers, I'm trying to figure out the longest series of work shifts such that:
during each shift, all workers work in $k$ teams of g people;
...
- 257