Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
628
questions
1
vote
0answers
37 views
Finding the optimal combination of matrices to multiply that maximise the result when multiplied
I have a 100000×60000 matrix where each element is either a 1 or 0. A 1 represents a signal to do something whereas 0 means to do nothing. Each column represents a different strategy (where strategies ...
0
votes
0answers
22 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
...
2
votes
1answer
71 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
524 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}...
1
vote
1answer
37 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. ...
5
votes
2answers
118 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
76 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
75 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
28 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
0answers
49 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 ...
0
votes
1answer
35 views
reference request: solving problems by dynamic programming + 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), k=0,\dots,N-1
$$
given some $x_0$ and ...
0
votes
1answer
9 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
38 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
50 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
17 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
37 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
39 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
89 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
23 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
64 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
54 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\...
2
votes
1answer
21 views
Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?)
I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used ...
0
votes
1answer
43 views
Combinations (repetition not allowed & order not important)
How to compute a table of numbers (all possibilities), where repetition is not allowed and order is not important.
Example:
I have a set of prime numbers. In this example I have four: {3,5,7,11}, but ...
2
votes
1answer
41 views
Compressing a bit string when I know how many 1s and 0s there are
Say I have a 256 bit bit-string, and I know that there are 16 ones and 240 zeros. I know that this bit string can be compressed, because there are only 256 choose 16...
4
votes
2answers
96 views
Why does my code work: bijecting binary trees to Dyck paths
The number of Dyck paths (paths on a 2-d discrete grid where we can go up and down in discrete steps that don't cross the y=0 line) where we take $n$ steps up and $n$ steps down follows the Catalan ...
2
votes
1answer
125 views
Number of substrings possible with even characters
Consider a string 'ABBAA'
Possible substrings with even number of characters are $4$
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even - ($0$)
Similarly 'BB' ...
2
votes
0answers
12 views
Number of substrings possible with even characters [duplicate]
Consider a string 'ABBAA'
Possible substrings with even number of characters are 4
'ABBA' : Count of 'A' is even and 'B' is even
'AA' : Count of 'A' is even and 'B' is even ($0$)
Similarly 'BB' and '...
1
vote
1answer
21 views
Probability of arising of simple graph in configuration model
I am studying a configuration model building $d$-regular graphs and reading the following article:
The expansion of random regular graphs by David Ellis.
I am stuck on the following step:
Each simple ...
1
vote
1answer
74 views
Create binary numbers with a described pattern
I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
1
vote
2answers
116 views
Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?
I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ?
I don’t have specific topic that I care more about ...
0
votes
0answers
36 views
How to solve this combinatoric problem without bruteforce
I'm trying to solve the following problem :
A tile results of a number and a color.
a tile can be black, red, orange or blue.
a tile number is >= 1 and <= 15.
Given a random set a tiles (a ...
1
vote
1answer
46 views
Number of substrings with exactly k distinct characters
Given a string s and an int k, return an int representing the number of substrings (not unique) of s with exactly k distinct characters. If the given string doesn't have k distinct characters, return ...
0
votes
1answer
26 views
Matching with specific cardinality
In a weighted graph $G(\mathcal{V},\mathcal{E})$ where $w(i,j)$ is the weight of the edge $(i,j) \in \mathcal{E}$. How can I find a maximum weighted matching with a specific size (i.e specific ...
4
votes
1answer
71 views
Bin packing when items can be broken
In the bin packing problem, there are some $m$ items of size less than $1$, and they have to be packed into as few as possible bins of size $1$. The problem is NP-hard, but if we are allowed to break ...
1
vote
0answers
70 views
Covering Variation of Longest Common Substring
Given three binary strings, find the maximum possible length of a contiguous block of 1's formed by shifting and overlapping the strings.
This may be interpreted as finding the maximum window size $k$...
1
vote
0answers
32 views
Binary ↔ Gray permutation matrix
Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements.
...
0
votes
0answers
34 views
How many different values can a shared variable take in concurrent computing?
Question:
Is there a way to find out number of different values that a shared variable can take in concurrent computing, in general, without listing all the possibilities and then counting the ones ...
2
votes
1answer
79 views
maximum cardinality weighted matching
I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.
Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{...
0
votes
1answer
33 views
Combinatorial optimization algorithm with constraints and objective function
I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function.
.e.g
Say each ...
2
votes
1answer
54 views
This costs minimization problem, is it solvable in polynomial time?
I have the following problem: I have $c$ conflicts, named $(c_1, \ldots, c_c)$, where each conflict $c_i$ has certain size $s_i\in\mathbb{N}_0$: the number of times conflict $c_i$ has happened. Also, ...
1
vote
1answer
187 views
number of ways evaluation of expression such that value not changed [closed]
one example:
How many ways we can do possible value-preserving parenthesis the following expression in such a way that value not changed after parenthesis with one constraint that parenthesis among ...
4
votes
4answers
503 views
Enumerating all partial permutations of given length in lexicographic order
I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, ...
0
votes
0answers
16 views
Efficiently compressing and decompressing an array of combinations
I'm wondering if there exists a way to efficiently compress an array containing combinations ${n}\choose{k}$, so that it can be easily decompressed minimizing the data read from that array. An example ...
1
vote
1answer
34 views
What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$?
I am currently studying the textbook Artificial Intelligence: A Modern Approach, 4th Edition, by Russell and Norvig. Chapter 3 Solving Problems by Searching says the following:
Another type of grid ...
1
vote
0answers
9 views
Creating neighbours of solutions to binary knapsack instances
I am currently trying to implement a Tabu Search algorithm for the binary knapsack problem. Part of my goal is to have a variety of different configurations of attributes used and stopping conditions.
...
0
votes
1answer
25 views
Find sets of weighted objects to maximize number of sets with weight >= X
I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
