Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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.
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 \...
user avatar
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 ...
user avatar
  • 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/...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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....
user avatar
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?...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
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 ...
user avatar
  • 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$, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 (...
user avatar
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: ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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, ..., ...
user avatar
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 $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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....
user avatar
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 ...
user avatar
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}$ ...
user avatar
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 ...
user avatar
  • 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?
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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): ...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
14