Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

84 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
39
votes
0answers
1k views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
9
votes
0answers
183 views

How to solve the loan graph problem

The problem A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
7
votes
0answers
155 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
6
votes
0answers
112 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 ...
5
votes
0answers
51 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 $\...
5
votes
0answers
50 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u \...
5
votes
0answers
174 views

Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
4
votes
0answers
33 views

Karger's min-cut (contraction): Combinatorial argument for success probability?

The contraction algorithm for min-cut is: pick an edge $(u,v)$ uniformly at random, and "contract" it by merging $u$ and $v$ into a single vertex, deleting self-loops. Continue until two vertices ...
4
votes
0answers
107 views

Generating all directed multigraphs

I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow ...
4
votes
0answers
59 views

Adversarial bin packing

An adversary gives you a set of items whose total size is $x$ (he gets to choose how $x$ is distributed. e.g. there may be $k-1$ items of size $\frac{x}{k}$ and 2 items of size $\frac{x}{2k}$). The ...
3
votes
0answers
79 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
0answers
43 views

How to determine the maximum valued play in Rummikub?

This question is meant as a follow-up this question and my answer here. The question asked multiple questions about algorithms for playing Rummikub and my answer provided an algorithm that, given a ...
3
votes
0answers
119 views

How to find an optimal sequence of matching

Given a graph $G(V.E,w)$ Here $w: E \mapsto R$. We need to find optimal set of matchings(set of edges that have no common vertices) and $t_i$'s such that after all these matchings, it results in $\...
3
votes
0answers
36 views

Scheduling problem of average sums with condition

Take a multiset $S=\{s_1,\ldots,s_n\} \subset \mathbb{N}$ and some $k \in \mathbb{N}$. Take $T$ to be the set of all sequences of the form $s_{\pi(1)},\ldots,s_{\pi(i)}$, such that $\sum_{j=1}^{i-1} ...
3
votes
0answers
74 views

Hardness of approximation for Disjoint Group Steiner Tree

Does anyone know any constant factor approximation hardness results on Group Steiner Tree when the groups partition the terminals, i.e. every terminal belongs to exactly one group? The (intuitive) ...
3
votes
0answers
258 views

permutations sampling by probability matrix

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = \...
3
votes
0answers
409 views

computing permanent of a 0-1 rectangular matrix

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1. All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired ...
3
votes
0answers
926 views

Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
2
votes
0answers
70 views

Set of maximum overlaps

Assume I have a list of $N$ surfaces $\{S_i\}, i \in [1,N]$ which may or may not overlap. I also have a boolean function $F(S_{i_1},\dots,S_{i_k})$ (with $1 \le k \le N$) which tests whether all ...
2
votes
0answers
26 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)...
2
votes
0answers
73 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
0answers
10 views

Maximal number of rounds we can do distributing 64 diners on 8 groups in different ways if they can't meet each other more than once?

N=64 hungry diners come to a buffet. We sit them at 8 different (s=8 people at each table) tables so that they get to know each other while they eat. After a while we distribute them over the tables ...
2
votes
0answers
116 views

Maximum number of non-overlapping rectangles where each contains a minimum number of points

Given n points and 0 < p < n, find the maximum number k of rectangles such that each rectangle contains at least p points and no two rectangles overlap. Each point is distinct from every other ...
2
votes
0answers
57 views

Inexact cover, or cover with gaps

Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem. In the Knuth's research papaer, linked above it is shown how Polymino problem (that is ...
2
votes
0answers
78 views

Grouping elements optimally other than NP-hard approach

Given a number $N$, I need to make a new array $B$ of size $n$ (index-1 based) such that the product of $B[i]-(i-1)$ for $1 \le i \le n$ is equal to $N$ and $B[n]$ is minimum and $B[i] \ge B[i-1]$ and ...
2
votes
0answers
35 views

Constrained selection of a random sample from a set of items with multiple attributes

Suppose I have a collection of N items, each of which has A different attributes, a1, a2, ..., aA. Attribute ai can take on Vi different possible (discrete) values, distributed across the population ...
2
votes
0answers
94 views

Efficient algorithm for “group-sum-min” problem

Given two finite sets $A, B \subseteq \mathbb{C} \times \mathbb{R}$, each stored as an array, define $$ S = \{ (z_1 + z_2, x + y, z_1, z_2, x, y) : (z_1, x) \in A, (z_2, y) \in B \} $$ and $$ f(s) = \...
2
votes
0answers
152 views

What is an efficient algorithm to solve the following combinatorial optimization problem?

I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes: weight, shape (denoted by number of faces, $n_{\rm ...
2
votes
0answers
59 views

Can't evaluate original Y combinator, two other variants do work, what do I miss?

I have made an evaluator of Lambda expressions. I tried to do Y combinator, but for some reason I can't get the original one working: $$λf.(λx.f \space (x \space x)) \space (λx.f \space (x \space x))\...
2
votes
0answers
90 views

Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?

The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux. But, since every permutation has a unique Young's tableau, there seems no reason as ...
2
votes
0answers
31 views

Is there a skippable, countable generator for unique permutations up to some symmetry?

Is there a good algorithm for generating all and only the unique permutations of a finite set respecting some kind of symmetry? For example, in Klondike solitaire, the two black suits are ...
2
votes
0answers
42 views

Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
2
votes
0answers
74 views

Activity scheduling with activities that can move around

In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values: Duration: The length of time the activity takes Earliest time to start: The earilest ...
2
votes
0answers
52 views

Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula ...
2
votes
0answers
217 views

How to formalise efficient payment with a collection of coins in a wallet?

Context If you have to pay an amount of money at a store and have a limited collection of payment items (i.e. coins and banknotes) -- let's for simplicity assume there are only coins -- a trivial ...
2
votes
1answer
50 views

Counting permutations whose elements are not exactly their index ± 1

This is a special case of the question: Counting permutations whose elements are not exactly their index ± M The $M=0$ case has already been solved, but no one was sure how to work out the non-...
1
vote
0answers
37 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
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
0answers
51 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
18 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
39 views

Number of binary trees of size $n$ such that all subtrees of same size are equal?

For a binary tree $t$, let the size $|t|$ be the number of leaves of $t$. I am interested in the following property of a binary tree $t$: If two subtrees $t'$ and $t''$ of $t$ have the same size, i.e. ...
1
vote
0answers
88 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
51 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
23 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
587 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
32 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
0answers
48 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
78 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
94 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 $...