Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions related to combinatorics and discrete mathematical structures

0
votes
1answer
29 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
51 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
119 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 ...
0
votes
0answers
36 views

A combinatorial optimization problem with restrictions

Assume $A$ is an $n \times m $ matrix. How can we select $n$ elements, one element from each row, such that their sum is minimized, subject to the following constraint: we can choose the elements from ...
1
vote
1answer
46 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
81 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
19 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
41 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
33 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
26 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
47 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
41 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
40 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" ...
1
vote
0answers
23 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
37 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
576 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
242 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
63 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
22 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
33 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
26 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
39 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
54 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
71 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
65 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
61 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
45 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
26 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
61 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 ...
0
votes
1answer
48 views

sub-optimal but fast partition generation

I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. ...
2
votes
2answers
47 views

Why is the number of digits (bits) in the binary representation of a positive integer $n$ is the integral part of $1 + \log_2 n$?

I've stumbled on this definition on Wikipedia, and I can't figure out why. I could probably start the demonstration by saying that, with $n$ bits, you can create $2^n$ possible different numbers, so $...
0
votes
0answers
26 views

Multi-trip travel salesman problem

Given a graph $G$, I want to find a shortest tour visiting each vertex. Different to the classical formulation of TSP, my tour needs to be divided into several subtours, each upper-bounded by a ...
1
vote
1answer
33 views

Minimum capacity cut reduction from digraph with two edge weight sets

Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{...
0
votes
1answer
62 views

Knapsack problem with diminishing prices

I wonder if the knapsack problem with diminishing prices is already studied? The problem is similar to the regular knapsack problem, except the price of each item is a decreasing function of the total ...
3
votes
1answer
38 views

Finding the maximum of a random forest

If we have some collection of decision trees with single-variable splits and a constant value at each leaf node, the average over all trees gives some function from $\mathbb{R}^n \to \mathbb{R}$. Is ...
2
votes
0answers
35 views

Constrained selection of a random sample from a set of items with multiple attributes

Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA. Attribute ai can take on Vi different possible (discrete) values, distributed across the population ...
2
votes
1answer
36 views

Fast computation of k-fibonacci numbers

Let's define the sequence of $k$-Fibonacci numbers as $$ F_i = 2^i, ~~ 0 \leq i \leq k-1 $$ $$ F_i = F_{i-1} + \dots + F_{i-k}, ~~ i \geq k $$ I have a problem which requires to compute $n$-th $k$-...
1
vote
1answer
28 views

Counting restricted partitions

Given positive intgers $N$ and $S$ i need to count in how many ways $N$ can be decomposed as sum of $S$ positive integers not greater than $\frac{N}{2}$: $$ N = x_1 + \dots + x_S, ~~~~ 0 \leq x_i \leq ...
0
votes
0answers
82 views

Permutation of multiple groups of different sizes

While working on my research for my master thesis I have stumbled upon the following problem: Given $N$ groups of different sizes, create all the possible combinations $p$ such that: $p = \{e_{0,j_0}...
0
votes
0answers
20 views

Assign team members to groups to maximize outcome

Team A has 2 Spots Team B has 1 Spot Player 1: 10 Units when on team A, Can't work on team B Player 2: 8 Units when on team A, Can't work on team B Player 3: 9 Units when on team A, 2 Units when ...
1
vote
1answer
41 views

Portfolio allocation with a few twists

A similar question has been asked here, but this one is more complicated and has more constraints. I'm trying to find an algorithm to solve the following (real-life) problem: A customer has $M$ ...
1
vote
1answer
21 views

Find the best set of triples of objects, using each object at max one time

I stumbled upon an interesting problem and I'm stuck with it, since I can't find parallels to other problems or algorithms to solve it. We have a set of objects $O = \{a,b,c,...,z\}$, objects can ...