All Questions
Tagged with combinatorics algorithms
1,045
questions
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
0
votes
1
answer
140
views
On a Codeforces combinatorics problem, from $O(m^2n)$ to $O(n \times \min(m, n))$? [Codeton 5 Problem G]
Problem link: https://codeforces.com/contest/1842/problem/G
Brief explaination:
Given a positive integer array $a$ ($1$-indexed) of length $n$ ($1 \leq n \leq 5000$) and a positive integer $v$, ...
- 1,008
0
votes
1
answer
40
views
Is the stable marriage problem defined for $0$ people?
When proving properties of algorithms which are supposed to solve the stable marriage problem, I find myself unable to prove them sometimes in the case of there being $0$ things to pair with each ...
- 3,029
2
votes
0
answers
47
views
How many ways are there to remove $2 \times 2$ rooms from $n \times m$ bounded grid by building walls
On an $n\times m$ grid, a room is considered to be a $2\times 2$ subgrid such that there isn't a wall between any $2$ cells in that subgrid that share an edge.
Initially, there are no walls in the ...
- 93
1
vote
1
answer
49
views
Optimizing Uniform Distribution of Attributes in Item Selection: A Combinatorial Problem
I am an engineer with limited mathematical proficiency, and I have encountered a quite challenging mathematical problem during my work. The problem as a whole is intricate, but I will try my best to ...
- 13
0
votes
1
answer
50
views
Converting between shortest path problems
Given a weighted digraph $G$, and collections of vertices $R, S \subset
V$ , consider the problem of finding a shortest length path joining
a vertex $r\in R$ to a vertex $s\in S$. Reduce this to the ...
0
votes
0
answers
163
views
1v1v1 Round Robin Schedule; How many possibilities? How to generate?
I am trying to create a round-robin bracket generator for a game where each match contains three teams competing against each other (1v1v1) given the teams, rounds, and rooms in Python. I don't ...
- 1
1
vote
0
answers
24
views
Number of Unique Groupings of Students Without Repeating Group Members [duplicate]
I'm working on a problem related to grouping students for a series of activities. The problem is as follows:
Suppose I have $m$ students, and I want to divide them into groups of size $n$ such that ...
- 11
1
vote
0
answers
95
views
Building a primitive programming language for solving math olympiad problem(TSTST 2015)
There was a 6th problem on USA TSTST 2015:
A Nim-style game is defined as follows. Two positive integers $k$ and
$n$ are specified, along with a finite set $S$ of $k$-tuples of
integers (not ...
- 61
2
votes
0
answers
38
views
Partition n objects into k groups with required repeats and pairwise restrictions
Is there a way to partition $ n $ objects into $ k $ groups, with repeats, with the following requirements:
each object should appear in at least $ m $ groups
no two objects can be grouped together ...
- 21
1
vote
0
answers
173
views
Number of guesses binary search would take to reach number
Essentially, given a start of an inclusive integer range $s$, an end of the range $f$ such that $s \le f$, and an integer $n$ such that $s \le n \le f$, how many guesses would binary search take to ...
- 240
2
votes
1
answer
139
views
HMMT 2014 #9, how many times has Lucky performed the procedure when there are 20 tails-up coins?
There is a heads up coin on every integer of the number line. Lucky is initially standing on the zero
point of the number line facing in the positive direction. Lucky performs the following procedure: ...
- 2,031
0
votes
1
answer
32
views
Problem on correspondence between one number and an array
Consider an array of length 100 which contains 20 many 1, 20 many 2 $\&$ 60 many 3. It is clear number of such array is $N=\dbinom{100}{20,20,60}$. I want to find a one to one correspondence ...
- 109
1
vote
1
answer
61
views
Permutations drawn from different intersecting sets
I'm looking to create non-repeating permutations of length $N$ drawn from $N$ finite and possibly intersecting sets. Specifically, element $i$ is always drawn from set $S_i$. A simple example, if:
$...
- 13
0
votes
1
answer
65
views
Finding $n$ disjoint paths in a graph which minimize number of vertices.
Let $G$ be a graph and fix $A,B$ two vertices. I want to find $n$ disjoint paths $P_1,...,P_n$ from $A$ to $B$ such that the total number of vertices $\# V(\cup_{i=1}^n P_i)$ is minimized. Disjoint ...
- 1,815
1
vote
1
answer
149
views
How to assign tasks to a set of machines, given that the more tasks you assign to a machine the slower they will run? Bin covering with merging bins?
Intro
I need to design an algorithm that will distribute a known set of tasks with a known RAM requirement to a known set of machines with known RAM capacities. The tasks require a certain amount of ...
- 113
3
votes
0
answers
88
views
Maximum number of flips to make all row sums and column sums non-negative
(An extension of: Making all row sums and column sums non-negative by a sequence of moves )
You choose integers to be written on each cell of an $m \times n$ grid. At each step, you are allowed to ...
- 31
1
vote
2
answers
71
views
Marching cubes generates surface triangles. How to adapt it to generate tetrahedra throughout the volume of a 3D model?
Background
There is a source code that generates surface triangles. The isosurface is generated for the iso-value of 0. The source code uses a table for ...
- 271
1
vote
0
answers
32
views
Given $M$ biased coins, what's the probability of drawing $K$ heads? Can we compute it efficiently? [duplicate]
We have $M$ coins, with biases $p_1,\dots,p_M$. I draw all of them and count the total number of heads. What's the probability of observing $K$ heads?
I realize the solution can be formally written as ...
- 6,771
2
votes
0
answers
84
views
How to solve this algorithmic task in Python?
I am trying to solve this task :
There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. second data on ...
- 139
1
vote
0
answers
59
views
How to calculate the number of set partitions of an arbitrary set? [duplicate]
Pre-Amble
I would like to rephrase the question
PREVIOUS INSTANCE OF THIS QUESTION ( Was closed due to an alleged duplicity ).
Considering sets of four elements we can consider sets of the following ...
- 2,789
3
votes
1
answer
115
views
From three integers, choose any two and replace one of them with the two numbers' mean. Show that we can obtain equal integers.
Let $a, b, c$ be three distinct positive integer numbers on a whiteboard. At each step, I choose two of them and I replace one of the two numbers with their arithmetic mean.
For example: I choose $a, ...
- 1,758
1
vote
0
answers
46
views
How to solve this specific combinatorial optimization task?
I have problems with my combinatorial optimization task:
Different teams of the same company may have employees in different cities. If employees have the same position, we can change their teams (we ...
- 139
0
votes
1
answer
102
views
Subarray Sum Equals K - If the same prefix sum is encountered why does it follow 1,3,7,15,31 pattern?
This is an interesting property I have noticed in the problem:
Subarray Sum Equals K
The basic algorithm is as follows:
You start with calculating the prefix (running sum).
You check if the ...
- 1,035
2
votes
1
answer
254
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [closed]
We define the set S as $\{(s_1, f_1), (s_2, f_2), ..., (s_i, f_i)\}$, where each $f_i$ is the frequency that $s_i$ is repeated in the multiset T. How many ways can we partition the multiset T into ...
3
votes
1
answer
57
views
Composition (Combinatorics) with upper bounds
Problem
There are $n$ balls numbered from 1 to $n$.
We uniformly sample $k$ balls without replacement.
Let $x$ be the number of sampled balls in a range 1..$m$.
I would like to efficiently sample $x$ ...
- 33
1
vote
1
answer
219
views
How to modify the hungarian algorithm for bipartite graphs with multiple edges with some already imposed connections
The Hungarian algorithm can be seen to take as input a complete weighted bipartite graph and outputs an optimal matching, maximising or minimising the sum of all the edges. Crucially, this algorithm ...
- 833
0
votes
1
answer
425
views
Climbing Stairs - Why is the number of ways I can reach a particular step the sum of the previous and second prevoius steps?
There is a famous coding question which goes like :
...
- 1,035
1
vote
0
answers
235
views
Counting cliques in graph
In graph theory, a clique is an undirected graph in which any pair of distinct vertices is connected by an edge. The clique number of an undirected graph $G$ is defined to be the maximal size of a ...
- 11
0
votes
0
answers
51
views
Difficulty in decoding the Prufer code.
I was looking at the proof of the following result:
Let $n\geq 2$,the number of spanning trees in the complete graph $K_n$ is $n^{n-2}$.
The proof uses a bijection between $T$ ,the set of all ...
- 3,619
0
votes
0
answers
32
views
Effectively solve optimization problem in this system?
The system :
Given
$2$ sets $I,J$ such that $I\cap J = \emptyset , \#I = \#J$
a time-dependent function $c : \mathbb{R}_{\ge 0} \times I \times J \to \mathbb{R}_{\ge 0}$ .
Consider a system that ...
- 910
0
votes
0
answers
19
views
Is there a formula to find a permutation from a given rank?
Observing, for example, a set of permutations from 4 choose 2:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]
Does such a formula exist to go from a permutation's rank to the values of it's permutation (...
- 1
1
vote
1
answer
142
views
Sum of Product of Min, which is related to the Pentagonal number theorem.
The title looks a little bit weird. The problem comes from the Atcoder Beginner Contest 279-Ex: Sum of Prod of Min:
Problem: You are given positive integers $n$ and $m$. Here, it is guaranteed that $n ...
- 1,008
0
votes
0
answers
49
views
Conditions for a sorted partition of the edges of $K_n$ to generate a total order of the vertices
Given a complete undirected graph $K_n$, it's given a refinement algorithm that builds, at iteration $t$, a sorted partition $E^t$ of the edges and a sorted partition $V^t$ of the vertices by refining ...
- 451
1
vote
0
answers
41
views
Algorithm for sorting by equivalence relation
I hope the thread title isn't too strange, but I don't know better.
My question seems a quite simple one.
Having a set of objects I'm interested in the subsets that are pairwise equal.
Example:
A set ...
- 21
0
votes
0
answers
21
views
Formula for succesively computing and assigning score value to quiz questions in my program
Hello please forgive my question is not suited for this place, I am not very good at math and I need help.
I have a computer program which is a quiz. As per my plan, each individual quiz question ...
0
votes
1
answer
71
views
Identifying weak partitions
Recently a problem rose to me I'm not really sure what topic it belongs to:
The origin is a "labeling application". There are n objects (say files etc., n abt. 1e6). And there are t ...
- 21
5
votes
1
answer
293
views
Efficient way to find all polygons of the same shape within a set, regardless of position, scale, or rotation
I've got a big set of 2D polygons described as a set of points. I would like to take this set of polygons and find any that are the same shape, regardless of rotation, translation, or scale.
Each ...
- 295
7
votes
1
answer
126
views
In this checkerboard problem, is there a way to tell if any two situations are equivalent?
There is an infinite square grid chessboard with chess pieces placed on certain squares. There is at most one piece in a grid.
We can perform the following operations each time:
Split: Select a chess ...
- 71
1
vote
0
answers
38
views
Hungarian Algorithm with Constrained Number of Unique Tasks
I was wondering if there is an extension to the Hungarian algorithm (https://en.wikipedia.org/wiki/Hungarian_algorithm) in which (i) A given task may be performed by more than one agent, and (ii) ...
- 37
0
votes
1
answer
343
views
Why the "sum of permutation inversions" is a non-admissible heuristic for the 8-puzzle? [closed]
A heuristic h(N) is admissible if for every node N, 0 ≤ h(N) ≤ h∗(N) where h*(N) is the true cost to reach the goal state from N.
In my opinion, the true cost to reach the goal state from N is 21 for ...
0
votes
1
answer
42
views
Generate pseudo-random sequence of 1 and 0 so that each pairing in the sequence appears and equal number of times
Edit: As pointed out by VTand below, this is indeed not possible due to the number of pairs with 32 elements, but I'm curious about any solutions for different list lengths too.
I need to generate a ...
