All Questions
Tagged with combinatorics algorithms
1,044
questions
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