We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

Filter by
Sorted by
Tagged with
3
votes
1answer
67 views

affinity based static load balancing

I am trying to find a good model the following problem: Given a collection of work packets x, y, z, ..., and a collection of worker nodes ...
1
vote
1answer
40 views

Checking large number of configurations with multiple constraints

I have a very large number of constraints such as: $ A1 \land B1 \land C1 \land D1 \land E1 \land F1$ $ A2 \land B2 \land C2 \land D2 \land E2 \land F2$ $ A3 \land B3 \land C3 \land D3 \land E3 \land ...
0
votes
1answer
132 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 ...
2
votes
2answers
36 views

Cuckoo filters for non powers-of-2

The Cuckoo filters paper (https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf) claims a 95% load factor, however it seems to make an implicit assumption that the table size is a power of 2, and ...
2
votes
2answers
151 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
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 ...
1
vote
1answer
80 views

Cardinality of ordered n-grams and subsets of those n-grams from a given set [closed]

Given a set T={A,B,C}, I need to know the cardinality of all ordered sequential n-grams and the total cardinality of all subsets of those n-grams. The ordered sequential n-grams of the set T above ...
2
votes
2answers
38 views

Points at distance $k$ or less in 2D grid

How can we prove that the total number of mesh points k or fewer jumps away from an arbitrary point in a 2D mesh is: $2k^2 + 2k + 1$. I tried making a $3 \times 3$ mesh. ...
2
votes
1answer
118 views

Possible combinations of soccer results

I'm trying to calculate the best and worst position for each team in the ranking based on the weekly matches. Suppose we have 4 teams with these position: Pos.| Name | Pts. 1 | Team A | 12 2 | ...
4
votes
3answers
125 views

Do most bitstrings expand if they halt when executed by a Universal Turing machine?

According to the counting argument, most bitstrings are incompressible or only slightly compressible. However, the counting argument does not work in the opposite direction, since there are an ...
1
vote
1answer
218 views

How does one generate all the terms of a multivariate polynomial algorithmically?

I was interested in writing a program that given the number of variables and the degree of the multivariate polynomial, it was able to output the multivariate polynomial itself or evaluate it at a ...
4
votes
1answer
37 views

Finding all additive orders

Suppose there are $m$ items, and each item has a price. We order the subsets of items according to their price. For example, if the price of $x$ is 1 and the price of $y$ is 2, then the order is: $$ \...
1
vote
1answer
679 views

Number of rooted labelled trees

According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2 If the tree is rooted then in each tree we can ...
1
vote
1answer
127 views

Algorithm to find the closest possible value among several combinations

I have the following problem and would like an orientation on which algorithms I can try to adapt to solve it in the best possible way. SCENARIO A company has a warehouse where it stores several ...
2
votes
1answer
51 views

Bound covariance of two discrete random variables

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
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
1answer
31 views

number of subsegments that contain A[i] as the minimum

I've recently been thinking about this problem. Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum. To better ...
2
votes
2answers
240 views

Enumerate partitions of a set with blocks of equal size

Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$? In The art of computer programming (Fascicle 3B) by Knuth, there's ...
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 ...
-2
votes
2answers
309 views

Combination generator - sets of size k from n [closed]

unique numbers $1 - n$ combinations (sets) of size $k$ $k < n$ do not re-use an $n$ in a set [1, 1, 1] is not valid How to generate all unique sets of size $k$? [1,2,3] = [3,2,1] order does ...
3
votes
2answers
620 views

Is there an algorithm that can solve chess within the span of a human lifetime?

According to Shannon (in his 1949 paper) the game of chess has too much complexity to be solved by a brute-force search of the game tree: A machine... would require over $10^{90}$ years to ...
1
vote
1answer
448 views

What is the optimal way to find unique combinations of N sets of integers

This is a simplification of a real world problem and only a small piece at that. Example sets are ...
0
votes
1answer
28 views

Data Analysis: Have 70 data parameters, how many different classes of 3 are possible?

The order of the classes of three does not matter. Example: 1,2,3 and 3,2,1 would be considered one class. I am trying to do fisher discriminant analysis on a set of data and want to begin reducing ...
2
votes
1answer
109 views

