Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
676
questions
1
vote
1
answer
16
views
A lower bound for the makespan of heterogenous fog nodes
Why there is a sigma in the denominator of equation (8) in the picture? suppose we have n tasks and m fog nodes.
- 25
0
votes
1
answer
78
views
Sample a set of N numbers without replacement, each element taken from N different weighted sets
Here's my problem: I have $N$ sets of integers $S_i$ where $|S_i| = n_i \forall i \in [1,N]$ each with non-uniform weights $W_i = \{w_{i,1}, ..., w_{i,n_i}\}$ such that $\sum_{j}{w_{i,j}} = 1$. I want ...
- 13
0
votes
1
answer
46
views
Boolean Logic for Floats
I would like to know whether a theory exists which generalizes boolean logic to floats.
Specifically, assume that instead of booleans 1 and 0, I have True/False tendencies, such as 0.9, where 0.1. ...
1
vote
2
answers
66
views
N Queens Problem - Number of Possible Placements
So, I have been looking into the famous back tracking problem called N Queens. The problem is essentially finding the number of possible ways you can place a n number of queens on a n x n chess board ...
- 113
1
vote
1
answer
69
views
Generating the n-th number with k bits set, is it possible?
Generating numbers with $k$ bits set for a poker simulation
Context
I'm trying to generate all possible Texas Hold'em games for $p$ players, which means there will be at most $2 \cdot p + 5$ cards at ...
- 135
0
votes
0
answers
16
views
Is Disjoint Edge Weighted Group Steiner Tree problem equivalent to the regular Steiner Tree problem?
Disjoint Group Steiner Tree (DGST) is the following problem:
Instance: a positive edge-weighted graph $G=(V,E,w)$, a collection of $k$ vertex sets (groups) $S_1,\dots,S_k \subseteq V$, such that $S_i \...
2
votes
1
answer
71
views
Question about stack permutations
I encountered an exercise in which I am struggling to understand the solution provided even though I spent a lot of time trying to figure it out.
The exercise is the following and was taken from the ...
- 65
0
votes
0
answers
41
views
The relationship between types of registers / feedback functions and de Bruijn sequences, and how these feedback functions are created
I have been learning about de Bruijn sequences recently, and have a decent sense what they are. There seem to be 3 or 4 primary methods for generating de Bruijn sequences:
Feedback functions/...
- 1,871
1
vote
0
answers
22
views
How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?
I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
- 1,871
1
vote
1
answer
38
views
What is a de Bruijn sequence exactly?
I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess).
There are two good resources I ...
- 1,871
1
vote
0
answers
24
views
matching vector families that form a group
Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)?
You can find the definition of MV families here:
https://homes....
- 21
1
vote
1
answer
21
views
Number of binary words that form a group of Hamming weight at most d
Consider binary words in {0,1}^n whose Hamming weight is at most some constant d. We want to select some of these words such that they form a group under addition. How many words can we choose at most?...
- 21
0
votes
0
answers
29
views
How can I generate all combinations of 2 sets of unique numbers? How are those called?
I want to generate 2 sets from N elements.
Sets must be unique in the combination of sets
Numbers must not repeat across the 2 sets
Sets can have any amount of numbers, but must not be empty
...
- 101
1
vote
2
answers
29
views
Generating combinations that fulfill certain restrictions for graphs
I am working with graphs, let's say I have 4 nodes, named A, B, C, D, each node has to be connected a certain number of times to the other nodes.
A: 3, B: 3, C: 2, D: 2
This means that A and B are ...
0
votes
0
answers
24
views
Graph with constant edge connectivity that remains connected after edge removals
I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
- 149
2
votes
0
answers
27
views
Proving existence of sinkless orientation on graph with minimum degree 2
I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge.
As a ...
- 149
1
vote
1
answer
32
views
Trivial vertex cover in regular graph is 2-approximation Proof
I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover.
My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
- 149
2
votes
1
answer
68
views
Can all teams in a tournament finish with the same points? If yes, how can there also be fewest drawn matches?
n teams play pairwise matches. If the match is a draw, both teams get 1 point.
The winner gets 3 points, and the loser gets 0 points otherwise. Is it possible that all n teams
finish with the same ...
- 23
1
vote
1
answer
174
views
Optimal coverage of arbitrary mask by strided masks
Say we have bit mask with some bits on and off:
1001110010101
We want to "deduce pattern", by covering this mask with as few strided masks as possible.
...
0
votes
1
answer
40
views
Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n
Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$.
My attempt:
At each step I will also remove the edge from the graph that I am adding to the ...
- 149
1
vote
1
answer
34
views
Hints for efficient computation of the maximum length of a binary sequence
Given a positive integer $n$ I would like to compute $f(n)$, the maximum possible length of a binary sequence such that any substring of it (subsequence with consecutive elements), of length $n$, ...
- 113
3
votes
0
answers
57
views
What is the name for this minimal satisfying set covering problem? [duplicate]
Preface
Hello! I have a problem here that's difficult for me to Google, and I don't know if there's a name for it. It feels like a set cover problem of some kind, but I'm very unfamiliar with ...
- 31
3
votes
1
answer
103
views
Analytic combinatorics and less-precise running times
Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
- 315
0
votes
0
answers
9
views
Algorithmic Complexity of Enqueue and Dequeue of a Special Queue [duplicate]
The Canteen Queue Problem: There is a common canteen for $K$ hostels. Each hostel (co-ed) has some $N_1, N_2,...,N_K$ students. These students line up to pick up their trays in the common canteen, in ...
6
votes
1
answer
109
views
Find all n bit numbers with k ones and unique under circular shift
I am trying to traverse through all uint64_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code.
The problem ...
- 61
0
votes
0
answers
46
views
Graph theory book for beginners
I need a book recommendation for graph theory which supposes background in set theory. I want to cover those questions first as graph theory is part of combinatorics. Can you recommend me a book which ...
- 59
0
votes
0
answers
25
views
graph representation of a Boolean function
I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
0
votes
0
answers
31
views
How to generate supersets from a finite number of subsets efficiently
Let $F$ be a set, for instance $\{a,b,c,d,e \}$. Suppose I have a set of subsets of cardinality two obtained from $F$:
$ ${ a,b },$\{b,c\},${a,d}
I want to create every possible set of cardinality ...
- 111
0
votes
1
answer
28
views
Determining runtime of a theoretical program (question of extraordinary complexity)?
I apologize in advance, as I don't have a clue to which stackexchange to post this question! I beg you to not delete this question, as I have chronic pain and it is very important to me!!! I actually ...
- 3
4
votes
1
answer
76
views
Attempt to reduce to problem of inner product
The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$?
The problem of max product: likewise two sets each $n$ vectors (...
2
votes
1
answer
29
views
Given a set $S =\{1,2,...,k\}$, how to generate variations of length $n, (k<n)$, such that each element of $S$ appears at least once?
Take, for example:
$$S=\{1,2,3\}\to k=3$$
$$n=4$$
The desired output for this would be:
...
- 23
1
vote
0
answers
24
views
Something wrong with my recursion definition - Best Possible Combinatorial Sum from a given list of numbers [closed]
I was trying to solve a problem "Write a function bestSum(targetSum, numbers)` that takes in a targetSum and an array of numbers as arguments.
The function should return an array containing the ...
- 11
2
votes
1
answer
76
views
What is the maximal length of a CNF formula?
The question is quite short. Let $k$ be a given number. What is the maximal length of $k$-CNF formulae can we compute, over the set of binary variables $\left\{ x_1 ,\ldots, x_n \right\}$?
The way I ...
- 1
1
vote
1
answer
48
views
Minimum steps needed to partially cover a sequence of points on a grid
Problem statement: You are in a 2D grid where you can move in any of the 4 directions, no obstacles. You start at position (0, 0).
We say that you partially cover a point $(x,y)$ if your position has ...
- 11
0
votes
0
answers
39
views
ILP - Maximize the number of pairs of variables with the same value
I have a 0-1 integer linear program for a set of $2n$ variables $S = \{x_1, ..., x_n, y_1, ..., y_n\}$. My objective is to maximize the number of pairs $(x_i, y_i)$ such that $x_i = y_i$, $i = 1, ..., ...
- 143
0
votes
0
answers
37
views
Permutation of a valid bracketing
Given a permutation $\pi$ of length $2n$, how can we find a valid bracketing (balanced string of opening and closing parentheses) which will remain valid when permuted under $\pi$?
For example, for $\...
- 31
4
votes
0
answers
67
views
Generating graphs with partially overlapping cliques
Currently, I am working on a research project where I will utilise reinforcement learning for the diversified top-$k$ clique search problem. To train the reinforcement learning algorithm, I need to ...
- 41
0
votes
0
answers
24
views
Optimization Problems which very deep local minima
I am looking for combinatorial optimization problems which have very deep local minima.
So I am searching for the global optimum (which is not unique).
Are there some games or problems you know which ...
- 51
3
votes
1
answer
54
views
Iteratively enumerating all permutations of $N$ objects using a generating set
The group theory of $S_n$ shows that all permutations of $n$ objects can be generated from the $n$-cycle $a:=(1 2 3 .. n)$ and the transposition $b:=(1 2)$. (See Theorem 2.5 at https://kconrad.math....
- 133
3
votes
2
answers
265
views
All possible sum of each array combination
Is there a name for this algorithm?
I have an array {1,2,3} and all my possible sums are
{1},{2},{3},{1+2},{1+3},{2+3}, {1+2+3} = {1},{2},{3},{4},{5},{6}
{1,1,2} => {1}, {2}, {3}, {4}
I tried to ...
- 31
0
votes
1
answer
13
views
Online binary tree creation via $a\to ax$ and $ab\to a(bx)$
I wish to construct a sequence of unlabeled binary trees $T_n$ satisfying the following properties:
$T_n$ has $n$ leaves
$T_n$ is well balanced (height $\lg n+O(1)$)
$T_n$ is obtained from $T_{n-1}$ ...
- 451
2
votes
1
answer
42
views
Find all combinations of adjacent records matching a graph template
I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from ...
- 23
1
vote
2
answers
66
views
How many Integers can be represent in Double-Precision floating-point form
How to calculate the number of Integers that can be represent in Double-Precision floating-point form?
- 15
3
votes
1
answer
26
views
On a coloring that uses $2\cdot a\left( G \right)$ colors
Denote $G=\left( V, E \right)$ arboricity by $a\left( G \right)$. I'm trying to understand why $G$ is $2\cdot a \left( G \right)$-colorable. I came across this post. Both the OP and the answer say ...
0
votes
0
answers
18
views
Method for minimizing relays in a switching/steering network - combinatorics/CSP algorithm exists?
This question is borne from the electrical engineering world, so I first asked it there, but it's really more of an algorithm optimization problem that everyone here might be better suited to help ...
1
vote
3
answers
551
views
The number of ways of insertion in binary search tree
The number of ways in which the numbers $1,2,3,4,5,6,7$ can be inserted in an empty binary search tree, such that the resulting tree has height 5, is _________.
Note: The height of a tree with a ...
0
votes
1
answer
111
views
What's the time complexity of finding all size-$k$ combinations from a set of size $n$?
I'm wondering what's the time complexity of finding all size-$k$ combinations from a set of size $n$(note that $k$ is a known and fixed constant, say $k=3$)? How does it differ from the time ...
- 103
0
votes
0
answers
119
views
A Variant to "Boats to Save People"
This question is a variant of LeetCode 881. Boats to Save People by removing the restriction of "each boat carries at most two people at the same time" from the original question.
Problem ...
- 1,071
1
vote
2
answers
45
views
Having a set of non unique Key-Value pairs, how can I optimally find a lowest sum subset if distinct keys?
I understand that the title might be confusing so I'll lead with an example.
I have the following set (actually a map):
...
- 141
0
votes
1
answer
174
views
Algorithm to return all possible ways to divide n unique elements into groups of size k
If I have as set N of n unique elements, is there a known algorithm that can return every possible way in which they can form groups of size k?
Eg: If N = { A, B, C, D} and k = 2, then the algorithm ...
