All Questions
Tagged with combinatorics algorithms
1,042
questions
1
vote
1
answer
44
views
Find Number of unique durations that can be created given a list of durations and an upper bound
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
184
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
214
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
80
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
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
2
votes
1
answer
46
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 ...
0
votes
0
answers
48
views
Coin weighting with constraints
Consider the following $(d,k,n)$-coin weighting (with spring scale):
You possess an electronic scale, $n$ coins, and $d$ of them are magnetic. Moreover, you always need to weight at least $k$ coins at ...
- 183
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
0
votes
1
answer
69
views
Stats problem, stacking cards [closed]
If I have n cards and n stacks of cards, how many ways can I split the cards between the stacks if the order of the cards in the stack is significant but the order of the stacks is insignificant and ...
0
votes
0
answers
48
views
Optimal Strategy for Identifying Lighter Balls: A Balance Scale Puzzle
There are n balls, among which m balls are lighter (and equally light with each other). We have a balance scale; how many times must we weigh at least, in order to find these m lighter balls? We ...
