Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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\...

1
2 3 4 5
14