All Questions
Tagged with algorithms combinatorics
1,046
questions
1
vote
1
answer
74
views
Generate superset with maximum overlap
I have a set $S$ with a total of 20000 items. I am also given a list $L$ of 0.5 million sets, with each set having 1-20 elements from the original set. I am given an integer $n$. Now I need a new set $...
- 129
0
votes
1
answer
56
views
Reordering algorithm to fragment consecutive sequences of ones as much as possible
Recently, I came across the following problem:
Let $s_1, s_2, ..., s_k$ be non-empty strings in $\{0,1\}^*$.
We define $S_{s_1,s_2,...,s_k}$ as the concatenation of $s_1, s_2, \dots, s_k$.
We call a &...
- 1
0
votes
1
answer
27
views
Choosing k elements with multiple weights maximizing the minimum weight
Consider the following optimisation problem.
Given a set $S$ with $q$ weight functions $w_1, \ldots, w_q: S\rightarrow \mathbb{R}_+$ and a constant $1\leq k\leq |S|-1$.
Find an $X\subset S, |X|=k$ ...
- 31
0
votes
0
answers
21
views
One to one mapping that maximize the minimum absolute difference
Given two sequences $a_0 \leq a_1 \leq \ldots \leq a_{n-1}$ and $b_0 \leq b_1 \leq \ldots \leq b_{n-1}$. We want to find a one-to-one mapping $\pi:[n-1] \rightarrow [n-1]$ such that
$$
\max \min_{i} |...
0
votes
1
answer
52
views
Find Number of unique durations that can be created given a list of durations and an upper bound [closed]
Lets say we are given a list of durations (5s, 10s, 10s, 15s, 15s, 15s, 25s, 30s....) and we want to find a list of unique durations that can be created using this list of single durations.
for ...
3
votes
2
answers
190
views
Guaranteed graph labyrinth solving sequence
Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
- 53
2
votes
1
answer
83
views
On an algorithm for counting triangles
This is regarding the complexity of an algorithm for counting triangles in an undirected graph which was suggested in a document I came across.
(Link - https://www.cs.cmu.edu/~15750/notes/lec1.pdf)
...
- 435
2
votes
1
answer
42
views
Algorithm to calculate a maximal string from a matrix.
I have stumbled upon an interesting question whilst working on my thesis.
You are given a matrix of pairwise distinct integers $A=(a_{i,j})$ with $1\leq i\leq k$ and $1\leq j \leq r$ and a tuple $(b_1,...
- 175
4
votes
3
answers
220
views
Proof for Particular Fair Shuffle Algorithm
I ran multiple simulations of the following function, and it seems to be fair shuffling, given that all permutations were roughly equal, but I don't understand why it works. It's just inserting at ...
- 41
0
votes
0
answers
21
views
Filtering out faulty durations
I have a question that is algorithms and CS related but felt more appropriate to ask on Math Exchange.
I have a list of candidates, each with a given duration. for example {candidate1: 15s, candidate2:...
0
votes
0
answers
30
views
Constructing an 8x8 Table with Unique Row Patterns and Consistent Prefix-Suffix Combinations
I am looking to create an 8x8 table with specific properties related to prefix and suffix combinations. Each cell in the table represents a combination of a prefix (rows) and a suffix (columns), ...
2
votes
0
answers
73
views
Bin packing : item to be packed in a certain bin depend on previously packed items to that bin.
I am working on an engineering problem. I need to implement an algorithm that looks like a certain variant of bin packing. Specifically, in this variant of the bin packing, the size of a certain item ...
- 131
3
votes
0
answers
82
views
A strategy for number-guessing game
Let player A and player B are playing number-guessing game, which is:
Player A draws one natural number $X$ in $1,2,\cdots,N$ at random.
Player B guesses a number $Y$ in $1,2,\cdots, N$.
Player A ...
- 918
15
votes
0
answers
273
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,333
2
votes
1
answer
47
views
Maximal counterexample for a greedy approach with a non-canonical coin system
Let $1 = c_1 < c_2 < \dots < c_n$ be an integer coin system. This coin system is not necessarily canonical (that is, a greedy algorithm will not necessarily yield the fewest number of coins ...
