Skip to main content

Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
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 ...
0 votes
2 answers
4k views

Given n numbers How to find out a set of numbers whose sum equal to a certain given number

I am given an list of numbers and A number-s. I need to find out the collection(s) of numbers from the list of numbers whose sum corresponds to the given number s. ...
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}{...
3 votes
1 answer
82 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-...
0 votes
0 answers
14 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 ...
0 votes
1 answer
123 views

Complexity for optimized k-sum problem

Following up on these two posts Generalised 3SUM (k-SUM) problem? https://people.csail.mit.edu/virgi/6.s078/lecture9.pdf The claim is that k-sum in the general case can be solved in $O(n^{k/2}log(n))$ ...
5 votes
6 answers
1k views

Enumerating all partial permutations of given length in lexicographic order

I need to generate all unique tuples of length k chosen from a series of unique, positive integers. In my case n choose k will have n=10, 1 <= k <= 10; and the series I am choosing from is { 0, ...
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 ...
3 votes
1 answer
652 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} = \...
1 vote
4 answers
195 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 ...
3 votes
1 answer
86 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 ...
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 - ...
2 votes
1 answer
55 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$...
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$. ...
2 votes
2 answers
210 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 ...
1 vote
1 answer
145 views

Sorting a collection of tuples using merge rearrangements

Given a collection of tuples $X=\{(x_1,y_1),\dots,(x_n,y_n)\}$, where elements $x_i, y_i \in R_{\geq 0}$ are non-negative real values. The collection $X$ is sorted if $x_i \leq x_{i+1}$ and $y_i \leq ...
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 ...
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. ...
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 ...
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,...
0 votes
2 answers
184 views

Create binary numbers with a described pattern

I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$...
0 votes
1 answer
167 views

Find the total no. of strings ( len n ) possible given a set of sets of letters such that no two letter from a single set should be in that string

This was an algorithm problem but I am having problems in formulating it. I have a certain approach but I do not know how to fully execute: Given 26 letters in total All possible strings of length n ...
0 votes
1 answer
549 views

Counting chords intersections in a circle

The problem is: Given 2n distinct endpoints of n chords on the unit circle, count the number of intersections between chords (if k chords intersect at one point, that point counts as $\binom{n}{2}$ ...
0 votes
1 answer
59 views

BSTs with repeating keys

The problem is to count number of unique binary search trees with keys $a_1,a_2,...,a_n$, given that some of the keys are not unique. For example, $a$ could be 2, 1, 1, 4, 3, 4. We could try an ...
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 ...
0 votes
1 answer
67 views

Counting number of 1-hop paths in a sparse graph

Given a sparse undirected graph $G=(V,E)$ where $|E|=O(|V|)$, a one-hop path between a pair of vertices $(u,v)$ is a path in $G$ connecting $(u,v)$ where there is exactly one intermediate vertex ...
0 votes
1 answer
127 views

Greedy Algorithm for Geometric Set Cover

Consider the geometric set cover problem https://en.wikipedia.org/wiki/Geometric_set_cover_problem. The Wiki article says there is a simple greedy algorithm for the one-dimension case, what is the ...
9 votes
1 answer
547 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 ...
3 votes
1 answer
108 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) ...
1 vote
1 answer
75 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 ...
12 votes
3 answers
3k views

Simple graph canonization algorithm

I'm looking for an algorithm that provides a canonical string for a given colored graph. Ie. an algorithm that returns a string for a graph, such that two graphs get the same string if and only if ...
0 votes
2 answers
87 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 ...
1 vote
1 answer
109 views

Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within ...
1 vote
0 answers
46 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 ...
1 vote
1 answer
135 views

Solving problems by dynamic programming plus quantization to avoid combinatorial explosion

The context: I have been working lately with problems like the following: Let $x_{k}\in\mathbb{R}^n$ be a state evolving accroding to: $$ x_{k+1} = f(x_k,u_k) $$ where $k \in \{ 0,\dots,N-1 \} $, ...
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 ...
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 ...
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 ...
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). ...
1 vote
1 answer
404 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 ...
5 votes
0 answers
76 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 ...
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 ...
1 vote
1 answer
74 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 ...
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 ...
3 votes
2 answers
418 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 ...
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 ...
0 votes
0 answers
71 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/...
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 ...
3 votes
2 answers
3k views

Counting the number of squares in a graph

Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4. I know that it is possible to count the number of ...
1 vote
1 answer
75 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 ...

1
2 3 4 5
16