Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
736
questions
0
votes
0
answers
20
views
Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)
The following a small-scale example meant to illustrate the general problem
Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$
The marbles can ...
- 3
0
votes
1
answer
33
views
Order in a subset
Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
- 11
0
votes
0
answers
31
views
Growth of a set of propositional formulas under partial evaluation
Definitions: Let $n \in \mathbb{N}, n \geq 1$. We write $|\alpha|$ to denote the length in characters of an expression $\alpha$ in propositional logic. We define partial evaluation in the normal way ...
- 921
0
votes
0
answers
18
views
What are some applications of gerrymandering for Electronic Design Automation/Very large-scale integration?
There are many algorithms used for Very large-scale integration design (VLSI) or EDA (Electronic Design Automation). Most of them are challenges that imply some combinatorial/mathematical optimization....
- 1
1
vote
0
answers
25
views
Find an assignment discarding a subset of possible assignments
We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task.
The number of possible assignments is $N!$. Let us call this set of all possible ...
- 11
0
votes
1
answer
41
views
Number of matchings in a bipartite graph having missing edges
Suppose we have a bipartite graph with $N$ vertices on either side.
In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$.
Now ...
- 11
0
votes
1
answer
47
views
Is there an algorithm for the distrubution of ducks into ponds?
The following is small-scale example is meant to illustrate the general distribution problem
Consider 4 parks, each with exactly 1 pond. Parks are marked as vertices in the following undirected graph:
...
- 3
0
votes
1
answer
44
views
Efficient algorithm for finding the target sum
Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
- 1
0
votes
1
answer
45
views
Algorithm to generate all N-size variations of natural numbers
For a size N>=1 (an input variable) I need an algorithm to generate all variations (no duplicates allowed) of natural numbers greater than zero.
For N=1, this is trivial:
...
- 155
2
votes
0
answers
32
views
Bananagrams decision problem - computational complexity
I've been playing Bananagrams recently, and have begun to wonder about the math behind it from a computational perspective. I've tried to formalize the problem as a decision problem below.
Loosely ...
- 21
2
votes
1
answer
43
views
Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"
I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
- 827
1
vote
0
answers
49
views
Are there known algorithms to find a line that intersects a given set of segments?
Are there known algorithms to find a line that intersects a given set of segments?
In:
A finite set of segments.
Out:
A line that cross all these segments or explicit answer that there is no such line....
1
vote
1
answer
56
views
Exact cover matrix for project planning
I'm trying to solve the project planning problem using DLX and exact cover matrix, but I'm struggling to find the set of constraints (columns) and the set of options (rows) to achieve this. Here is a ...
1
vote
0
answers
32
views
Maximum size of a graph with given girth
I am unable to get the bound on the maximum size of a graph of order $n$ with girth $g$. Is there any literature regarding this. I know that there is an asymptotic bound on the size of a graph $G$ ...
- 175
0
votes
1
answer
69
views
On hardness of finding total dominating sets in triangle-free graphs
A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of ...
- 25
2
votes
1
answer
101
views
On hardness of finding dominating sets in triangle-free regular graphs
A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
- 25
1
vote
0
answers
39
views
Finding maximal cliques in a graph represented as a collection of complete biparti graphs
I have a graph whose edges can be very efficiently represented as a set of complete biparti graphs (that may share nodes). Is there a name for such a representation?
And secondly. I want to enumerate ...
- 11
2
votes
1
answer
64
views
Selecting a submatrix of a binary matrix NP hard?
I have the following problem and I am wondering if it is NP Hard or not.
Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$.
A ...
- 23
1
vote
1
answer
37
views
Densest Sub Graph and forbidden Pairs
Given two graphs $G$ and $F$ on the same vertex set $V$. Compute a sub set $\tilde{V}\subset V$ which' sub graph of $G$ is of maximum density and does not have any pair that is connected in $F$.
...
1
vote
1
answer
60
views
Faster finding of a subset of bits with all combinations in the bitstrings
Assume that I have a bunch of bitsets (strings on $\{0,1\}$) of the same length, e.g.:
101110001
001001101
010101010
101001001
101010101
I want to find the largest ...
- 315
1
vote
1
answer
155
views
Reorder columns in a 2d matrix to maximize the count of all repeated subarrays across all rows
I have a matrix (input):
--
c1
c2
c3
r1
AA
BB
CC
r2
CC
RR
BB
r3
EE
DD
FF
r4
KK
DD
EE
r5
DD
GG
KK
r6
PP
QQ
KK
Let's call each matrix cell a namespace. If two ...
1
vote
1
answer
41
views
Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?
Given a bipartite graph $G=(V,E)$ and an integer $l$, how many edge subsets ($E'\subseteq E$) of size $l$ are there such that the degree of each vertex in the resulting subgraph $G'=(V,E')$ is odd?
I ...
- 133
1
vote
0
answers
34
views
What is the worst case time complexity of unranking n choose k combinations (combinatorial number system, combinadics)
The combinatorial number system shows that there is a bijection between the natural numbers less than $n \choose k$ and $n\choose k$ combinations. There is a greedy algorithm for unranking ...
- 111
2
votes
0
answers
45
views
Designing Shortest Route
Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
- 53
1
vote
1
answer
168
views
Iterating over combinations of 4 timestamps from 2 timelines *efficiently*
I need help in finding a more performant algorithm.
I have two timelines in the form of two indexed lists where each element is a floating-point value that represents seconds. The values in each list ...
- 11
0
votes
0
answers
23
views
Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?
A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements.
https://math.stackexchange.com/...
- 1
1
vote
1
answer
62
views
Bin packing with more than one parameter
Usually, in bin-packing, we have objects of sizes $a_1,...a_n$, and each bin has size 1, We need to minimize the number of bins, and for this, there are best fit/first-fit approximation algorithms.
...
- 53
1
vote
0
answers
104
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]
We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
0
votes
0
answers
32
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [duplicate]
We define the set S as {(s1, f1), (s2, f2), ..., (si, fi)}, where each si is the frequency that it is repeated in the multiset T. How many ways can we partition the multiset T into different ...
- 1
1
vote
1
answer
61
views
Generate uniform random vectors
Problem : Consider a random vector $v$ which is uniformly distributed over the sample space $S = \{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\}$ . How to efficiently generate such random vector ?
note :...
- 129
0
votes
0
answers
88
views
Has this problem related to bin-packing and knapsack been studied?
There is a problem I recently encountered in my work which is related to the knapsack and bin packing problems. But I couldn't find the exact problem anywhere.
Say you have some suitcases. Each of ...
- 305
0
votes
1
answer
86
views
Greedy Algorithm for Geometric Set Cover
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 53
0
votes
1
answer
54
views
Geometric Set Cover in one dimension
Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem.
The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
- 53
1
vote
1
answer
59
views
A kind of generalised assignment problem where we minimise error relative to a goal "weight"/"value" - how to solve it?
I apologize if I did not use the terminology entirely correctly in the title. This problem seems to me quite similar to an assignment problem and likely something that occurs in real life in business.
...
- 11
3
votes
1
answer
82
views
Are two regularity properties on hypergraphs equivalent?
Let $H=\left( E_0 ,E_1 ,E_2 , \ldots , E_d \right)$ be a $d$-dimensional full-hyper graph/complex. That is to say, if for some $i\in \left[d \right]$ the hyper-edge $e_j \in E_i$ than for any $i-1$-...
- 125
1
vote
1
answer
129
views
Counting independent sets
I know the Independent set problem is NP-complete. But could there be a more efficient way to count the exact number of different independent sets in an arbitrary, given graph?
- 23
1
vote
1
answer
134
views
Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements
$x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is
sorted if $x_i \leq x_{i+1}$ and $y_i \leq ...
- 123
0
votes
0
answers
46
views
algorithm that determines if there are $a_1+a_2+\dots a_{k-1} =a_k $
Let $A_1,A_2 \dots A_k $ be sets of integers such that $\left|A_{1}\right|+\left|A_{2}\right|+\dots\left|A_{k}\right|=\mathcal{O}\left(n\right) $
Find an algorithm that determines if there are $a_1+...
- 232
0
votes
0
answers
64
views
Number of ways to insert elements into an AVL tree such that there are no rotations
How many ways can we insert elements { 1, 2, 3, .... 7 } to make an AVL tree so that it does not have any rotation?
I broke it down into 2 cases:
Case 1: height of tree = 2, (a complete binary tree) ...
- 108
0
votes
2
answers
66
views
Some questions regarding asymptotic notation of ${n \choose k}$
Is it always the case that ${n \choose k} = O(n^k)$?
If it is, then why does the comment from Clement C. in this post state it is only the case when $k$ is a constant?
If it is not, then why is the ...
- 685
0
votes
1
answer
49
views
BSTs with repeating keys
The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4.
We could try an ...
0
votes
1
answer
51
views
Counting number of 1-hop paths in a sparse graph
Given a sparse undirected graph $G=(V,E)$ where $|E|=O(|V|)$, a one-hop path between a pair of vertices $(u,v)$ is a path in $G$ connecting $(u,v)$ where there is exactly one intermediate vertex ...
- 1
1
vote
0
answers
26
views
Quicksort sampling
This question is in the context of quicksort. Consider that a subarray of distinct elements of size $k$ is sampled from the input array of size $n$, and then we choose a pivot from the sampled ...
- 71
0
votes
0
answers
18
views
The maximal choice smallest grammar algorithm. Is this an exact algorithm or an approximation?
When we speak of a variable, sometimes we will mean the string it expands to, and other times, the variable itself. Let $t \leqslant s$ mean substring.
Take the string $s = a^6$. Then its ...
0
votes
0
answers
32
views
An ingenious exact smallest grammar algorithm for strings over a single letter, $s \in \{a\}^*$. First enumerate the start rules up to commutation
Take $s = a^{10}$ for our example string. Compute the set of all potential grammar reducing variable-rules:
$$
A \to aa \\
B \to aaa \\
C \to aaaa \\
D \to aaaaa
$$
There is always exactly $\left\...
2
votes
1
answer
64
views
Possible approaches to the Ship City problem?
About few ago in my freshman year of college I stumbled across an an old blog post on r/programming posing a programming challenge. Here is the short version of it:
Hundreds of ships would like to ...
- 21
1
vote
1
answer
31
views
Can distance-regular graphs with different intersection arrays have the same number of k-hop neighbors for all k?
I would like to ask a very fundamental question regarding distance-regular graphs. Denote $d(u,v)$ as the distance between node $u$ and $v$. Distance-regular graphs are graphs such that for any pair ...
- 296
1
vote
1
answer
160
views
Max-flow problem with additional constraint
Consider the max-flow problem with a set of additional constraints, each in the following form: the flow on edge $e$ must equal the flow on edge $e'$. My question is how to modify existng max-flow ...
- 71
2
votes
1
answer
86
views
Probability of this random selection
Suppose we have an array of $n$ integers. Suppose that we pick one of these elements uniformly at random and call it $x$. Suppose that $\log n$ elements are also sampled (uniformly at random) from the ...
- 71
0
votes
1
answer
28
views
Finite Automata Mixture Combinatorics
Hello Folks,
I am facing hard time in understanding this, basic question which says, how many possible finite automata ( DFA ) are there with two states X and Y, where X is always initial state with ...
