All Questions
Tagged with combinatorics algorithms
1,042
questions
0
votes
0
answers
14
views
Counting cliques in polynomial time
Let $G$ be a disconnected graph such that every connected component is a $k$-clique, $k \geq 2$. That is, a connected component of $G$ can be a single edge, or a triangle, or a $K_4$ and so on. Is it ...
- 339
9
votes
0
answers
118
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
2
votes
0
answers
41
views
Dividing $N$ coins into at most $K$ groups such that I can get any number of coins by selecting whole groups
Problem
Inspired from Dividing $100$ coins into $7$ groups such that I can choose any number of coins by selecting whole groups . I am interested in the number of possible ways we can get such a split....
- 1,171
1
vote
0
answers
27
views
Knapsack with fixed number of bins?
Constant: d, a fixed number of bins/sacks
Input:
$v_1,v_2,...,v_n$ item profits,
$0<w_1,w_2,...,w_n\leq1$ item weights.
Output: $B_1,B_2,...,B_d$ which are d subsets of $\{1,2,...,n\}$ s.t. they ...
- 11
1
vote
1
answer
33
views
Testing for strong homomorphism in polynomial time
Let $G$ and $H$ be graphs. We say that a map $f:V(G)\rightarrow V(H)$ is a strong homomorphism if for all $u,v\in V(G)$ it holds that $(u,v)\in E(G)$ if, and only if, $(f(u),f(g))\in E(H)$.
Fix $H$ ...
- 823
0
votes
0
answers
35
views
Minimum number of measurements required to find heaviest and lightest from a group of idetntical looking balls having distinct weights.
You are given 68 identical looking balls, each with a distinct weight. You are given a common balance using which you can compare weights of any two pair of balls with a single measurement. Describe ...
- 9
2
votes
0
answers
44
views
Does every collection of edges between two sets of vertices in a plane have a "perimeter" edge suitable for induction inwards?
Joel Hamkins posted this nice problem: https://x.com/JDHamkins/status/1790582025977577591
I quote:
Suppose you have 1000 white points and 1000 black points in the plane, no three collinear. Can you ...
- 9,307
3
votes
1
answer
161
views
How to solve a given combinatorial problem?
Given $n$ balls, which are numbered from $1$ to $n$, and also $n$ boxes, which are also numbered from $1$ to $n$. Initially, $i$-th ball is placed at $i$-th box. Then we are doing the following ...
- 33
1
vote
0
answers
86
views
Is there a measure that produces given values (probabilities or cardinals) for sets $A_1,\dots, A_n$ and all their intersections $A_i\cap A_j, ... $?
Assume that values (e.g., probabilities or cardinals) of a measure on a finite set $\Omega$ are given for sets $A_1,\dots, A_n$ and all of their intersections $A_i, A_i\cap A_j, A_i\cap A_j\cap A_k, ....
- 8,350
1
vote
1
answer
44
views
find the number of ways to distribute 30 students into 6 classes where there is max 6 students per classroom
here is the full question:
Use inclusion/exclusion to find the number of ways of distributing 30
students into six classrooms assuming that each classroom has a maximum capacity
of six students.
Let $...
- 15
0
votes
1
answer
35
views
create a recurrence relation for the number of ways of creating an n-length sequence with a, b, and c where "cab" is only at the beginning
This is similar to a problem called forbidden sequence where you must find a recurrence relation for the number of ways of creating an n-length sequence using 0, 1, and 2 without the occurrence of the ...
- 15
1
vote
1
answer
73
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
26
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} |...
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 ...
2
votes
2
answers
86
views
Is this problem NP-hard？Or what kind of mathematical problem does it belong to?
Assuming there are n types of gifts, each with a number of $a_n$. Now we have to pack them into gift packs, each containing several types of gifts, and each gift has only one.If a gift package ...
- 33
2
votes
0
answers
17
views
Mechanic shop with limited delay capacity
Suppose a mechanic shop serves $M$ customers for $N$ days. Each morning, each customer brings in a number of parts to repair (denoted by $0\leq A_{i,j}\leq A_{max}$).
Suppose all parts need to be ...
- 75
1
vote
1
answer
177
views
Total number of distinct possible marks for given number of questions and marks (ZIO 2023 Q1)
Q. There is an exam with N problems. For each problem, a participant can either choose
to answer the problem, or skip the problem. If the participant chooses to answer the
problem and gets it correct, ...
- 11
1
vote
0
answers
47
views
Squared multiplicty minimization in multiple set choosing problem
The problem is the IOI 2007 competition's Sails problem. It has also appeared in Pranav A. Sriram Olympiad Combinatorics notes (Chapter 1 Exercise 14). I copied the problem description from Pranav. ...
- 11
5
votes
1
answer
153
views
What are the chances that the Enemy/Defender game has a stable solution?
There is a game called Enemy/Defender that you might play with kids. The setup is as follows:
Everyone stands in a circle. You say, "Look around the circle and select someone (at random) to be ...
0
votes
0
answers
35
views
Understanding the optimality bound for Greedy algorithm in maximization of monotone submodular functions
I am trying to understand whether the Greedy algorithm guarantee for maximization of monotone submodular functions with a cardinality constraint is a lower bound on the performance. This is the ...
1
vote
1
answer
92
views
A shuffling algorithm that limits the number of consecutive repetitions?
This question comes from Stack Overflow. I feel that we need more of a mathematical breakthrough, so I forward the question here.
I also found a similar problem that seems to be a special case of this ...
- 11
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
0
votes
2
answers
62
views
Finding the minimum value of K for non-repeated sums
Given a set $A$ containing 10 positive integers, with the largest element denoted as $K$, we calculate all possible sums of elements from set $A$, including sums of 2, 3, 4, and so on, up to all 10 ...
- 143
2
votes
0
answers
87
views
Finding all possible valid values of a set based on a list of rules.
I'm working on a programming project and I stumbled into a bit of a problem. I think it's not an impossible problem, but I'm guessing it would involve some math. It would be amazing if anyone can ...
- 121
1
vote
1
answer
48
views
Indexing function for placements of identical balls into distinct boxes.
I am trying to find out if there is a mathematical function which can take n objects and place them in m boxes in a way that is indexed?
For example if I had 3 balls and I wanted them in 4 boxes, the ...
- 111
0
votes
0
answers
24
views
Counting Paths in the XY Plane (Discrete math) [duplicate]
I need help with the following mathematical task:
A particle moves in the xy-plane according to the following rules:
U: (m, n) → (m+1, n+1)
L: (m, n) → (m+1, n-1)
where m and n are integers. I need ...
- 39
3
votes
1
answer
97
views
Expected Length of Maximum Decreasing Subsequences in Random Sequences
Given $ n $ distinct numbers that are randomly shuffled to form a sequence $ A = [a_1, a_2, \ldots, a_n] $, we select the largest number $ x_1 $ from the sequence. Subsequently, we pick the largest ...
- 1,231
2
votes
2
answers
84
views
Analytic solution for number of paths with length $k$ on an $n \times n$ Chessboard allowing Self-Intersecting?
Consider an $n \times n$ chessboard where the journey begins at the bottom-left corner $(1, 1)$ and concludes at the top-right corner $(n, n)$. How many distinct paths are available that necessitate ...
- 1,231
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
1
vote
1
answer
318
views
Converting Undirected Graphs to a Tree While Preserving Edge Information
I'm working on a problem where I need to convert an undirected and unweighted graph with cycles into a tree while preserving the edge information (all the edges from the graph are preserved in the ...
- 11
1
vote
2
answers
71
views
When can a deck be shuffled by shuffling fixed subdecks?
Suppose I want to shuffle a deck of $n$ cards, but I have a problem -- for some reason, I am only able to shuffle at most $n-1$ cards at a time at some fixed indices. For example, if $n=5$, I could ...
- 685
4
votes
1
answer
283
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
1
answer
46
views
Last step of an intense algorithm requiring efficiency: A closed form for $\sum_{s=2}^{\lfloor\frac{T}{2}\rfloor}{2s-1 \choose s-2}{T \choose T-2s}$?
I'm working on an algorithmic problem for HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler106/problem
The broad overview of the problem is finding how many evenly-sized ...
- 11
3
votes
1
answer
115
views
Social golfer problem with additional requirement
I need to write a program that sorts people into groups.
To give a little context: The aim of the program is to create an equitable distribution of tasks and people for a school trip. Every day the ...
