Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
652
questions
0
votes
0answers
16 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
0answers
26 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 ...
0
votes
1answer
27 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 ...
4
votes
1answer
68 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
1answer
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:
...
1
vote
0answers
18 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 ...
2
votes
1answer
26 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
vote
1answer
31 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 ...
0
votes
0answers
32 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, ..., ...
0
votes
0answers
35 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 $\...
4
votes
0answers
61 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 ...
0
votes
0answers
23 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 ...
3
votes
1answer
53 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....
3
votes
2answers
60 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 ...
0
votes
1answer
12 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}$ ...
2
votes
1answer
40 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 ...
1
vote
2answers
41 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?
3
votes
1answer
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
0answers
16 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 ...
0
votes
0answers
19 views
Proving Correctness of Knapscap Fraction Algorithm
I am trying to prove correctness of Knapsack algorithm below:
Algorithm works by taking rations of values of items to weights and then sort them in decreasing order taking $O(n\log{n})$ time. So to ...
1
vote
3answers
339 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
1answer
42 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 ...
0
votes
0answers
48 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
vote
2answers
43 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):
...
0
votes
1answer
101 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 ...
1
vote
0answers
23 views
Maximum number of edges with k components
Given $N$ vertices and $K$ components what is the maximum number of edges that may exists ? I just got gut instinct that it will be maximum if we take one set with $k-1$ vertices and this will have no ...
0
votes
1answer
46 views
Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string
This was an algorithm problem but I am having problems in formulating it.
I have a certain approach but I do not know how to fully execute:
Given
26 letters in total
All possible strings of length n
...
1
vote
1answer
77 views
Faster algorithm for specific inversion count (part 2)
Following the issue from Faster algorithm for a specific inversion:
We have a permutation (a derangement actually) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$.
I want to compute ...
3
votes
1answer
541 views
Faster algorithm for a specific inversion
There is a permutation (more precisely a derangement) $\sigma$ of the set $\{0,1,\dots,n-1\}$ with cardinality $n$.
I want to compute the following counts (a kind of inversion):
$$K(\sigma )_{i}=\#\{j&...
1
vote
1answer
23 views
Simple problem of combinatorics
There are $3$ red socks, $4$ green socks and $3$ blue socks.You choose $2$ socks. The probability that they are of the same color is
Answer:
$\dfrac{^{3}C_{2}+^{4}C_{2}+^{3}C_{2}}{^{10}C_{2}}=\dfrac{4}...
3
votes
1answer
52 views
Equally coloring the edges of square tiles that form a grid
I need to generate a set of square tiles that are colored and are grid-able. Each square tile must have a unique set of 4 colors and each exterior edge of each tile is colored with a different color. ...
6
votes
2answers
224 views
Can this special case of bin packing be solved in polynomial time?
Consider a multiset of $n$ integers, where each integer is between $1$ and $3 M$. The sum of all integers is $3 S$. There are three bins. The capacity of each bin is $C = S + M$.
Is there a polynomial-...
2
votes
0answers
81 views
An unknown combinatorial optimization problem
I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$.
Let $\sigma_{i\_H}$ ...
6
votes
1answer
76 views
Number of combinations without given pairs
Given a set of elements {e1, e2, ... en}, a set of pairs of these elements (each element may be present in several pairs) and a number k.
I need to count how many combinations of size k exist which ...
1
vote
0answers
26 views
Is the problem "find the sequence of $N$ numbers between 1 and $D$ with least cost", NP-hard?
Consider sequences $p=(p_1,\dots,p_N)$ (the order matters) of length $N$, where $p_i\in\{1,\dots,D\}$ for fixed $D$. Moreover, consider a cost function $c:\{1,\dots,D\}^N\to\mathbb{R}$ which comply $c(...
0
votes
1answer
33 views
Is this variation of the traveling salesman problem NP-hard
Consider the following setting. You have $n$ cities, and there is a cost to travel from a city $i$ to a city $j$ given by $c_{ij}>0$ where $c_{ij}\neq c_{ji}$. Moreover, if you are traveling to ...
0
votes
0answers
39 views
Is this combinatorial seach problem NP-complete?
The context: Consider the following optimization problem. Let $f_1,\dots,f_L:\mathbb{R}\to\mathbb{R}$ arbitrary (continous) functions for $L>1$ and $x_k\in\mathbb{R}$ evolve according to
$$
x_{k+1}...
4
votes
1answer
68 views
Combinatorics - how many $c$-distinct sets are possible?
I'm not sure if CS SE is the right place for this question, but since originally this question was in the CS area (and I translated it to a mathematical form), I will post it here.
I am given two ...
1
vote
1answer
65 views
Solving problems by dynamic programming plus quantization to avoid combinatorial explosion
The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to:
$$ x_{k+1} = f(x_k,u_k) $$
where $k \in \{ 0,\dots,N-1 \} $, ...
0
votes
1answer
20 views
Divide members into multiple teams without overlap
I'm trying to separate people from a pool into several smaller groups. The group-size should always remain the same. People can be part of several groups - but no two people can be part of more than ...
1
vote
0answers
30 views
How to compute all inequivalent (under Aut(P)) nonnegative integer weight assignments (with fixed sum) to the vertices of a finite poset P?
Let $P$ be a poset on $n$ points, $\text{Aut}(P)$ its automorphism group, and $a_1,a_2,\dots,a_k$ the lengths of the orbits under $\text{Aut}(P)$.
Goal: An algorithm to generate a member from each ...
2
votes
0answers
39 views
Efficient solution to this scheduling problem or integer optimization problem
Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to
$$
P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)}
$$
where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
3
votes
0answers
53 views
Make Change in Linear Time
The question is motivated by this post on StackOverflow.
Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
1
vote
0answers
19 views
Streaming maximum pair matching with limited memory
I am trying to find as many pairs of elements as possible from two distinct data streams, while being constrained by the number of elements I can hold in memory at any given time. Once a pair of ...
3
votes
1answer
45 views
Upper bound on the number of subgraphs in a tree
Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.
For example, consider the ...
4
votes
1answer
43 views
Model Counting for Sum of Conjunctive Formulas
Problem:
Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.
Input: We are given a positive integer $C$ ...
2
votes
2answers
116 views
Produce all unordered unique combinations of N-sized subsets of an m·N-sized set
Say there is a set of m·N named elements. How to produce all the (unordered) combinations of N-sized subsets?
For example, m=2 and N=2, the elements are called A, B, C and D. There will be 3 ...
2
votes
0answers
28 views
Is this a variant of "Path Covering"?
According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G".
In my research, I met a similar problem. There, you can add ...
4
votes
0answers
67 views
Number of permutations with satisfactory triangles
We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
1
vote
1answer
61 views
Not satisfiable 3SAT instance implications
Suppose we have an instance of 3SAT that is NOT satisfiable and we say $S$.
If in $S$ there are the following $8$ clauses
$\left(a\vee b\vee c\right)\wedge\left(a\vee\bar{b}\vee c\right)\wedge\left(a\...
