All Questions
Tagged with algorithms combinatorics
1,046
questions
0
votes
0
answers
24
views
Counting Paths in the XY Plane (Discrete math) [duplicate]
I need help with the following mathematical task:
A particle moves in the xy-plane according to the following rules:
U: (m, n) → (m+1, n+1)
L: (m, n) → (m+1, n-1)
where m and n are integers. I need ...
- 39
3
votes
1
answer
99
views
Expected Length of Maximum Decreasing Subsequences in Random Sequences
Given $ n $ distinct numbers that are randomly shuffled to form a sequence $ A = [a_1, a_2, \ldots, a_n] $, we select the largest number $ x_1 $ from the sequence. Subsequently, we pick the largest ...
- 1,231
2
votes
2
answers
84
views
Analytic solution for number of paths with length $k$ on an $n \times n$ Chessboard allowing Self-Intersecting?
Consider an $n \times n$ chessboard where the journey begins at the bottom-left corner $(1, 1)$ and concludes at the top-right corner $(n, n)$. How many distinct paths are available that necessitate ...
- 1,231
5
votes
0
answers
486
views
How many Color Balanced sets can you make with n colors?
You have n colors and you make nonempty sets from them. A set of these color sets is color balanced if each color is in the same number of the color sets.
Ex. For <...
- 51
1
vote
1
answer
322
views
Converting Undirected Graphs to a Tree While Preserving Edge Information
I'm working on a problem where I need to convert an undirected and unweighted graph with cycles into a tree while preserving the edge information (all the edges from the graph are preserved in the ...
- 11
1
vote
2
answers
73
views
When can a deck be shuffled by shuffling fixed subdecks?
Suppose I want to shuffle a deck of $n$ cards, but I have a problem -- for some reason, I am only able to shuffle at most $n-1$ cards at a time at some fixed indices. For example, if $n=5$, I could ...
- 685
4
votes
1
answer
285
views
Printing neatly
I'm working on the following problem (which is not my actual question)
Consider the problem of neatly printing a paragraph with a monospaced font (all
characters having the same width). The input ...
- 910
0
votes
1
answer
46
views
Last step of an intense algorithm requiring efficiency: A closed form for $\sum_{s=2}^{\lfloor\frac{T}{2}\rfloor}{2s-1 \choose s-2}{T \choose T-2s}$?
I'm working on an algorithmic problem for HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler106/problem
The broad overview of the problem is finding how many evenly-sized ...
- 11
3
votes
1
answer
119
views
Social golfer problem with additional requirement
I need to write a program that sorts people into groups.
To give a little context: The aim of the program is to create an equitable distribution of tasks and people for a school trip. Every day the ...
2
votes
1
answer
132
views
Optimal strategy in number guessing game?
Consider the following game.
Two players each create a passcode using the digits 0-9 four times with repetition allowed.
The two take turns asking a yes or no question about the opponent's passcode. ...
- 21
0
votes
1
answer
130
views
Generalised Rubik's cube algorithm to go from any valid cube state A to any valid cube state B.
For a $3 \times 3 \times 3$ cube, there are several known algorithms to go from any valid state of the cube to the solved state, $S$, of the cube (same color on each side).
How about a more general ...
- 79
1
vote
1
answer
180
views
Closed formula for recursive algorithm
The $treeSize(n)$ function is designed to calculate the number
of leaf nodes in a spherical tree structure. The tree is generated
by recursively exploring points in three-dimensional, discrete space,
...
- 29
1
vote
0
answers
30
views
Is it always possible to create a minimum depth tree where tree nodes are unique and have a 'choice'?
This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:...
- 141
0
votes
0
answers
76
views
Deranged generous gift giving in the limit
I was writing a routine for a game and stumbled upon some algorithm issues and a theoretical question about it. Here I'm mostly concerned with the latter, which may be phrased as a sort of graph ...
- 12.3k
1
vote
1
answer
55
views
All cliques of a graph
Given an arbitrary undirected graph $G$ with $n$ vertices, I am interested in counting the number of cliques.
(For example, the number of cliques of a complete graph $K_n$ is trivially $2^n-1$;the ...
- 203