Best combination of values pulled from a matrix

What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized? For example, given the ...
1
vote
1answer
69 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 ...
5
votes
1answer
82 views

Uniformly Random Nested Subset Pairs

Main Question We can represent subsets of a vector using, say, a bit mask. Let's say a nested subset is a pair of masks, for example ...
1
vote
1answer
71 views

How to find number of permutations of 1-N length, each [1-N] with k values

This imaginary problem involves a vector of length 5, with each value to be selected from a unique range of values. A real-world example might include 5 different single-digit combination locks. ...
1
vote
1answer
34 views

Two definitions of the Reed-Muller code

I found two definitions Reed-Muller codes being used in literature. More specifically for any $n \in \mathbb{Z}^+$ and $1 \leq d \leq n$ we define the set $RM(d,n)$ in two possible ways, 1. $RM(d,n) =...
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
1answer
421 views

Subset partition problem variant

Given a set S of integers, the task is to partition the set into subsets such that: Total number of partitions is maximized Each partition has sum at least K This looks like a variant of bin-packing ...
0
votes
1answer
79 views

Find hamming codewords in r=2^k dimensions

There is the original problem, and an equivalent problem. The equivalent problem: construct a set $A$ that contains bit arrays of length $r-1$, where $|A|=2^{r-1}/r$ and $hamming \space distance (i, ...
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
1answer
21 views

A comparison operation for lists, based on P(a > b)

Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from ...
2
votes
1answer
77 views

Algorithm to generate integer sets fulfills restrictions

I'm trying to solve the following problem. Input positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.) Output A list $S_1, \dots, S_k$ of all possible integer multisets (a ...
0
votes
2answers
195 views

Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters?

Question: Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters? And how many words can we form with up to 4 letters? I was thinking about the logic behind this and came up with ...
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
votes
2answers
357 views

What will be the time complexity for the following search algorithm in a graph? [duplicate]

I have a graph which looks something like below I am searching for a given string s going down such that at every node it makes a decision (either to visit the ...
2
votes
0answers
136 views

Find, with proof, the number of distinct graphs with the vertex set $V = \{1, 2, \ldots,n\}$ [closed]

Let $n \in \mathbb{Z^+}$. Find, with proof, the number of distinct graphs with the vertex set $V = \{1, 2, \ldots,n\}$. We say two such graphs are distinct if one of them has an edge $(u, v)$ and the ...
1
vote
1answer
138 views

Unique number to represent a combination of 5 numbers 1-39

This is a related question poker hand representation and I got a great accepted answer. The problem can be reduced to a virtual 39 card deck that from what I can tell is 16 bits. I have 5 numbers 1-...
11
votes
3answers
997 views

Represent a 5 card poker hand

A deck of cards is 52. A hand is 5 cards from the 52 (cannot have a duplicate). What is the least amount of bits to represent a 5 card hand and how? A hand is NOT order dependent (KQ = QK). 64329 =...
-1
votes
2answers
357 views

How many integers can you represent with 6 bits?

I might be wrong but I think it must be 2^6 = 64 integers?
2
votes
1answer
933 views

Algorithm to identify if a string of numbers is a lottery sequence

Suppose that a valid lottery ticket consists of a sequence of 7 numbers drawn from the set $\{1,2,\ldots,59\}$. Given a string like "$12345678$", I want to efficiently print all the lottery sequences ...
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 ...
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 ...
1
vote
1answer
283 views

Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets

The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind) Is ...
2
votes
1answer
43 views

Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items

I have $n$ items that have a total of $k$ properties. Each item can have any number of properties, from $1$ to $k$. There is no upper limit to k (the lower limit is $\lceil log(n) \rceil$). The items ...
4
votes
1answer
205 views

lower bound for Renyi–Ulam Game with lies

Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ). Game : $A$ chooses an element in {1,2....,n} $B$ tries to ...
3
votes
1answer
91 views

Sum collision from two lists of numbers

Suppose you have two large lists of integers of length $N$, and you want to find two pairs $(a_1, b_1)$, $(a_2, b_2)$ from the lists such that $a_1 + b_1 = a_2 + b_2$ (modulo the integer width). Say ...
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 ...