All Questions
Tagged with combinatorics algorithms
1,044
questions
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 ...
1
vote
0
answers
45
views
Counting the deduplicated list
You are given $2n$ positive integers $x_i, d_i$ ($1 \leq i \leq n$). Let $l := [x_1, 2x_1, ..., d_1x_1, x_2, 2x_2, ..., d_2x_2, ..., x_n, 2x_n, ..., d_nx_n]$. Let $s = set(l)$, i.e., the set by ...
- 1,008
0
votes
1
answer
223
views
Algorithm to compute number of combinations
I have to compute (m+n)!/(m!)(n!) where m>=n.
Due to overflow constraints, I cannot calculate (m+n)! as it might exceed size of variable (int). To overcome this difficulty, one solution is to do ...
- 345
3
votes
1
answer
80
views
Block Game: Dynamic vs Greedy approach
This is a question from an old exam in a Combinatorial Algorithms class, I am reviewing for a midterm. I understand the game but I don't understand the "optimal" approach, ie. implementing a ...
- 31
5
votes
0
answers
56
views
Bracelet isomorphism algorithms
I feel like the problem should have been studied, but I wasn't able to find anything precise.
Given two bracelets with $n$ beads and $m$ colors, given that the multiplicity of each color is the same, ...
- 2,103
0
votes
0
answers
46
views
Colored hypercubes isomorphism
I would like to extend the method to verify isomorphism between cubes with colored faces in this answer to $4$-cubes (tesseracts) with colored faces ($2$-faces), allowing rotations and reflections, ...
- 2,103
2
votes
2
answers
110
views
Counting integers $n \leq x$ such that $rad(n)=r$
Let $r$ be the largest square-free integer that divides $n$. Then $$r = \operatorname{rad}(n)=\prod_{\substack{p\mid n\\p\text{ prime}}}p$$ $r$ is called the "radical" of $n$, or the square-...
- 1,022
1
vote
2
answers
105
views
Bin packing with load fairness across the bins
The bin pack problem denotes the process of assigning a set of n items into a minimal number of bins of capacity c. It can be simply formulated as an ILP as per the below description:
My question is :...
- 131
3
votes
0
answers
99
views
What set of angles uniquely defines a convex quadrilateral?
I am trying to characterize the set of angles in a (convex) quadrilateral that distinguishes it from any other quadrilateral that is not similar to it. Such a set will be said to uniquely define a ...
- 1,022
1
vote
0
answers
73
views
How to quickly eyeball maximum sum subarray?
Given an integer array, I want to find the continuous subarray (containing at least one number) which has the largest sum. There are some algorithmic solutions to this here: https://en.wikipedia.org/...
- 1,415
1
vote
2
answers
66
views
Finding perfect matchings
Given a connected graph $G$, do you have an idea how to calculate the amount of perfect matchings
this graph has (given at least one exists)? I dont worry about the calculation being efficient in any ...
- 13
0
votes
0
answers
277
views
Count the integers that conform another integer
I have to count all the integers than conform to integer A.
We say that integer B conforms to integer A if, in all positions where A has bits set to 1, B has corresponding bits set to 1.
If I have a ...
- 378
1
vote
0
answers
61
views
Counting number of length k non-overlapping paths on an $n \times n$ grid
Suppose we have a square grid of size $n \times n$, where each node is connected to its immediate neighbors (up, down, left, right, and the four diagonals when they exist). I'd like to count all of ...
3
votes
2
answers
87
views
Dividing distinguishable cards into distinguishable hands where some hands cannot contain some cards
I am making a computer program to play cards, for this algorithm to work I need to deal cards out randomly.
However, I know that some people cannot have some cards due to the rules of the card game.
...
- 2,305
0
votes
0
answers
68
views
Finding the general formula for the last standing soldier
Suppose there are 'n' soldiers standing in a circle who have decided to kill each other (just because they don't want to surrender to the opposition).
Lets say they are denoted from a1 to an in the ...
- 1
0
votes
0
answers
109
views
Binary sequences of length $N$ including all numbers upto $N$ [duplicate]
Consider numbers $n$ and $N = 2^n$ and define a binary sequence $b = [b_0,\dots,b_{N-1}]$, $b_i \in \{0,1\}$, to be complete or to include all numbers upto $N$ when for each number $0 \leq i < N$ ...
- 18.2k
-1
votes
1
answer
59
views
Is there an efficient way to loop through this problem? [closed]
So I saw this very interesting problem. Let's say you have a length of 2, and a base length of 5
l = 2, b = 5
this would be translated to :
...
- 9
1
vote
1
answer
62
views
How to discover a recursive relation in a data set?
For a set of data, $x(n)$, where $n = 1, 2, 3, ...$, we know there are some kind of recursive relations among those data, $x(n)$ somehow depends on previous data $x(n-1), x(n-2), ...x(1)$, but we do ...
- 553
0
votes
4
answers
195
views
Get all the methods to break 100% into certain number of parts?
Being straight about the question, for a program I'm writing, I need to divide 100% into 5 parts. In my program, percentages incremented/decremented by 10%. So I can express my requirement in the ...
- 103
2
votes
1
answer
57
views
Computing subset reciprocals, $\frac1{a+b}+\frac1{a+c}+\frac1{b+c}$
I'm interested in computing the sum
$$
H_k = \sum_{S\subseteq T, |S|=k} \frac{1}{\sum_{s\in S} s},
$$
where $T$ is some set of integers.
Obviously this can be done in $|T|^k$ time, enumerating all ...
- 4,814
1
vote
0
answers
30
views
Can we find a proper $\phi$ so that maps each interval to its center?
For a compact interval $[0,1]$, we divide it into $N^{1/3}$ subintervals with length $N^{-1/3}$. Define a map $\phi: [0,1]\mapsto [0,1]$ maps each subintervals to its center.
For example, let $X\sim ...
- 1,520
0
votes
1
answer
266
views
Algorithm verification: Get all the combinations of possible words
I wanted to know if the algorithm that i wrotte just below in python is correct.
My goal is to find an algorithm that print/find all the possible combinaison of words that can be done using the ...
- 805