Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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 ...
Pedro Soriano Ruiz's user avatar
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 ...
m00151's user avatar
  • 13
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^*...
Diceble's user avatar
  • 113
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 ...
Bernd Strehl's user avatar
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: ...
jminuscula's user avatar
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}+...
Mr. Sigma.'s user avatar
  • 1,293
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 \...
jbilander's user avatar
  • 113
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 ...
Adam Kurkiewicz's user avatar
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 ...
tomoka kazuki's user avatar
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 ...
Andrei's user avatar
  • 362
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 ...
Charlie Parker's user avatar
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 ...
Zephyr's user avatar
  • 993
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 ...
Marlon Patrick's user avatar
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. ...
JohnL_10's user avatar
  • 113
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) =...
gradstudent's user avatar
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 ...
Li Wang's user avatar
  • 33
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 ...
PPenguin's user avatar
  • 327
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 ...
user54272's user avatar
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 ...
omnibus's user avatar
  • 13
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 ...
Nimrod's user avatar
  • 19
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. ...
user128409235's user avatar
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 ...
Lars Quinnn's user avatar
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 ...
Kolophonius's user avatar
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$.
JonyWalk's user avatar
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 ...
Learner's user avatar
  • 131
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 ...
BurninateSE's user avatar
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 ...
Gary D.'s user avatar
  • 313
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(...
Daniel Geisler's user avatar
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 ...
kaka's user avatar
  • 155
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 ...
Nau's user avatar
  • 111
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). ...
sbh's user avatar
  • 51
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 ...
cgss's user avatar
  • 111
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 ...
Jo Ma's user avatar
  • 15
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: ...
adib's user avatar
  • 111
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 ...
akhil's user avatar
  • 11
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....
Leonid Dworzanski's user avatar
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 ...
Mohamed Challouf's user avatar
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$ ...
vidyarthi's user avatar
  • 175
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 ...
Bob Lucassen's user avatar
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$. ...
Daniel Schwegler's user avatar
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 ...
night-crawler's user avatar
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 ...
Quantum Guy 123's user avatar
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 ...
AmirHosein Adavoudi's user avatar
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 ...
77H3jjuu's user avatar
  • 123
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 ...
joeren1020's user avatar
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)=\...
MC From Scratch's user avatar
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 ...
rhodeo's user avatar
  • 111
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 ...
Lance's user avatar
  • 2,213
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....
Ali Gholami's user avatar
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 ...
Harsha's user avatar
  • 11

1
9 10
11
12 13
16