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

# Questions tagged [combinatorics]

Questions related to combinatorics and discrete mathematical structures

510 questions
Filter by
Sorted by
Tagged with
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 ...
40 views

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 ...
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. ...
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 | ...
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 ...
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 ...
37 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
34 views

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 ...
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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-...
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 =...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...