Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

119 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 ...