Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
1
vote
0answers
76 views

Tree Optimization, Combinatorics, algorithm [closed]

My Partners and me, we are trying to optimize frequency process... I used Java to show our Problem, but the question is about algorithm NOT about Java implementation. Although implementations in java ...
2
votes
0answers
27 views

Linear order minimizing weighted distance from special element

Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
1
vote
0answers
68 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
1
vote
2answers
70 views

Maximal cliques in a multipartite graph - efficient?

I am looking at a combinatorial optimisation problem where I have N classes and k objects of each class. Now I am looking for the optimal subset such that each of the N classes is represented ...
0
votes
0answers
59 views

Minimum Ratio Spanning Tree

Problem statement: Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{...
5
votes
0answers
65 views

Number of strings at given edit distance

I would like to know the number of strings at edit distance $n$ of a string $s$. I guess this is textbook knowledge... but I cannot find the textbook in question. More formally, I have an alphabet $\...
0
votes
1answer
57 views

How many possible ways to go right and up in an array

Let's say we have a 2D matrix, and we begin at $(0, 0)$. We must travel $m$ steps to the right and $n$ steps up, in any order. Each step moves the position right or up by $1$. For example if $n = 5$...
0
votes
1answer
88 views

Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint

I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative ...
6
votes
0answers
120 views

Algorithms to generate random nowhere-neat rectangulation?

I want to generate random rectangular partition of a given $m*n$ rectangle under the constraint that it must be nowhere-neat partition. Nowhere-neat partition means that a dissection of a rectangle ...
1
vote
1answer
135 views

How to calculate combination from given n,r and rank?

Suppose that $S=\{1,2,...,n\}$ and we are given an integer $r\leq n$. An $r$-combination of $S$ is obtained by selecting $r$ distinct integers out of the $n$. We order all $r$-combinations for a ...
1
vote
1answer
12 views

Software metric for data growth

I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements. Is there a ...
0
votes
0answers
27 views

Handling $AND$ and $OR$ cases in MILP?

Suppose I want to have an integer program for handling the cases $x_1>1\wedge x_2>1\wedge x_3>1\wedge\dots\wedge x_n>1\iff\delta=1$ $x_1>1\vee x_2>1\vee x_3>1\vee\dots\vee x_n&...
2
votes
1answer
63 views

Maximal size of a set of ordered words such that no pair of letters occurs twice

Consider an alphabet $\Sigma=\{1,\dots,n\}$. An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1<w_2<\dots<w_k$. In other words, an ordered word is a strictly increasing ...
0
votes
1answer
44 views

When do we use parallel algorithms for enumerating combinations?

I know that combination is used in many areas. But do we really need parallel version of algorithms for that? If so, where do they used? Here is a famous example of parallel algorithms, Adaptive and ...
2
votes
1answer
127 views

Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]

What would it be a recursive algorithm to get permutations for any list of n elements that might contain or not repeated elements? For the following 3-element list ...
0
votes
1answer
43 views

invariant of bin packing

We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
1
vote
1answer
93 views

Counting models satisfying a boolean formula

I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–...
9
votes
2answers
185 views

Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example, ...
0
votes
1answer
126 views

Number of possible min heaps

The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is -------------- According to me, the answer should be 48. The first element 1 is fixed as root. The ...
1
vote
1answer
31 views

Minimum number of tree operations to normalize a labeled tree

Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many ...
3
votes
0answers
82 views

Adjacent Gray code

Gray code is permutation of $\{0,1,2,\dots,2^n-1\}$ such that each of consecutive number is differs only one bit in binary representation. Example for $n = 3$ $000\\ 001\\ 011\\ 010\\ 110\\ 111\\ ...
3
votes
1answer
66 views

Sampling numbers from a weighted set that sum to constant value

So I have a multi-set of positive integers $S = \{n_1, n_2, \dots\}$ with associated weights $W = \{w_1, w_2, \dots\}$. I want to sample some numbers, without replacement, from $S$ according to ...
2
votes
3answers
411 views

Efficient n-choose-k random sampling

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)? I have read this question but it asks for generations of all combinations, not ...
1
vote
1answer
72 views

Placing items into compatible bucket types to find an optimal total value

Suppose we have a list of buckets, each with a unique type and a maximum capaciy. We also have a list of items, each with a value and a list of compatible bucket types. An item is compatible with a ...
2
votes
1answer
37 views

Generate a random combination in O(k) time and space?

How to generate a random combination of $k$ numbers from $n$ choices in $O(k)$ time and space, if we can generate a random number between 1 and $O(n)$ in $O(1)$ time? I know only 3 algorithms: with $...
0
votes
1answer
201 views

What is the fastest algorithm of generating all possible permutations (within a given set of constraints) of a multidimensional array?

There is D-dimensional array A. The number D and the size Sd of every dimension d=1..D is input from keyboard. There is also 1-dimensional array E of size N. It consists of unique integer numbers 0..N-...
2
votes
1answer
52 views

Subset on boolean cube with largest sum of biases

On the boolean cube $\mathcal{B}=\{0,1\}^n$, we assign each vertex a value by $p:\mathcal{B}\rightarrow[0,1]$. Let $$\tilde{p}_i=\sum_{x\in\mathcal{B}}(-1)^{x_i}p(x).$$ What is the value of $\max_p\...
8
votes
1answer
74 views

Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

As an example, here are all possible trees for the case $k=3$: On each node written is its arity (= the number of children). While this should be solvable by dynamic programming, I think there was a ...
1
vote
1answer
18 views

Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
2
votes
1answer
62 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
57 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
48 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 ...
3
votes
1answer
60 views

Generation of all k-combinations of a set in max-differing 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
121 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
91 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 ...
3
votes
3answers
552 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
19 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
40 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
258 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
34 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
137 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
48 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
74 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). ...
2
votes
1answer
67 views

how many boolean functions exist that satisfy the condition

How many boolean functions exist that satisfy the following condition? $$\neg f(x_1,x_2,x_3,....,x_n) = f(\neg x_1, \neg x_2,...,\neg x_n)$$
1
vote
1answer
41 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
473 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
147 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
205 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
168 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
1answer
45 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 ...

1 2 3 4 5 11