All Questions
Tagged with combinatorics algorithms
336
questions with no upvoted or accepted answers
15
votes
0
answers
271
views
Recovering a binary function on a lattice by studying its sum along closed paths
I have a binary function $f:\mathbb N^2\rightarrow\{0,1\}$. While I do not known $f$ explicitly, I have a "device" located at the origin $(1,1)$ which can do the following:
Given an even ...
- 4,323
9
votes
0
answers
117
views
+50
What is the current best algorithm to find if a simply connected region is uniquely tileable with dominoes?
I was reading both Thurston's and Fournier's papers on algorithms which detect whether or not a simply connected region is tileable using dominoes (1 by 2 rectangles) when I came across the section in ...
- 405
8
votes
0
answers
278
views
Count permutations with given longest increasing subsequence
Problem: Given $n \in \mathbb{Z}_+$ and a set $A \subset \{ 1,\ldots,n \}$ sorted in ascending order, find the number of permutations $\sigma \in S_n$ such that $A$ is a longest increasing subsequence ...
- 4,051
8
votes
0
answers
317
views
Efficient algorithms to determine whether vertices form a deadlock
$\textbf{I. Problem Statements}$
Let $m, n \in \mathbb{N}^*$ and $G = (V, E)$ be a simple graph. First we define some notations:
(1)$[m] := \{1, 2, \dots, m\}$.
(2)$e_i$ is the elementary vector with $...
- 1,008
6
votes
0
answers
355
views
Decrease list difference via swaps
There are four lists, each with $100$ numbers in $[0,1]$. You want to perform as few swaps between pairs of numbers as possible, so that the difference between the sums of numbers in any two lists ...
- 83
6
votes
0
answers
391
views
Traveling salesman problem: can a terrible strategy beat a good one?
Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
- 133
6
votes
0
answers
178
views
$k$-covering of the set of all possible n-length words
Give an alphabet $\mathcal{A}=\{a_1,a_2,\ldots,a_m\}$, and let $L_n$ is the set of all possible $n$-length words in form $[a_{i_1}a_{i_2}a_{i_3}\ldots a_{i_n}],\ a_{i_j}\in \mathcal{A}$.
We call a $...
- 173
5
votes
0
answers
485
views
How many Color Balanced sets can you make with n colors?
You have n colors and you make nonempty sets from them. A set of these color sets is color balanced if each color is in the same number of the color sets.
Ex. For <...
- 51
5
votes
0
answers
56
views
Bracelet isomorphism algorithms
I feel like the problem should have been studied, but I wasn't able to find anything precise.
Given two bracelets with $n$ beads and $m$ colors, given that the multiplicity of each color is the same, ...
- 2,103
5
votes
0
answers
200
views
Topological Minors on Simple Graphs --- Antichains?
This is a follow-up discussion on @296991, with further questions.
In the following discussion, "graphs" are finite but not necessarily simple (i.e. $|V(G)|<\infty,$ but allow loops and ...
- 51
5
votes
0
answers
290
views
Faster Algorithm for counting non-negative tripple(a, b, c) satisfied (a + b + c <= S) and (a * b * c <= T) and subproblem divisor summatory function
Statement
This problem
Code
Used this Paper
Given $S, T (0 \leq S, T \leq 10^{18})$
I need to count the number of tuple $(a, b, c)$ satisfied $(\min(a, b, c) \geq 0)$ and $(a + b + c \leq S)$ and $(a ...
- 85
5
votes
0
answers
45
views
Number of lines of $3$ points in an arrangement of points and lines
It is well known that a finite set of $n$ points cannot form more than
$$\bigg\lfloor \frac{n(n-3)}{6} \bigg\rfloor+1 $$
lines that include $3$ points. Would this result still hold if we assume that ...
user920720
5
votes
0
answers
80
views
Arranging playdate groups
At my kids' school, the kids are meeting in playdate groups of two girls and two boys every month. The groups are constructed to get as much variation in the groups over the months. Having seen too ...
5
votes
0
answers
121
views
Partition problem where partition are in increasing order.
For given $n$ and $S$, how many possible combinations are there such that:
$x_1 + x_2 + .. + x_n = S $ $\forall i, x_i \leq x_{i+1}$ $\&$ $x_i \geq 1$
For example, if $n$ = 3 and $S$ = 5, there ...
- 51
5
votes
0
answers
81
views
Is there a characterization of the permutations arising from this 'buggy' shuffle?
The classical 'correct' way of shuffling a deck of $n$ items is to use the Fisher-Yates shuffle:
...
- 52.4k