Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
581
questions
4
votes
2answers
80 views
Min path cover for a three-layer graph with all paths traversing all layers
Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...
0
votes
0answers
27 views
Algorithm for specific load balancing/arbitration problem
I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
1
vote
1answer
19 views
Upper bound on size of minimal binary coverage code
Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that ...
0
votes
1answer
26 views
Bottleneck TSP with repeated nodes
I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
1
vote
2answers
37 views
Floating-point oblivious way to compute multiset numbers
I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
4
votes
2answers
257 views
Given a row sum vector and a column sum vector, determine if they can form a boolean matrix
For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:
$$
\begin{...
3
votes
0answers
70 views
Speeding up the Rummikub algorithm - explanation required
Regarding this question: Rummikub algorithm.
I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
1
vote
1answer
11 views
Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
0
votes
1answer
53 views
Balanced sub-sequence
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of ...
3
votes
1answer
52 views
Topological sort where some nodes can't come in between two other nodes
I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node ...
2
votes
0answers
42 views
What is the largest sum that can be constructed with the given recipes?
There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$.
There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to ...
2
votes
0answers
22 views
How to linearly combine loss functions to preserve optimal substructure property?
I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
3
votes
1answer
45 views
Combinatorial Problem similar in nature to a special version of max weighted matching problem
I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.
I have a ...
0
votes
1answer
32 views
Approximate bin-packing?
Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to ...
2
votes
1answer
15 views
Maximum Chromatic number of Cayley Graphs with large degree
It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}...
0
votes
0answers
36 views
finding the combinatorial solutions of series and parallel nodes
I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, ...
0
votes
1answer
46 views
Combinations of set unions
I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1
\cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$...
1
vote
0answers
53 views
Number of words of length n for special language
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
2
votes
1answer
60 views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldnāt come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
2
votes
1answer
82 views
Maximization problem on finite collection of finite sets
Problem
I am considering the following maximization problem:
Input is a finite collection of finite sets $\mathcal{F} = \{ X_1, X_2, \ldots, X_n \}$.
Goal is to find a subset $G \subseteq \mathcal{F}$...
0
votes
0answers
22 views
Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling
I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
0
votes
0answers
18 views
Is the number of sub-boolean algebras of a set with size of n equal to Bell(n)?
In boolean algebra (P(S),+,.,ā) we must have S as 1 and {} as 0 in every possible sub-boolean algebra to hold id elements.
We must have S-x for every subset xāS to hold complements.
It seems like ...
-1
votes
1answer
79 views
Number of sequences of given type
Consider that there is sequence $a$ of length $n$ ,$a=[a_i,0\le i\le n]$. Now you are given with $\text{lcm}$ of some pairs of number from list that is, $\operatorname{lcm}(a_i,a_j)=k$ for $0\le i,j\...
0
votes
1answer
33 views
“Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations
In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head.
Let $x_i$, $ 1\leq ...
1
vote
0answers
21 views
Space complexity of using a pairwise independent hash family
I'm trying to analyze the space complexity of using the coloring function $f$ which appears in "Colorful Triangle Counting and a MapReduce Implementation", Pagh and Tsourakakis, 2011, https:...
2
votes
1answer
39 views
Streaming algorithm for counting triangles in a graph
As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it ...
0
votes
0answers
17 views
How to consider combinatorial optimization problem with multiple objectives?
I am considering a combinatorial optimization problem with two objectives. The two objectives have a trade-off between each other which means if I minimized the first objective alone it gives the ...
1
vote
1answer
70 views
Lexicographic permutation
Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now ...
4
votes
1answer
54 views
Algoritm to sample an even subgraph of a graph
In some problems related to the Ising model in physics and mathematics the following problem comes up:
Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep ...
0
votes
0answers
20 views
About number of NFSTs
Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
1
vote
3answers
54 views
Proving a solution for the $n$-Queens Puzzle
Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens ...
1
vote
0answers
98 views
Best algorithm for RenyiāUlam Game with lies [closed]
Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type).
Game :
$A$ chooses an element in $\{1,2,\dots,n\}$.
$B$ tries ...
2
votes
2answers
59 views
Is there a dynamic programming solution to the student allocation problem?
The student project allocation problem I am trying to solve goes as follows.
There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
Each student makes a top $3$ of their ...
1
vote
1answer
25 views
Where is the theory about “binary toggling games”?
Let us -- using parameters $M, N$ and $L$ --
create an ordered set of size $M$ of $N$-bit long vectors $V$ and initialize them randomly: $V_k[i] = b \sim Bin(n=1, p=0.5)\ \forall i \in
\{0\ ..\ N-1\}...
-1
votes
2answers
64 views
I am unable to understand the logic behind the code (I've added exact queries as comments in the code)
Our local ninja Naruto is learning to make shadow-clones of himself and is facing a dilemma. He
only has a limited amount of energy (e) to spare that he must entirely distribute among all of his
...
2
votes
1answer
19 views
Enumerating every “partnering” without repeating partners
I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with ...
0
votes
1answer
77 views
Asymptotic complexity of Combination sum problem vs Coin change problem
I've been looking at the following combination sum problem:
...
0
votes
0answers
12 views
How to get started with multi-level pairwise combinations
Let's say we have 4 ranks: 1-4
Every rank has a set of unique nodes, each pair of same-rank nodes can be combined to create a node of a rank 1 level higher, in any number of combinations:
...
2
votes
1answer
149 views
Organizing a “speedback”
Speedback is the merging of speed-dating with feedback: a 2 min. 1-on-1 talk with all members of a group of people.
I'm in a team and I want to plan the ideal speedback setup: all team members have ...
0
votes
0answers
44 views
Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph
This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
0
votes
0answers
21 views
Powells Method for 2 Variables?
I've been studying this YouTube video on Powells method and it looks like when we have a single variable we start at the upper and lower bounds of the variable and then we keep dividing the search ...
3
votes
2answers
297 views
Algorithm to generate combinations of n elements from n sets of m elements
Suppose I have 3 sets of 2 elements: [A, B], [C, D], [E, F], and I wanted to generate all possible combinations of 1 element from each set, such that the result of ...
0
votes
0answers
32 views
Fractional knapsack with setup costs
I am considering a variant of the classical fractional knapsack problem, it's written in the following integer programming form
Here $v_i, c_i, w_i, b$ are all positive. $c_i$ can be interpreted as ...
0
votes
1answer
33 views
Counting directed graphs
I am trying to find a computable, injective and bijective function $f: \mathbb{N} \to A$ where $A$ is the set of all (finite) directed graphs up to isomorphism (also with no edge repetitions). Which ...
2
votes
1answer
61 views
How to solve the bin packing problem with conflicts?
I'm trying to devise an algorithm to solve the bin packing problem with conflicts (sometimes referred to as BPPC, or BPC).
The problem is defined as follows: consider a set $V$ of $n$ items, where ...
2
votes
1answer
79 views
Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic)
I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? ...
1
vote
0answers
184 views
Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
2
votes
1answer
72 views
Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?
A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT ...
1
vote
0answers
44 views
Minimun k-union from a different angle
I'm looking for work done on solving some problem which is very similar to the minimum k-union.
The problem:
There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,...
0
votes
1answer
41 views
Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria
You have to find out the number of good strings of length N characters in size which you can make using characters A B and C.
A string is a good String if it satisfies the following three criteria:
...
