Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

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

The Hydra Game algorithm

I was recently introduced to the Hydra Game by the youtube channel Numberphile (https://www.youtube.com/watch?v=prURA1i8Qj4). In this video, they discuss many variants of the Hydra Game - cut off one ...
SomeCallMeTim's user avatar
0 votes
0 answers
18 views

Algorithm to "reverse" search/match pairs from results

Sorry, I don't know how to title it clearly. There is a game, where players can send their units to attack another player's units (weeell, there is a lot of games like that). Each unit has some value. ...
herhor67's user avatar
-1 votes
0 answers
23 views

Is deciding all combinations of repeated usage of $A$ does not sum up to $A$ coNP-complete? [closed]

Given a set $A$ $=$ {$2,3,...$}, decide if every possible combination with repeated usage of set $A$ makes the following true for all combinations where $\sum_{x \in A} x \neq \sum_{y \in B} y$ ? ...
The T's user avatar
  • 319
1 vote
1 answer
52 views

Combinatorial Optimization Assignment Problem as Graph Coloring Problem

Im trying to present a Combinatorial Optimization Problem that is kind of Assignment-Like in a different way so that it is perhaps easier to solve with conventional Algorithms. I'd like you to look ...
ImNotSure's user avatar
0 votes
1 answer
30 views

How can I assign people to groups of 4 and optimize for "strangers" on a week-to-week basis when the group can change?

Let's say I have a group of people that meets every week. I would like to assign them to groups of 4. How can I assign these people such that, week after week, collectively, every group consists ...
squeegene's user avatar
  • 101
8 votes
1 answer
529 views

Is there a linear-time algorithm for randomly sampling weighted combinations?

For concreteness, here's the specific problem description: suppose we have a set $S$ of $n$ items $a_1, a_2, \ldots, a_n$ with weights $w_1, w_2, \ldots, w_n$ respectively. The goal is to select a ...
Steven Stadnicki's user avatar
1 vote
0 answers
38 views

How many different colors are possible to generate in the HSV Color Space using OpenCV?

I don't know if this post belongs in this site because I feel it might be a programming question, but also I feel it might be related to the way Color Spaces work, if it does't belong here I can ...
Nau's user avatar
  • 111
0 votes
1 answer
39 views

Regular branch and bound vs integer programming branch and bound

In the context of linear integer programming, we have a branch and bound algorithm described here. This involves solving the non-integer constrained linear program and successively introducing ...
Rohit Pandey's user avatar
8 votes
0 answers
96 views

Problem of constructing binary sequence with least possible 1s under given constraint

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the ...
Relja Šegvić's user avatar
2 votes
1 answer
65 views

Covering a graph with M cliques maximizing total edges weight

I am working on a problem that involves distributing a set of N supplements across a predefined number of meals (M) in a way that maximizes the total number of positive interactions and minimizes ...
essacult's user avatar
1 vote
0 answers
111 views

How many comparative sorting algorithms are there?

I've invented an abstract structure to represent a comparison-based sorting algorithm, which I will call a comparison tree (similar to the decision tree of a comparative sorting algorithm). ...
sbh's user avatar
  • 51
5 votes
0 answers
75 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
2 votes
1 answer
58 views

Weighted bipartite maximum cost with a fixed number of vertices

Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph with the maximum sum of all weights and: Only a constant number $n$ of vertices ...
Lozan's user avatar
  • 21
2 votes
1 answer
52 views

Number of n-variable symmetric boolean functions that are linear

How many symmetric boolean functions exist that are linear? Let $f$ be a $n$-variable boolean function. $f$ is said to be symmetric if it is unchanged by any permutation of its variables, i.e. for 2-...
M3n4p's user avatar
  • 23
1 vote
0 answers
37 views

Set cover variation: disjoint covers for all but one element

In the classical set cover problem, we are given the set $U$ of elements $\{1, \dots, n\}$ and a collection $C$ of some subsets such that their union is the whole set. Now, I will introduce the first ...
cgss's user avatar
  • 111
3 votes
2 answers
416 views

Find Minimum Transformation Between Multisets of Lists of Cards

Brief: I have two configurations, a and b, of the same set of Rummikub tiles (a may not be a ...
xdaimon's user avatar
  • 53
0 votes
0 answers
51 views

How to estimate the number of nodes in a trie based on a dictionary of words?

Say I want to build a trie out of 800,000 Sanskrit "base" words (in Devanagari script), with 20 prefixes and 2,000 possible suffixes. Each word is anywhere from 1-20 characters, and prefixes/...
Lance's user avatar
  • 2,223
1 vote
1 answer
331 views

Finding all stable matchings in stable marriage problem

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
void's user avatar
  • 11
0 votes
0 answers
17 views

Finding all stable matchings in stable marriage problem [duplicate]

I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
void's user avatar
  • 11
0 votes
1 answer
53 views

fast estimation of the amount of unique combinations

Let's say I have a set of two columns - Name, Surname. I have a list of possible values for Name -> Jacob, John Surname -> Mayerson, Kindle. I want to generate a set of unique combinations for ...
lapots's user avatar
  • 125
1 vote
1 answer
92 views

Is there an efficient algorithm for this ecommerce optimization problem?

Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules: There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
Jo Ma's user avatar
  • 15
1 vote
1 answer
58 views

Maximum Weighted coverage approximation algorithm?

I am looking for an algorithm similar to the unweighted maximum coverage. However, I have been unable to find a similar algorithm for the weighted version. How should I modify the algorithm above to ...
calveeen's user avatar
  • 141
0 votes
0 answers
27 views

Enumerate all n-tuples in parallel

Let $T = \{0, 1\} ^ {n}$, i.e. set of all $n$-bit binary strings ($n$-tuples). Let $f : T \to T$ be a function, that maps one string to another. $f$ is bijective, but $f^{-1}$ is hard to compute. It ...
Georgy Firsov's user avatar
1 vote
0 answers
39 views

Grouping transactions having pre-determined sums?

I have a transaction grouping problem that I'm having trouble to devise the algorithm to solve it. Not even ChatGPT (version 3.5) can solve this correctly. Suppose I have five transactions: ...
adib's user avatar
  • 111
0 votes
0 answers
47 views

Binary combinatorics with rank

I am looking at finding acceptable binary values with maximum 2 consecutive 1s and 0s, from a range of maximum 6 bits (2^6 values). Also, I want to rank and unrank these subset of values (in ...
Dave's user avatar
  • 23
0 votes
1 answer
27 views

How can I organize groups of people, who don't know each other, on a regular cadence?

I'm trying to figure out an algorithm for this specific problem. The problem: I have N people (say 60 but could be far more) that I want to organize into groups of 4 on a monthly cadence. The ...
Craig's user avatar
  • 101
1 vote
1 answer
70 views

Number of maximal induced trees in a connected planar graph

An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot ...
Yolov4's user avatar
  • 73
0 votes
0 answers
28 views

Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)

The following a small-scale example meant to illustrate the general problem Suppose we have $n = 60$ marbles that we want to distribute into 3 bowls, $B = \{bowl_1, bowl_2, bowl_3\}$ The marbles can ...
silass0's user avatar
1 vote
1 answer
77 views

Order in a subset

Lets consider a range of "K" binary digit numbers. In that range, we want to take a subset of those values which have (<="n" consecutive 0s) AND (<="n" consecutive ...
Dave's user avatar
  • 23
0 votes
0 answers
37 views

Growth of a set of propositional formulas under partial evaluation

Definitions: Let $n \in \mathbb{N}, n \geq 1$. We write $|\alpha|$ to denote the length in characters of an expression $\alpha$ in propositional logic. We define partial evaluation in the normal way ...
ShyPerson's user avatar
  • 925
0 votes
0 answers
20 views

What are some applications of gerrymandering for Electronic Design Automation/Very large-scale integration?

There are many algorithms used for Very large-scale integration design (VLSI) or EDA (Electronic Design Automation). Most of them are challenges that imply some combinatorial/mathematical optimization....
isimo00's user avatar
1 vote
0 answers
32 views

Find an assignment discarding a subset of possible assignments

We have a $N \times N$ cost matrix where the cost denotes the amount incurred for assigning a worker to a task. The number of possible assignments is $N!$. Let us call this set of all possible ...
akhil's user avatar
  • 11
0 votes
1 answer
64 views

Number of matchings in a bipartite graph having missing edges

Suppose we have a bipartite graph with $N$ vertices on either side. In the full bipartite graph, the number of edges is $N^2$ and the number of possible matchings (i.e. assignments) is $N!$. Now ...
akhil's user avatar
  • 11
0 votes
1 answer
52 views

Is there an algorithm for the distrubution of ducks into ponds?

The following is small-scale example is meant to illustrate the general distribution problem Consider 4 parks, each with exactly 1 pond. Parks are marked as vertices in the following undirected graph: ...
silass0's user avatar
0 votes
1 answer
74 views

Efficient algorithm for finding the target sum

Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
jamesw1's user avatar
0 votes
1 answer
67 views

Algorithm to generate all N-size variations of natural numbers

For a size N>=1 (an input variable) I need an algorithm to generate all variations (no duplicates allowed) of natural numbers greater than zero. For N=1, this is trivial: ...
Barney's user avatar
  • 155
2 votes
0 answers
41 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
1 answer
47 views

Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"

I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is ...
Mike Battaglia's user avatar
1 vote
0 answers
50 views

Are there known algorithms to find a line that intersects a given set of segments?

Are there known algorithms to find a line that intersects a given set of segments? In: A finite set of segments. Out: A line that cross all these segments or explicit answer that there is no such line....
Leonid Dworzanski's user avatar
1 vote
1 answer
72 views

Exact cover matrix for project planning

I'm trying to solve the project planning problem using DLX and exact cover matrix, but I'm struggling to find the set of constraints (columns) and the set of options (rows) to achieve this. Here is a ...
Mohamed Challouf's user avatar
1 vote
0 answers
34 views

Maximum size of a graph with given girth

I am unable to get the bound on the maximum size of a graph of order $n$ with girth $g$. Is there any literature regarding this. I know that there is an asymptotic bound on the size of a graph $G$ ...
vidyarthi's user avatar
  • 175
0 votes
1 answer
80 views

On hardness of finding total dominating sets in triangle-free graphs

A total dominating set $S\subset V(G)$ is a set of vertices such that $\forall v\in V(G)$, $v$ has a neighbour in $S$. The minimum total dominating set of $G$ is a total dominating set of $G$ of ...
Ankit Gayen's user avatar
2 votes
1 answer
117 views

On hardness of finding dominating sets in triangle-free regular graphs

A $k$-regular graph is one in which every vertex has degree k. A triangle-free graph is one in which any three vertices do not form a triangle. A dominating set $D$ of a graph $G$ is a set of vertices ...
Ankit Gayen's user avatar
1 vote
0 answers
41 views

Finding maximal cliques in a graph represented as a collection of complete biparti graphs

I have a graph whose edges can be very efficiently represented as a set of complete biparti graphs (that may share nodes). Is there a name for such a representation? And secondly. I want to enumerate ...
Bob Lucassen's user avatar
2 votes
1 answer
67 views

Selecting a submatrix of a binary matrix NP hard?

I have the following problem and I am wondering if it is NP Hard or not. Let $A$ be a binary matrix whose rows and columns are indexed by the sets $\mathcal{I}=1,...,m$ and $\mathcal{J}=1,...,n$. A ...
D. Sena's user avatar
  • 23
1 vote
1 answer
39 views

Densest Sub Graph and forbidden Pairs

Given two graphs $G$ and $F$ on the same vertex set $V$. Compute a sub set $\tilde{V}\subset V$ which' sub graph of $G$ is of maximum density and does not have any pair that is connected in $F$. ...
Daniel Schwegler's user avatar
1 vote
1 answer
71 views

Faster finding of a subset of bits with all combinations in the bitstrings

Assume that I have a bunch of bitsets (strings on $\{0,1\}$) of the same length, e.g.: 101110001 001001101 010101010 101001001 101010101 I want to find the largest ...
Dmitry's user avatar
  • 345
1 vote
1 answer
160 views

Reorder columns in a 2d matrix to maximize the count of all repeated subarrays across all rows

I have a matrix (input): -- c1 c2 c3 r1 AA BB CC r2 CC RR BB r3 EE DD FF r4 KK DD EE r5 DD GG KK r6 PP QQ KK Let's call each matrix cell a namespace. If two ...
night-crawler's user avatar
1 vote
1 answer
50 views

Given a bipartite graph G and an integer l, how many edge subsets of size l are there such that the degree of each vertex is odd?

Given a bipartite graph $G=(V,E)$ and an integer $l$, how many edge subsets ($E'\subseteq E$) of size $l$ are there such that the degree of each vertex in the resulting subgraph $G'=(V,E')$ is odd? I ...
QNA's user avatar
  • 133
1 vote
0 answers
45 views

What is the worst case time complexity of unranking n choose k combinations (combinatorial number system, combinadics)

The combinatorial number system shows that there is a bijection between the natural numbers less than $n \choose k$ and $n\choose k$ combinations. There is a greedy algorithm for unranking ...
Quantum Guy 123's user avatar

1
2 3 4 5
16