Questions tagged [combinatorics]
Questions related to combinatorics and discrete mathematical structures
119
questions with no upvoted or accepted answers
1
vote
0answers
32 views
What do you call a greedy algorithm that solves a combinatorial problem by optimizing the best k>1 choices altogether?
Suppose you have a problem which goal is to find the permutation of some set $S$ given in input that minimizes an objective function $f$ (for example the Traveling Salesman problem).
A trivial ...
1
vote
0answers
21 views
What are all linear extensions of the product order of $\{1, \dots, M\} \times \{1, \dots, N\}$?
Note: I have read somewhere that finding all linear extensions of a partial order is in general a #P-complete problem (which apparently means difficult, and thus no closed form expression), but just ...
1
vote
0answers
25 views
Find an algorithm to fully consume items with criteria and produce minimal result
So here are the prerequisites:
There are items to be consumed. Consider an item is just an object with a bunch of properties (e.g. size, weight), and there are tens or hundreds of properties.
Items ...
1
vote
0answers
25 views
Counting number of binary trees with given node values and root
I came across following problem:
Find number of binary trees possible with 2 as roots. Nodes={1,2,3,4,5}
There was no solution given. I knew number of binary trees for given preorder is given by ...
1
vote
0answers
21 views
How to compute the general term formula for the number of full binary tree heaps that can be formed with distinct elements?
The number of possible heaps that are full binary trees of height $h$ and can be formed with ($n = 2^h - 1$) distinct elements can be computed by recursion:
$$ a_h = {2^h - 2 \choose 2^{h - 1} - 1} a_{...
1
vote
0answers
47 views
Is there an algorithm to generate all permutations of a multiset through swaps?
I am currently working on a project where I have to perform a computation over all possible permutations of a multiset $S$. In my setting, each multiset is a list of small positive integers such as $S ...
1
vote
0answers
45 views
coloring of an interval graph with constraints
Given an interval graph that represents a set of tasks, in a given period of time, to be assigned to a set of employees, the objective is to find a minimum coloring of this graph such that the total ...
1
vote
0answers
70 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
0answers
66 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 ...
1
vote
0answers
23 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 ...
1
vote
0answers
118 views
Hanoi Tower Variation: Place Maximum Number of Balls on $N$ Pegs
Problem Statement. There are many interesting variations on the Tower of Hanoi problem. This version consists of $N$ pegs and one ball containing each number from $1, 2, 3, \dots$ Whenever the sum of ...
1
vote
0answers
54 views
Hat Distribution Problem
I had a question for my paper last week and i tried solving but failed.
Given n people, any two are either friends or enemies, and friendship and enmity are mutual. I want to distribute hats to them, ...
1
vote
0answers
25 views
Set cover such that every vertex appears in at most k sets
Given a set $\{x_1,x_2,\dots, x_n\}$ and sets $\mathcal(F)=\{f_1,f_2,\dots, f_m\}$.
Is there any hardness result or approximation algorithm to find a set cover with this extra condition.
For every ...
1
vote
0answers
675 views
Efficient Algorithm for Combinations With Replacement (n choose k)
I am looking for the canonical implementation of the "k-combinations with repetition" algorithm.
Simple Example:
Input: "ABC" (choose 2)
['AA', 'AB', 'AC', 'BB', 'BC', 'CC']
I have a ...
1
vote
0answers
33 views
Commonly-used formal definition of graphs with 'connections'?
Sometime you want to model some data from the real world using a graph, but such that edges don't just connect to a vertex; rather, they connect to some aspect of that vertex - some connection if you ...
1
vote
1answer
79 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
0answers
87 views
Bin Packing across multiple iterations
I am working with an iterative application in a distributed setup. The application has n processes (P1, P2,...Pn) and m iterations. Each process may or may not perform any computation in a given ...
1
vote
0answers
18 views
Relationship between lexicographic index of size k (tuple) with that of size(k-1) tuple
Given a non-negative integer $n$ such that $X = \{1,2, \dots, n\}$, a combination of k-tuple and its associated index $pos_k$.
How to compute the associated lexicographic index for any subset of the ...
1
vote
0answers
97 views
Algorithm better than Greedy for Dominating set
I just want to know that whether there is an algorithm better than the Greedy Algorithm for Dominating set. I know that Greedy gives $O(\log(\Delta))-approx$ and we can not do something better than $...
1
vote
0answers
144 views
Counting the number of non-overlapping squares and cubes in a string
Given a string S of length n that contains exactly $\lceil\frac{n}{3}\rceil$
b's and $\lceil\frac{2n}{3}\rceil$ a's:
Suppose the charge is 2 for each non-overlapping occurrence of aaa, and 1 for each ...
1
vote
0answers
180 views
How to encode each possible b-tree of a sequence of n numbers?
Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
1
vote
0answers
142 views
Best combination of elements with defined constraints
My goal is to find the best combination, or good approximation, of weighted elements with different constraints / relations, for example:
B can only be there after A
B have to be there after A
B have ...
1
vote
0answers
132 views
Multidimensional 0-1 knapsack as the solution to 0-1 goal programming problem
I am trying to find the algorithm for the 0-1 goal programming problem. Actually I don't have any recent references for explicit algorithms, all the recent articles are about the modelling and not ...
1
vote
0answers
198 views
Maximum flow problem with non-zero lower bound
Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write
$$\begin{align*}
\delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\
\delta ^{-}(X) &= \delta ^{+}(V -...
1
vote
0answers
26 views
State of art quadratic knacksack algorithms
What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.
1
vote
0answers
50 views
Assigning packages to different points by minimizing distance: is this a known problem?
Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of ...
1
vote
1answer
518 views
What is the optimal way to find unique combinations of N sets of integers
This is a simplification of a real world problem and only a small piece at that.
Example sets are
...
0
votes
0answers
68 views
$O(n)$ algorithm to find a sequence of 3 or n tennis players with ratings in decreasing/increasing order
This problem is a follow up from this.
At a certain (unrealistic) event, we have infinitely many tennis players lined up who are conveniently numbered $(P_1,P_2, \cdots)$. Each player has a certain ...
0
votes
0answers
30 views
How many different values can a shared variable take in concurrent computing?
Question:
Is there a way to find out number of different values that a shared variable can take in concurrent computing, in general, without listing all the possibilities and then counting the ones ...
0
votes
0answers
14 views
Efficiently compressing and decompressing an array of combinations
I'm wondering if there exists a way to efficiently compress an array containing combinations ${n}\choose{k}$, so that it can be easily decompressed minimizing the data read from that array. An example ...
0
votes
1answer
19 views
Find sets of weighted objects to maximize number of sets with weight >= X
I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
0
votes
0answers
31 views
On the probability of randomized testing covering all combinatorial testing interactions
I'm interested in how fuzz testing and something called combinatorial testing. Combinatorial testing attempts to forgo exhaustive testing in favor of trying to test all possible "interactions&...
0
votes
0answers
30 views
Subset selection with maximum sum and minimum variance?
So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
0
votes
0answers
28 views
Algorithm for specific load balancing/arbitration problem
I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
0
votes
0answers
36 views
finding the combinatorial solutions of series and parallel nodes
I have n nodes, and I want to find the (non duplicate) number of possible ways in which these nodes can be combined in series and parallel, and also enumerate all the solutions. For example, for n=3, ...
0
votes
0answers
22 views
Analyzing a counting triangles streaming algorithm which uses $\ell_0$ sampling
I'm trying to analyze the following streaming algorithm for counting triangles (see below). It supposedly works also for dynamic graphs (i.e. "turnstile model", where edge deletions are ...
0
votes
0answers
18 views
Is the number of sub-boolean algebras of a set with size of n equal to Bell(n)?
In boolean algebra (P(S),+,.,ā) we must have S as 1 and {} as 0 in every possible sub-boolean algebra to hold id elements.
We must have S-x for every subset xāS to hold complements.
It seems like ...
0
votes
1answer
94 views
“Knapsack problem” with repetition, “lesser or equal” constraint, and recording all valid combinations
In a game I am developing I came across an interesting problem, that seems like it could be solved using some modified variant of the knapsack problem, but it's a bit over my head.
Let $x_i$, $ 1\leq ...
0
votes
0answers
18 views
How to consider combinatorial optimization problem with multiple objectives?
I am considering a combinatorial optimization problem with two objectives. The two objectives have a trade-off between each other which means if I minimized the first objective alone it gives the ...
0
votes
0answers
21 views
About number of NFSTs
Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.
0
votes
0answers
14 views
How to get started with multi-level pairwise combinations
Let's say we have 4 ranks: 1-4
Every rank has a set of unique nodes, each pair of same-rank nodes can be combined to create a node of a rank 1 level higher, in any number of combinations:
...
0
votes
0answers
44 views
Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph
This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
0
votes
0answers
24 views
Powells Method for 2 Variables?
I've been studying this YouTube video on Powells method and it looks like when we have a single variable we start at the upper and lower bounds of the variable and then we keep dividing the search ...
0
votes
0answers
32 views
Fractional knapsack with setup costs
I am considering a variant of the classical fractional knapsack problem, it's written in the following integer programming form
Here $v_i, c_i, w_i, b$ are all positive. $c_i$ can be interpreted as ...
0
votes
2answers
52 views
What is a good method for modelling combinatorial tree (sport competition results)?
Probably newbie question here, please point me out to relevant theories/tutorials if needed :
let say I want to evaluate the probabilities of the final rankings for a sport competition
the ...
0
votes
0answers
79 views
Sliding Puzzle w/ multiple solutions
I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles ...
0
votes
0answers
16 views
Maximizing a sequence of items under order and pairwise restriction
Suppose I have a number of items $\{A ... Z$} which are ordered accordingly. Each item has an associated weight, for example $W_A$. Between all items, there's a criterion $c$ which determines whether ...
0
votes
0answers
34 views
Schedule a Seminar in Minimum Time
There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
0
votes
0answers
45 views
Which is the most similar NP classic problem, if any exists, to this one?
Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the ...
0
votes
0answers
330 views
Help with an algorithm task
I've been given a task that I had issue solving.
Problem statement:
John likes jumping so he is about to build a new jumping terrain. The
terrain consists of N blocks, and in each block he can ...
