All Questions
Tagged with combinatorics algorithms
1,045
questions
5
votes
1
answer
146
views
$X^A \equiv B \pmod{2K + 1}$
I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.
Is there something special about the modulus being odd that allows us to ...
- 51
1
vote
1
answer
71
views
Algorithm to find specific set of integers within sorted set
I need an effective algorithm to find a subset of integers within a set that meet the conditions:
The sum of sub-set items <= the "limit"
prefer to pick the subset with maximum values that fit ...
- 11
2
votes
0
answers
400
views
Efficient factorion search in arbitrary base
A factorion in base $N$ is a natural number equal to the sum of the factorials of its digits in base $N$. So, the decimal factorions are:
$1 = 1!$
$2 = 2!$
$145 = 1! + 4! + 5!$
$40585 = 4! + 0! + 5! +...
- 143
2
votes
3
answers
261
views
Calculate the number of strings without more than two succeeding occurrences of any character
Problem:
Given an arbitrary, finite alphabet $\Sigma$ with $|\Sigma| > 1$, define the language
$\qquad L = \{w \in \Sigma^* \mid w \text{ has no subword of the form } aaa, a \in \Sigma\}$.
Let $...
- 21
19
votes
4
answers
9k
views
Algorithm wanted: Enumerate all subsets of a set in order of increasing sums
I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time.
Given a set of ...
- 293
4
votes
3
answers
4k
views
Dividing a set into two subsets the optimal way (May be similar to the knapsack problem)
We have n stones having weight m[1]..m[n], and two sacks. We put each stone into first or second sack; the resulting sacks ...
- 143
11
votes
5
answers
12k
views
Secret santa problem
We decided to do secret Santa in our office. And this brought up a whole heap of problems that nobody could think of solutions for - bear with me here.. this is an important problem.
We have 4 people ...
- 221
2
votes
2
answers
152
views
Formula for the number of 0's in an alternating 0-1 matrix
I was working with a piece of code when I stumbled across a matrix, which is similar to this:
$$\begin{matrix}
0&1&0&1&0&1&0&\cdots\\
1&1&1&1&1&1&...
- 135
8
votes
1
answer
2k
views
Is there a simple algorithm to generate unlabeled graphs?
While working on some other problem I realized I need to generate (not only enumerate!) all unlabeled graph (or exactly ONE representative from each equivalence class of labeled graphs) with a certain ...
- 1,431
4
votes
2
answers
358
views
Rota's "lure of the algorithm"?
Quoting Gian-Carlo Rota (from the Foreword to Richard Stanley's Enumerative Combinatorics Volume I), "In mathematics, however, the burden of choice faced by the writer is so heavy as to turn off all ...
- 153
9
votes
4
answers
4k
views
calculating n choose k mod one million
I am working on a programming problem where I need to calculate 'n choose k'. I am using the relation formula
$$
{n\choose k} = {n\choose k-1} \frac{n-k+1}{k}
$$
so I don't have to calculate huge ...
- 315
6
votes
2
answers
2k
views
How can I reduce a number?
I'm trying to work on a program and I think I've hit a math problem (if it's not, please let me know, sorry). Basically what I'm doing is taking a number and using a universe of numbers and I'm ...
- 419
0
votes
1
answer
1k
views
Project Euler Problem 338
I'm stuck on Project Euler problem 338. This is a cross post from StackOverflow where I initially posted, however, it was suggested that I post it here too since the problem mostly relies on math. The ...
- 49
27
votes
2
answers
3k
views
Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$
More precisely,
$$\sum_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} -\frac{\pi^2 + 6 \gamma^2}{12 \log^2 n} +O\left(\frac1{\log ^3 n}\right).$$
This is Theorem 4 ...
- 1,727
17
votes
3
answers
11k
views
Generate Random Latin Squares
I'm looking for algorithms to generate randomized instances of Latin squares.
I found only one paper:
M. T. Jacobson and P. Matthews, Generating uniformly distributed random Latin squares, J. ...
user14947
2
votes
0
answers
126
views
What does it mean if a sequence is indexed beyond its bounds?
I'm looking at a paper (On Base and Turyn Sequences by C. Koukouvinos, S. Kounias and K. Sotirakoglou) that describes an algorithm for finding specific sequences.
Part of the algorithm involves ...
- 183
2
votes
3
answers
478
views
Generate partitions of a set of words respecting order
I'm working on a program (using C++) that has a list of words in a vector: {"one", "two", "three", "four"} for example, and I'd need to get all possible partitions respecting the order and where ...
- 123
0
votes
1
answer
231
views
Cells counting problem
There is a 3D grid with cells for which we define its value (0 or 1) as F(i,j,k)=F(i-1,j,k) XOR F(i,j-1,k) XOR F(i,j,k-1), base cases are ...
- 1
0
votes
2
answers
202
views
Combinations Help
I have an application where I iterate through all k-combinations of a set of size n. For example here I have listed all k-combinations for when n is 4. Also I have separated each list of combinations ...
- 383
3
votes
1
answer
580
views
Proof: BEST-IN-GREEDY-Algorithm for Matroids maximizes all Bottleneck-Functions over Bases
Let $(E,\mathcal{F})$ be a Matroid. Given is a Bottle-Neck-Function $$b(F)=\min\{b(e)|e\in F\}$$
I want to prove that the Best-In-Greedy-Algorithm maximizes every Bottle-Neck-Function over the Bases.
...
- 2,225
3
votes
1
answer
122
views
Average result of game
I'm trying to find the average result for a game where you have 12 items (containing a score), you can pick up to five of them, one of them is a multiplier, that when selected multiplies your result ...
- 133
7
votes
3
answers
2k
views
A balanced latin rectangle (more rows than columns)
In psychology we sometimes use balanced latin squares for the order of our tests to counterbalance first-order carry-over effects (fatigue, learning, etc.) .
For our current study we want to pretest ...
- 123
4
votes
2
answers
326
views
Finding sets that do not intersect. Approximation algorithm
I am trying to solve the following problem. Let $S$ be a set and $F \subset {S \choose k}$ that is $F$ is a subset of the set of all $k$-sets of $S$.
A set $M \subset F$ such that no two elements ...
- 5,032
0
votes
2
answers
283
views
How can I create an equation for a Gaussian distribution based on a sum of a series?
I am trying to create an equation that will generate a Gaussian distribution such that y = the sum of f(x) in a series of integers 1->28. I have y and want to know what the value of x at each integer ...
- 103
2
votes
0
answers
702
views
Anti-prime sequence
I have permutation from $x$ to $y$.
And how to make sequence which $d$ summed numbers from this sequence ISN'T a prime number.
if we have sequence $x_1,x_2,x_3,x_4,x_5 \dots y$ than $d$ means :
$x_1+...
- 2,312
57
votes
2
answers
5k
views
How do the Catalan numbers turn up here?
The Catalan numbers have a reputation for turning up everywhere, but the occurrence described below, in the analysis of an (incorrect) algorithm, is still mysterious to me, and I'm curious to find an ...
- 41.7k
1
vote
1
answer
160
views
How to partition a list in smaller lists so that the odds of one element encountering another element is evenly distributed?
I'm struggling with an algorithm to divide a group of contestants into smaller groups to make up rounds. Take for example a group of $20$ people, which I want to divide into $3$ groups $(7,7,6).$ For ...
- 113
5
votes
2
answers
705
views
Generating fixtures for a Chess league, with a twist
I am in the process of building some software to generate fixtures for a chess league, which has a little twist which complicates matters. I would like to introduce a constraint whereby two ...
- 151
2
votes
3
answers
6k
views
The fastest algorithm for asymmetric travelling salesman problem (TSP)
What is the fastest algorithm for asymmetric TSP?
Maybe someone knows the fastest solution according to computer calculations. For example, WinQSB calculates 60 cities in 2-3 seconds on Intel Core 2, ...
- 133
2
votes
4
answers
242
views
Is this a kind of Permutation?
I'm trying to design an algorithm to generate something that I don't know how exactly to call! Ok, I'm not a mathematician, I'm studying computer science and thought this would be a great moment to ...
- 413
18
votes
4
answers
7k
views
Looking to understand the rationale for money denomination
Money is typically denominated in a way that allows for a greedy algorithm when computing a given amount $s$ as a sum of denominations $d_i$ of coins or bills:
$$
s = \sum_{i=1}^k n_i d_i\quad\text{...
- 484
9
votes
1
answer
5k
views
On problems of coins totaling to a given amount
I don't know the proper terms to type into Google, so please pardon me for asking here first.
While jingling around a few coins, I realized that one nice puzzle might be to figure out which $n$ or so ...
user7055
15
votes
5
answers
14k
views
Algorithm for generating integer partitions up to a certain maximum length
I'm looking for a fast algorithm for generating all the partitions of an integer up to a certain maximum length; ideally, I don't want to have to generate all of them and then discard the ones that ...
- 757
5
votes
2
answers
2k
views
Generating a Eulerian circuit of a complete graph with constant memory
(this question is about trying to use some combinatorics to simplify an algorithm and save memory)
Let $K_{2n+1}$ be a complete undirected graph on $2n+1$ vertices.
I would like to generate a Eulerian ...
- 3,315
7
votes
1
answer
385
views
How to check if a polytope is a smooth Fano polytope?
Question:
We say that a convex lattice polytope $P\subset \mathbb{R}^d$ is a smooth Fano polytope if:
The origin is contained in the interior of $P$
The vertices of every facet of $P$ are a $\...
- 1,017
3
votes
1
answer
2k
views
Looking for an algorithm for grouping based on preferences
I am looking for an algorithm that "describes" the following situation:
15 - 22 people are combined into groups of 4 or 5 based upon stated preferences of who they wish to be grouped with. Each ...
jjj
3
votes
3
answers
6k
views
What are the prerequisites for combinatorics?
I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
- 55
2
votes
1
answer
339
views
Finding a Pattern Between Latin Squares
I manually arranged two complete latin squares from ordered pairs of 4 and 6 like so:
...
- 81
6
votes
1
answer
663
views
Balancing a Latin Square
I'm searching for an algorithm that forms a balanced (or quasi-complete) latin square, in which every element is a horizontal neighbor to every other element exactly twice, and a vertical neighbor to ...
- 81
9
votes
3
answers
9k
views
How can I (algorithmically) count the number of ways n m-sided dice can add up to a given number?
I am trying to identify the general case algorithm for counting the different ways dice can add to a given number. For instance, there are six ways to roll a seven with two 6-dice.
I've spent quite ...
- 557
4
votes
6
answers
5k
views
Finding the Heavy Coin by weighing twice
Suppose you have $100$ coins. $96$ of them are heavy and $4$ of them are light. Nothing is known regarding the proportion of their weights. You want to find at least one genuine (heavy) coin. You are ...
anonymous
12
votes
1
answer
831
views
Split up $n \in \mathbb{N}$ into sum of naturals with maximum LCM
Question:
Given some natural number, we can of course split it up into various sums of other naturals (e.g. $7 = 6 + 1 = 1 + 4 + 2 = \ldots$)
More precisely, for $n \in \mathbb{N}$, we can a find ...
- 2,624
4
votes
3
answers
302
views
Can this algorithm on removing $1$'s from a $(0,1)$-matrix fail?
Let us be given a $n\times n$ matrix containing only zeros and ones.Now, the goal is to remove some 'ones' from the matrix (i.e. replace them with zeros) so that in each row and each column there is ...
- 448
6
votes
5
answers
2k
views
Least wasteful use of stamps to achieve a given postage
You have sheets of $42$-cent stamps and
$29$-cent stamps, but you need at least
$\$3.20$ to mail a package. What is the
least amount you can make with the $42$-
and $29$-cent stamps that is ...
- 36.6k
16
votes
4
answers
5k
views
Is there a closed-form equation for $n!$? If not, why not?
I know that the Fibonacci sequence can be described via the Binet's formula.
However, I was wondering if there was a similar formula for $n!$.
Is this possible? If not, why not?
- 3,561