Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

167 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
9 votes
0 answers
222 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, ...
coderodde's user avatar
8 votes
0 answers
215 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 ...
user306101's user avatar
7 votes
0 answers
622 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 ...
Mohammad Al-Turkistany's user avatar
6 votes
0 answers
166 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 $\...
unamourdeswann's user avatar
6 votes
0 answers
213 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 ...
Gaganpreet's user avatar
5 votes
0 answers
68 views

Rank and unrank for Heap's Algorithm

I am looking for an unranking (and ranking) algorithm for permtuations that is consistent with the order that Heap's Algorithm generates permutations. I have been researching a bit on ranking and ...
Gunnar Bernstein's user avatar
5 votes
0 answers
60 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 \...
Berk U.'s user avatar
  • 429
4 votes
0 answers
71 views

Generating graphs with partially overlapping cliques

Currently, I am working on a research project where I will utilise reinforcement learning for the diversified top-$k$ clique search problem. To train the reinforcement learning algorithm, I need to ...
Jesse's user avatar
  • 41
4 votes
0 answers
52 views

Largest sumset without multiplicity

Given a group $G$, the sumset of two sets $A,B$ is denoted as $A+B = \{a+b:a\in A,b\in B\}$. We say $A$ injects $B$, if $A+B$ has no multiplicities, i.e. $|A+B| = |A||B|$. We let $I(B) = \max \{|A|:A \...
Zach Hunter's user avatar
4 votes
0 answers
73 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 ...
usul's user avatar
  • 4,119
4 votes
0 answers
127 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\\ ...
L Lawliet's user avatar
4 votes
0 answers
116 views

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

In the following, I consider rooted, unlabelled, ordered binary trees, where each node has exactly $0$ or $2$ children (I will simply call them binary trees). A binary tree $t'$ is a subtree of a ...
Danny's user avatar
  • 994
4 votes
0 answers
205 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 ...
mikebolt's user avatar
  • 176
4 votes
0 answers
68 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 ...
user12486's user avatar
4 votes
0 answers
1k 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 ...
mayank's user avatar
  • 325
3 votes
0 answers
70 views

Make Change in Linear Time

The question is motivated by this post on StackOverflow. Given an integer $n$ and a finite list of distinct positive integers $ds$, let $f(n, ds)$ denote the number of ways $n$ can be expressed as a ...
hilberts_drinking_problem's user avatar
3 votes
0 answers
73 views

Number of permutations with satisfactory triangles

We are given $N$ points($N \leq 40$), where no combination of three or more points is colinear. The values of $x$ and $y$ are bounded by [$0$,$10^4$]. The problem is to find the number of permutations(...
Jonathan Mcgee's user avatar
3 votes
0 answers
297 views

Speeding up the Rummikub algorithm - explanation required

Regarding this question: Rummikub algorithm. I was reading the first part of the solution in the posted answer (specifically, when there are no jokers involved, all tiles are distinct and only four ...
S.T.'s user avatar
  • 131
3 votes
0 answers
113 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 ...
waiwai933's user avatar
  • 131
3 votes
0 answers
178 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 $\...
T.Harish's user avatar
  • 222
3 votes
0 answers
41 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} ...
Cole Comfort's user avatar
3 votes
1 answer
102 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) ...
Thomas Bosman's user avatar
3 votes
1 answer
639 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} = \...
michal's user avatar
  • 103
3 votes
0 answers
487 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 ...
user3724568's user avatar
2 votes
0 answers
39 views

Bananagrams decision problem - computational complexity

I've been playing Bananagrams recently, and have begun to wonder about the math behind it from a computational perspective. I've tried to formalize the problem as a decision problem below. Loosely ...
AbsentMynd's user avatar
2 votes
0 answers
45 views

Designing Shortest Route

Suppose we have a metric space $(X,d)$ and we call $r$ to be a root vertex and then there are $n$ clients(i.e. $n$ vertices/nodes) who need packages delivered to them from $r$. The $i$th client ...
Sandra's user avatar
  • 63
2 votes
0 answers
72 views

Playing with boxes: NP-hard? [Graph Theory]

You are playing with boxes on a $K_{1, n}$-$\textbf{subdivision}$ graph $G:=(V, E)$ whose number of vertices is odd, i.e., $|V| \equiv 1$ (mod $2$) with a given central point $C$ such that $\forall v \...
Muses_China's user avatar
2 votes
0 answers
45 views

Lowest total cardinality mutually exclusive construction of a superset

Let there be $N$ sequences containing at least one set each. Each set has at least one element each. Select exactly one set from each sequence. The selection within each sequence is mutually exclusive....
Reinderien's user avatar
2 votes
0 answers
43 views

Proving existence of sinkless orientation on graph with minimum degree 2

I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge. As a ...
NiRvanA's user avatar
  • 159
2 votes
0 answers
83 views

An unknown combinatorial optimization problem

I have $N$ available sensors and $M$ devices. Each device needs $a$ sensors. One sensor cannot be used on multiple devices. Each sensor has two properties defined by $H$ and $R$. Let $\sigma_{i\_H}$ ...
user1506630's user avatar
2 votes
0 answers
43 views

Efficient solution to this scheduling problem or integer optimization problem

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
FeedbackLooper's user avatar
2 votes
0 answers
64 views

Is this a variant of "Path Covering"?

According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G". In my research, I met a similar problem. There, you can add ...
Light Yagmi's user avatar
2 votes
0 answers
27 views

How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
redox's user avatar
  • 21
2 votes
0 answers
251 views

Example of *small* non monotone circuit such that any equivalent monotone circuit has greater size?

A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies: fan-in=2 for the AND and OR nodes fan-n=1 for the NOT ...
Dudi Frid's user avatar
  • 161
2 votes
0 answers
246 views

Minimun k-union from a different angle

I'm looking for work done on solving some problem which is very similar to the minimum k-union. The problem: There's a set of elements $E=\{e_1,e_2,...,e_k\}$ of size $k$, and a family of sets $S_1,...
Gilad Deutsch's user avatar
2 votes
0 answers
51 views

Finding multiple paths through a grid such that every grid square is equally used

Setup Here’s the setup: I have an $N$ x $N$ grid of tiles, and a list of $M$ agents that need to move across the grid. Each agent has its own start tile $S(a)$, end tile $E(a)$, and an exact number ...
Paul Accisano's user avatar
2 votes
0 answers
36 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 ...
hasManyStupidQuestions's user avatar
2 votes
0 answers
155 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 ...
Valentin Hirschi's user avatar
2 votes
0 answers
29 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)...
user1502040's user avatar
2 votes
0 answers
112 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). ...
Hang Wu's user avatar
  • 121
2 votes
0 answers
14 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 ...
skan's user avatar
  • 121
2 votes
0 answers
316 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 ...
P. Anderson's user avatar
2 votes
0 answers
80 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 ...
Joey's user avatar
  • 21
2 votes
0 answers
40 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 ...
Anne Hanna's user avatar
2 votes
0 answers
109 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) = \...
Alex Shtoff's user avatar
2 votes
2 answers
205 views

Matching 2 sets of items by price

I'm trying to solve the following problem in the most efficient way I can find. I want to trade my items for someone elses items, every item have a price and a value. I want to maximize the value of ...
RythemOfTheDay's user avatar
2 votes
0 answers
166 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 ...
Silent Sabreur's user avatar
2 votes
0 answers
75 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))\...
MarkokraM's user avatar
  • 385
2 votes
0 answers
923 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 ...
Solaxun's user avatar
  • 121
2 votes
0 answers
34 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 ...
amashi's user avatar
  • 56