Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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 ...
silass0's user avatar
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 ...
Dave's user avatar
  • 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 ...
ShyPerson's user avatar
  • 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....
isimo00's user avatar
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 ...
akhil's user avatar
  • 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 ...
akhil's user avatar
  • 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: ...
silass0's user avatar
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 ...
jamesw1's user avatar
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: ...
Barney's user avatar
  • 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 ...
AbsentMynd's user avatar
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 ...
Mike Battaglia's user avatar
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....
Leonid Dworzanski's user avatar
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 ...
Mohamed Challouf's user avatar
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$ ...
vidyarthi's user avatar
  • 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 ...
Ankit Gayen's user avatar
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 ...
Ankit Gayen's user avatar
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 ...
Bob Lucassen's user avatar
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 ...
D. Sena's user avatar
  • 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$. ...
Daniel Schwegler's user avatar
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 ...
Dmitry's user avatar
  • 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 ...
night-crawler's user avatar
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 ...
QNA's user avatar
  • 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 ...
Quantum Guy 123's user avatar
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 ...
Sandra's user avatar
  • 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 ...
Enyium's user avatar
  • 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/...
Amir's user avatar
  • 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. ...
Sandra's user avatar
  • 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 ...
AmirHosein Adavoudi's user avatar
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 ...
Amir's user avatar
  • 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 :...
C.C.'s user avatar
  • 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 ...
Rohit Pandey's user avatar
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 ...
Sandra's user avatar
  • 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 ...
Sandra's user avatar
  • 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. ...
edwi's user avatar
  • 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$-...
Benicio Agüero's user avatar
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?
Mirco Paul's user avatar
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 ...
77H3jjuu's user avatar
  • 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+...
Danny Blozrov's user avatar
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) ...
Arun Madhav's user avatar
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 ...
J. Schmidt's user avatar
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 ...
prototycoon2's user avatar
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 ...
Jason's user avatar
  • 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 ...
joeren1020's user avatar
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 ...
MathCrackExchange's user avatar
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\...
MathCrackExchange's user avatar
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 ...
Gabe Kelly's user avatar
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 ...
zbh2047's user avatar
  • 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 ...
lchen's user avatar
  • 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 ...
joeren1020's user avatar
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 ...
Niraj Jain's user avatar

1
2 3 4 5
15