Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
755
questions
1
vote
1
answer
453
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 ...
1
vote
1
answer
119
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 ...
1
vote
1
answer
75
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
1
answer
31
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 ...
1
vote
1
answer
151
views
Shift Organization algorithms (Constraint Programming + Marriage problem)
I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition:
Daily shifts must be covered by workers, who are divided in three groups:
...
1
vote
1
answer
65
views
Obtaining a recurrence from a rational generating function
Looking at some Generating functions of a series, I have conjectured -
If $G(x) \ =\ \frac{1}{1-x^{t_1}-x^{t_2}-...-x^{t_n}}$, then the recurrence equation of the the series is -
$a_n = a_{n-t_1}+...
1
vote
1
answer
940
views
Reverse cartesian product matching all given rows
I´m looking for an efficient algorithm that will find reverse cartesian products.
Mathematically, given $S \subseteq T^n$, I want to express $S$ as a union of sets $A_{i,1} \times A_{i,2} \times \...
1
vote
2
answers
168
views
Non-trivial bin-packing instance with 5 objects
Bin packing problem is a problem, where one has to find the minimum number of bins of size $v$ required to store $n$ objects of sizes $s_1, \ldots, s_n$. Object sizes are never greater than $v$.
For ...
1
vote
3
answers
944
views
Is there a way to make chess an absolutely fair game? [closed]
Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also appears to be a fair game ...
1
vote
1
answer
49
views
Checking large number of configurations with multiple constraints
I have a very large number of constraints such as:
$ A1 \land B1 \land C1 \land D1 \land E1 \land F1$
$ A2 \land B2 \land C2 \land D2 \land E2 \land F2$
$ A3 \land B3 \land C3 \land D3 \land E3 \land ...
1
vote
1
answer
387
views
How does one generate all the terms of a multivariate polynomial algorithmically?
I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a ...
1
vote
1
answer
2k
views
Number of rooted labelled trees
According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2
If the tree is rooted then in each tree we can ...
1
vote
1
answer
434
views
Algorithm to find the closest possible value among several combinations
I have the following problem and would like an orientation on which algorithms I can try to adapt to solve it in the best possible way.
SCENARIO
A company has a warehouse where it stores several ...
1
vote
1
answer
78
views
How to find number of permutations of 1-N length, each [1-N] with k values
This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values.
A real-world example might include 5 different single-digit combination locks.
...
1
vote
1
answer
39
views
Two definitions of the Reed-Muller code
I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways,
1.
$RM(d,n) =...
1
vote
1
answer
122
views
Given a valid combination, how to get its index in the sequence of integer partition
This question is extended from this Algorithm to generate integer sets fulfills restrictions, in the answer I learned the formal term of this problem, and the recursive algorithm described in that ...
1
vote
1
answer
23
views
A comparison operation for lists, based on P(a > b)
Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from ...
1
vote
1
answer
74
views
Faster way of calculating how many ways can $2n$ elements be paired?
So the problem is in how many ways $2n$ elements can be paired, my approach was multiply all odd numbers less then $2n$.
$(2n-1)*(2n-3)*...*1$
but my professor claimed it can be done much faster in ...
1
vote
1
answer
591
views
Letter Combinations of a Phone Number
I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem).
Problem statement – Letter Combinations of a ...
1
vote
1
answer
103
views
Relation between Hamming distances of columns and rows
You're given a $0-1$ $n\times n$ matrix such that for every distinct columns $C_i$ and $C_j$, $d_H(C_i,C_j)\gt 2t$ for some $t$. What could be said about the Hamming distances of the rows? It it true ...
1
vote
2
answers
222
views
Shortest path in divisors graph
There is a graph with N vertices numbered from 1 to N. Edge between a and b exists if and only if a|b or b|a. If a|b then the weight of the edge is b/a. If b|a then the weight of the edge is a/b. ...
1
vote
1
answer
186
views
efficient cumulative all over combinations of boolean vector elements
Problem
Given a vector of bools of length n I wish to compute the logical and over all subsets up to length k.
By logical ...
1
vote
1
answer
55
views
Combinatorial optimization - is there a formal name for this problem?
I am looking for a formal name and an algorithmic approach to the following problem.
Given is a set of services each coming with a price:
{s1, 300}
{s2, 400}
{s3, 800}
Additionally there is a ...
1
vote
1
answer
92
views
Probability of having a log(n) length monotone subsequence in a random permutation of {1,...,n}
How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$.
I wish to upperbound it with $1/n$.
1
vote
1
answer
2k
views
Permutations in an k-sorted array
Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order.
I have a question in my Algorithms assignment which asks to prove the lower bound to ...
1
vote
1
answer
140
views
How many ways to find a sum totalling n using only certain Integers?
Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n?
Clarification: The Integers are arbitrary, positive, and may not include 1.
At first I thought it was ...
1
vote
1
answer
129
views
Partial Range Query on Inverted File with Combined Index
I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is ...
1
vote
2
answers
188
views
What are efficient ways to compute the derivatives of iterated functions?
The derivatives of iterated functions at a fixed point $z_0$ are useful in constructing a Taylors series of iterated analytic functions - in other words, the Taylors series of a dynamical system $f^t(...
1
vote
1
answer
168
views
Recurrence formula for a known sequence?
Problem: How do we can generate some mathematical close form of the following sequence, which has following 256 entries:
1 7 7 7 7 9 9 9 7 9 9 9 7 9 9 9 7 11 11 11 ...
1
vote
0
answers
35
views
How many different colors are possible to generate in the HSV Color Space using OpenCV?
I don't know if this post belongs in this site because I feel it might be a programming question, but also I feel it might be related to the way Color Spaces work, if it does't belong here I can ...
1
vote
0
answers
108
views
How many comparative sorting algorithms are there?
I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
1
vote
0
answers
37
views
Set cover variation: disjoint covers for all but one element
In the classical set cover problem, we are given the set $U$ of elements $\{1, \dots, n\}$ and a collection $C$ of some subsets such that their union is the whole set. Now, I will introduce the first ...
1
vote
1
answer
92
views
Is there an efficient algorithm for this ecommerce optimization problem?
Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:
There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
1
vote
0
answers
39
views
Grouping transactions having pre-determined sums?
I have a transaction grouping problem that I'm having trouble to devise the algorithm to solve it. Not even ChatGPT (version 3.5) can solve this correctly.
Suppose I have five transactions:
...
1
vote
0
answers
32
views
Find an assignment discarding a subset of possible assignments
We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task.
The number of possible assignments is $N!$. Let us call this set of all possible ...
1
vote
0
answers
50
views
Are there known algorithms to find a line that intersects a given set of segments?
Are there known algorithms to find a line that intersects a given set of segments?
In:
A finite set of segments.
Out:
A line that cross all these segments or explicit answer that there is no such line....
1
vote
1
answer
72
views
Exact cover matrix for project planning
I'm trying to solve the project planning problem using DLX and exact cover matrix, but I'm struggling to find the set of constraints (columns) and the set of options (rows) to achieve this. Here is a ...
1
vote
0
answers
34
views
Maximum size of a graph with given girth
I am unable to get the bound on the maximum size of a graph of order $n$ with girth $g$. Is there any literature regarding this. I know that there is an asymptotic bound on the size of a graph $G$ ...
1
vote
0
answers
41
views
Finding maximal cliques in a graph represented as a collection of complete biparti graphs
I have a graph whose edges can be very efficiently represented as a set of complete biparti graphs (that may share nodes). Is there a name for such a representation?
And secondly. I want to enumerate ...
1
vote
1
answer
39
views
Densest Sub Graph and forbidden Pairs
Given two graphs $G$ and $F$ on the same vertex set $V$. Compute a sub set $\tilde{V}\subset V$ which' sub graph of $G$ is of maximum density and does not have any pair that is connected in $F$.
...
1
vote
1
answer
160
views
Reorder columns in a 2d matrix to maximize the count of all repeated subarrays across all rows
I have a matrix (input):
--
c1
c2
c3
r1
AA
BB
CC
r2
CC
RR
BB
r3
EE
DD
FF
r4
KK
DD
EE
r5
DD
GG
KK
r6
PP
QQ
KK
Let's call each matrix cell a namespace. If two ...
1
vote
0
answers
45
views
What is the worst case time complexity of unranking n choose k combinations (combinatorial number system, combinadics)
The combinatorial number system shows that there is a bijection between the natural numbers less than $n \choose k$ and $n\choose k$ combinations. There is a greedy algorithm for unranking ...
1
vote
0
answers
114
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]
We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
1
vote
1
answer
145
views
Sorting a collection of tuples using merge rearrangements
Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements
$x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is
sorted if $x_i \leq x_{i+1}$ and $y_i \leq ...
1
vote
0
answers
27
views
Quicksort sampling
This question is in the context of quicksort. Consider that a subarray of distinct elements of size $k$ is sampled from the input array of size $n$, and then we choose a pivot from the sampled ...
1
vote
0
answers
55
views
Sum of coprime divisors
Define the following function to be the count of integers not greater than $L$ that are coprime to $n$:$$C(n,L)=\sum_{k=1 \atop {GCD(n,k)=1}}^L1$$
Then I am interested in the following sum:
$$S(x)=\...
1
vote
0
answers
208
views
Finding maximum weight closure of a graph using min-cut
I am going through the book "Network Flows" by Ahuja et al. In chapter 19.2 "MAXIMUM WEIGHT CLOSURE OF A GRAPH", I find this example of turning a vertex-weighted (positive or ...
1
vote
0
answers
30
views
How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?
I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
1
vote
0
answers
33
views
matching vector families that form a group
Is there any research/information on matching vector family sets (the U list or the V list or both) that form a group (under addition)?
You can find the definition of MV families here:
https://homes....
1
vote
0
answers
27
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 ...