Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
2
votes
1answer
32 views
Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?
For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one.
...
1
vote
0answers
39 views
Find a partition of multiset of binomial coefficients with constriants
Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $
0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of ...
0
votes
0answers
33 views
O(1) algorithm to get approximate number that is larger as a binomial coefficient
Ideally I need a to calculate the binomial coefficient ${p \choose n}$. But since the fastest algorithm to do this is an $\mathcal{O}(n)$ algorithm I would look to do something different. I don't ...
0
votes
1answer
24 views
Generation of all combinations of a set in max-differing/random order
I'm looking for an algorithm that generates all k-combinations of a set, such that each successive combination generated differs as much as possible (or in practice, a lot) from all previous ...
0
votes
0answers
18 views
Counting chords intersections in a circle
The problem is:
Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point,
that point counts as $\binom{n}{2}$ ...
1
vote
1answer
60 views
Given a bitstring generate all bitstring with n flipped bits
For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and ...
4
votes
3answers
235 views
Hard connected instances for Weisfeiler-Lehman test of isomorphism
There are instances when WL algorithm fails. For example graphs G1 and G2 below have the same coloring after WL-1 algorithm.
However, one of these graphs is disconnected. So what are the instances ...
1
vote
0answers
14 views
Relation between deficiency and color class parity of graphs
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
35 views
invite 12 person from 24 that we have 6 men and 6 womens [closed]
i had a question and its
"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite ...
2
votes
1answer
29 views
Variant of interval scheduling (multiple machines with given availability)
I am looking for an algorithm to solve the following variant of interval scheduling : schedule some tasks on multiple machines, which are only available during a given interval of time. Two tasks ...
1
vote
1answer
27 views
Linear ordering of all subsets of size k
I was wondering if there is an obvious way to 'name' the ${n \choose k}$ subsets of size $k$ of the integers from $1$ to $n$. So I am looking for a bijection from the subsets of $\{1,\ldots, n\}$ into ...
2
votes
1answer
35 views
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
0
votes
1answer
38 views
Sum of zero nim sum series
The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
2
votes
0answers
58 views
Balls in Bins with Pairwise Distance
Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
1answer
34 views
Number of ways to choose same number of elements from two different sets
Given two sets of elements S and R, with p elements and q elements respectively. 1 <= p,q <= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum_{i=0}^{\min(p,...
0
votes
1answer
62 views
Hiring problem from CLRS
Hiring problem is discussed in section 5.1 and 5.2 of the CLRS and I'm referring this for exercise solutions.
However, for Exercise question 5.2-2 my solution deviates from the one given in the ...
4
votes
2answers
135 views
A problem on constrained combinatorics
Not sure if this is a proper place, but I really don't know where else to ask. I'm craving for an algorithm generating certain sequences of numbers (the problem comes from physics).
I'm looking for ...
1
vote
1answer
56 views
Algorithm to organize a tournament where the team componentes change each round
So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
4
votes
3answers
88 views
Sum of unique elements in all sub-arrays of an array
Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.
Subarrays:
...
0
votes
0answers
21 views
Maximizing benefits of performed tasks by purchasing less reusable devices
Suppose to accomplish a task $t_i$ from a finite task set $T=\{t_1, \ldots, t_n\}$, we need a set of reusable devices $D(t_i) = \{d_1, \ldots, d_m \}$ from a finite device set ${\cal D}$ such that
1) ...
0
votes
1answer
42 views
Different iterations of regular expressions
A four-part question dealing with formal languages and regular expressions:
How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
How ...
2
votes
1answer
36 views
No. of subsets whose element multiply to give a square number
I have been given an array whose elements lie between [1,70] and the size of array [1,10^5].
I have to find the total number of subsets whose all elements multiply to give a perfect square number.
...
2
votes
0answers
8 views
Maximal number of rounds we can do distributing 64 diners on 8 groups in different ways if they can't meet each other more than once?
N=64 hungry diners come to a buffet.
We sit them at 8 different (s=8 people at each table) tables so that they get to know each other while they eat.
After a while we distribute them over the tables ...
2
votes
1answer
28 views
Count number of the ways to fill a N-lengthed binary string
From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
2
votes
0answers
52 views
Maximum number of non-overlapping rectangles where each contains a minimum number of points
Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
15
votes
8answers
2k views
Cardinality of the set of algorithms
Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms ...
3
votes
1answer
45 views
How to generate a binary string so to minimize weighted bitwise distance?
I've got an array of weights, for example
[1, 0, 3, 5]
The distance between two strings is defined as a sum of weights for different bits, like this:
...
3
votes
1answer
49 views
Primary/Secondary On Call Rotations
I'm trying to setup a primary and secondary on call schedule with 6 people.
I'm trying to schedule people to be on call, so that they will be paired with everyone and they have the longest "break" ...
2
votes
0answers
27 views
Inexact cover, or cover with gaps
Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem.
In the Knuth's research papaer, linked above it is shown how Polymino problem (that is ...
4
votes
1answer
49 views
Integer Problem Solving with two boolean selection variables
I am trying to solve a two dimensional combinatorial problem.
Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible ...
4
votes
1answer
582 views
Making 5-tuples out of their respective 4-tuples
Let's take integer numbers from [1..36]. We can generate 376992 different (order is not important) five-number-combinations like (1,3,5,7,12), etc. Such five-number-combinations always have five ...
0
votes
2answers
385 views
Given n numbers How to find out a set of numbers whose sum equal to a certain given number
I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s.
...
1
vote
1answer
17 views
Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k
Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40)
How would I find the maximum possible size of S, where S is a ...
2
votes
1answer
76 views
Which algorithm can calculate an optimal allocation of students to projects?
I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
2
votes
1answer
22 views
How many different strongly connected graphs can be created given n nodes?
Given some fixed number of nodes $n$, which we will number 1 to $n$ in order to tell them apart, how many different strongly connected graphs can be created? Multiple edges with the same starting and ...
4
votes
2answers
91 views
How to model and solve this problem?
I have a matrix $P \in M_n(\mathbb N)$, where
$$ P =
\begin{bmatrix}
0 & P_{12} & \ldots & P_{1n}\\
P_{21} & 0 & \ldots & P_{2n}\\
\vdots & \vdots & \ddots &...
2
votes
1answer
25 views
How to find splitting point in [0,1] to maximize sum of sign function?
Given two $n$-number arrays $a_1, a_2, \ldots,a_n \in [0,1] $ and $b_1, b_2, \ldots,b_n \in [0,1] $. We would like to find the real number $x^{*} \in (0,1)$ s.t:
$x^{*} =\arg\max_{x} \sum_{i=1}^n \...
0
votes
0answers
19 views
How many sets of LR(0) items exist in this grammar? (question from the dragon book)
The grammar:
\begin{align}
S&\rightarrow A_ib_i &\text{for }1\le i\le n\\
A_i&\rightarrow a_jA_i\mid a_j &\text{for }1\le i,j\le n\text{ and } i\neq j
\end{align}
The answer is $2^n +...
2
votes
1answer
48 views
Centre, diameter, and radius of graph
I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here.
Ques1. ...
0
votes
2answers
30 views
Infer a list of numbers from observations of subranges
There's a list of (unknown) integers, in [0...20]. They are generated from a uniform distribution via a RNG.
The input is observations of the form:
in a subrange <...
3
votes
1answer
43 views
Minimum number of moves required to transfer items from source bins to target bins?
I have a set of source bins, each with some number of items, and a set of target bins. I want to move all of the items from the source bins to the target bins, using the minimum number of moves. ...
1
vote
2answers
66 views
Computational complexity of Bell numbers
I've been recently dealing with a problem which, when worst case is considered, results in exploration of $B_{n}$ options, where $B_{n}$ is th $n^{th}$ Bell number. I am trying to rigorously prove, ...
2
votes
0answers
73 views
Grouping elements optimally other than NP-hard approach
Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and ...
2
votes
1answer
78 views
Subset sum into a consecutive range vs. standard subset sum
The following problems live in integer domain.
I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq ...
0
votes
0answers
66 views
How to correctly count subsets using dynamic programming
I'm trying to solve this problem: UVa 1734 - Numbered Cards.
You have $N$ cards and each has an unique number between $1$ and $N$ written on it. In how many ways can you select a non-empty subset ...
2
votes
1answer
46 views
Find the maximizing row-column matches in a matrix
I have a set of R x C matrices similar to the following (can be much longer):
C1 C2 C3 C4 C5 C6
R1 0.32 0.81 NA NA NA NA
R2 0.90 -0.44 0.95 ...
0
votes
0answers
35 views
Optimise 1D cutting stock problem - maximum waste that can be removed with n cuts
The problem statement can be made as follows. There is a 1D length of raw material that contains "net" and "waste" intervals. Using 2n cuts, sections of material can be removed so that less waste has ...
1
vote
1answer
69 views
Efficient alternatives to inclusion-exclusion
Say you've got a number of sets $S_1,...,S_n$ given and are supposed to calculate $\,\,\displaystyle\big|\bigcup_{i=1}^n S_i\big|$ .
The basic approach probably would be to use the classic inclusion-...
1
vote
1answer
52 views
Number of words in $\{pi,po\}^*$ of length at most 9
I have a language $L^*$ for $L = \{pi,po\}$ (I think pi counts as one letter and po also as one letter otherwise a max length of 9 is not possible).
The question is how many words I can make with $L^*...
1
vote
1answer
34 views
Group tuples to satisfy constraints
This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced ...
