Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
611
questions
2
votes
0answers
20 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
59 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
52 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
19 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 ...
-1
votes
1answer
29 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
29 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
85 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
82 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
20 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
72 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
98 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
33 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
32 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
24 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
68 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
28 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
31 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
72 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
32 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, ...
0
votes
1answer
185 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
291 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
14 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
32 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
7 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
19 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 ...
2
votes
1answer
49 views
Min weighted edge cover - is the greedy algorithm sub-optimal?
The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum ...
0
votes
0answers
31 views
On the probability of randomized testing covering all combinatorial testing interactions
I'm interested in how fuzz testing and something called combinatorial testing. Combinatorial testing attempts to forgo exhaustive testing in favor of trying to test all possible "interactions&...
0
votes
0answers
33 views
Subset selection with maximum sum and minimum variance?
So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
4
votes
2answers
138 views
Min path cover for a three-layer graph with all paths traversing all layers
Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...
0
votes
0answers
28 views
Algorithm for specific load balancing/arbitration problem
I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
1
vote
1answer
24 views
Upper bound on size of minimal binary coverage code
Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that ...
0
votes
1answer
39 views
Bottleneck TSP with repeated nodes
I am aware that the traveling salesman problem (TSP) and the bottleneck TSP problem is NP-hard for complete directed graphs. I am also aware that regular TSP that allows a path with repeating is also ...
1
vote
2answers
44 views
Floating-point oblivious way to compute multiset numbers
I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
4
votes
2answers
274 views
Given a row sum vector and a column sum vector, determine if they can form a boolean matrix
For example, for a boolean matrix of size $3x4$, the column sum vector $C = (3, 3, 0, 0)$ and the row sum vector $R = (2, 2, 2)$ form a match because I can construct the boolean matrix:
$$
\begin{...
3
votes
0answers
91 views
Speeding up the Rummikub algorithm - explanation required
Regarding this question: Rummikub algorithm.
I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
1
vote
1answer
14 views
Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
0
votes
1answer
56 views
Balanced sub-sequence
Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of ...
3
votes
1answer
54 views
Topological sort where some nodes can't come in between two other nodes
I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node ...
2
votes
0answers
42 views
What is the largest sum that can be constructed with the given recipes?
There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$.
There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to ...
2
votes
0answers
23 views
How to linearly combine loss functions to preserve optimal substructure property?
I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
3
votes
1answer
51 views
Combinatorial Problem similar in nature to a special version of max weighted matching problem
I have a problem and want to know if there is any combinatorial optimization that is similar in nature to this problem or how to solve this special version of the max weight matching problem.
I have a ...
0
votes
1answer
33 views
Approximate bin-packing?
Let $X_1,...X_n$ denote some bins, and $w_1,...w_m$ some positive real numbers, where $m \in \mathbb{N}$, and the order matters, so e.g. we can't switch the position of $w_n$ and $w_1$. The goal is to ...
2
votes
1answer
16 views
Maximum Chromatic number of Cayley Graphs with large degree
It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}...
0
votes
0answers
36 views
finding the combinatorial solutions of series and parallel nodes
I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, ...
0
votes
1answer
54 views
Combinations of set unions
I have a set $S = \{0,1,2,3,4,5,6,7,8,9\}$. $S_i \subset S$ for $i = {1,2,3,4,5}$. Any three $S_i$ has the same union, that is $S_1
\cup S_2\cup S_3 = S_1\cup S_2\cup S_4 = ...=S_3\cup S_4\cup S_5 = A$...
1
vote
0answers
56 views
Number of words of length n for special language
Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties:
if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
3
votes
1answer
66 views
Counting circuits with constraints
Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).
In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be ...
