Skip to main content

Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
4 votes
1 answer
92 views

Expected Entropy of the Empirical Distribution

Given a distribution on $n$ outcomes where outcome $i$ has probability $p_i$, the Shannon entropy of the distribution is defined as $- \sum_{i = 1}^n p_i \cdot \log_2 p_i$. Let's suppose I sample from ...
Karagounis Z's user avatar
0 votes
0 answers
15 views

Analysis of LRU algorithm with uniformly random access

Consider the following model of LRU: The cache can hold $k$ pages. The memory has $n$ pages. In each $t \in \{1, 2, \dotsc, T\}$ the program selects a random page to access independently (i.e. each ...
strategyproof's user avatar
0 votes
1 answer
43 views

Binary subset rank and unrank

Let there be "N" bits. We want to rank and unrank a specific subset of bit combinations based on the following criteria - ...
Dave's user avatar
  • 25
2 votes
1 answer
56 views

Number of graphs that almost contain a $k$-clique

A (loop-free) graph almost contains a $k$-clique if it does not contain a $k$-clique, but adding an edge between any two different vertices that are not already connected by an edge would produce a $k$...
rus9384's user avatar
  • 1,696
3 votes
1 answer
88 views

The existence of a (nearly) quadratic time algorithm for 2-steps shortest path or smallest triangle

I am interested in two problems, which seem to be related, solving each will advance me in other possible directions. In both problems, $G=(V,E)$ is a positively-weighted undirected graph. Denote its ...
Mařík Savenko's user avatar
1 vote
0 answers
29 views

Minimum expected number of path to cut graph problem

I came up with a problem but was unable to show the hardness of the problem (NP/#P/P-hard). The problem is as follows. Given a directed graph $G=(V, E)$, each edge will have a confidence score $c$. ...
sweet-potato's user avatar
3 votes
1 answer
40 views

Best algorithm to evaluate a function that takes the elements of all possible combinations of N numbers

Consider a set $A$ containing $N$ real numbers. Let $f(X_{r,k})$ represent a function, where $X_{r,k}\subseteq A$ denotes the $k$th combination of $r$ elements from $A$, with $1 \leq k \leq \binom{N}{...
GeoArt's user avatar
  • 31
0 votes
0 answers
22 views

How can i allocate troops so as to maximize the number of bases conquered without going over a maximum time?

I have a set of bases which are connected by directed edges illustrating which bases can be attacked from any particular base. Bases have a health pool (ex: 1,000,...
paullc's user avatar
  • 1
0 votes
2 answers
67 views

Lossless compression collision such as 2 different files gives the same zip file after compression

Theoretically, if I try to compress some data I decrease the length of the data. I will give very simple example just for the sake of the example, in practice it will be similar but with much bigger ...
Zlelik's user avatar
  • 103
1 vote
4 answers
211 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
36 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
0 votes
0 answers
89 views

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

Given a set $A \subseteq \{1,2,3,\dots\}$, decide if $\sum_{x \in A} x \neq \sum_{y \in B} y$ for every $B$ that is a combination with repeated usage of $A$. We define $B$ to be a combination with ...
The T's user avatar
  • 321
0 votes
1 answer
33 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
9 votes
1 answer
553 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
51 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
42 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
99 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
68 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
113 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
79 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
63 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
3 votes
1 answer
86 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
  • 33
1 vote
0 answers
38 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
419 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
73 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,243
1 vote
1 answer
416 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
55 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
95 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
78 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
40 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
49 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
  • 25
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
72 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
85 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
  • 25
0 votes
0 answers
38 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
66 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
75 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
72 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
  • 167
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
49 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
76 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
81 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

1
2 3 4 5
16