All Questions
Tagged with combinatorics algorithms
1,045
questions
2
votes
0
answers
63
views
A (simple?) optimization question
I am looking for a way to optimize the function $f$, defined below.
First, fix some positive integer $k$ and let $c_1$ and $c_2$ be vectors in $\mathbb{R}^n$. Let $g$ be an increasing concave function ...
- 578
3
votes
1
answer
118
views
Help identify this pairing function
I'm organising the natural numbers in columns like this, based on the number of $1$ bits contained in the binary expansion:
1
11
111
1111
11111
111111
1111111
11111111
10
101
1011
10111
101111
...
- 267
0
votes
1
answer
63
views
Determining all possible values of $n$ in terms of $x$ of the following tree.
Let $T$ be a maximal heap tree. Let $T$ hold the integers $1$ to $n$ as its nodes without duplicates. Let $x$ be a child of the root. What are the possible values that $n$ could take, in terms of $x$?
...
- 1
1
vote
1
answer
396
views
Find minimum moves to transform one number to another
Suppose we are given two positive integers, $a$ and $b$. Each move we are allowed to divide $a$ by 2 (but only if $a$ is even), multiply $a$ by 2, or add 1 to $a$. How many moves does it take to ...
- 173
1
vote
2
answers
71
views
Looking for an algorithm
I have a very long "list" of numbers ( maybe thousands ) which may be grouped, by sum into "n" groups. The number of groups and values are given. For example:
List of numbers: [1, ...
3
votes
1
answer
119
views
When will the algorithm stop. While $a>0$, do if $a<b$ then $(a,b)\rightarrow (2a,b-a)$ else $(a,b)\rightarrow (a-b,2b)$
I came to this question in the Problem Solving Strategies.
We start with the state $(a,b)$ where $a,b$ are positive integers. To this initial sate we apply the following algoritm
While $a>0$, do if ...
- 31
3
votes
1
answer
93
views
Is there an algorithm to generate size $n$ mutually orthogonal latin squares for $n \neq 2, 6$?
Is there an algorithm to generate size $n$ mutually orthogonal latin squares for $n \neq 2, 6$?
For reference, I've been scanning several texts on combinatorics (Knuth's "The Art of Computer ...
- 295
1
vote
1
answer
429
views
Number of permutations following given order
I have $n$ numbers and ordered sets $s_i$ of some of these numbers, I need to calculate the number of all the possible permutations of the $n$ numbers respecting the orders in the sets $s_i$. I found ...
- 111
4
votes
2
answers
487
views
Coloring triangles of triangulations in $\mathbb{R}^2$ with permutations, s. t. opposing vertices get the same number
I wonder if it is always possible and if there is a known algorithm for the following problem:
Given:
A triangulation $\mathcal{K}$ of a domain $\Omega \subseteq \mathbb{R}^2$ with Lipschitz boundary
...
- 1,284
1
vote
0
answers
54
views
Enumerating subsets of a finite set satisfying some disjoint union conditions
Take a finite set $A=\{1,...,n\}$, and consider subsets $A_1,...,A_m$ of $A$ of fixed cardinalities $a_1,...,a_m\in \mathbb{Z}_{>0}$, subject to a few conditions of the form $A_{i_0}=A_{i_1}\sqcup ...
- 1,881
2
votes
1
answer
77
views
Choosing a random subset (algorithmically) that has specified intersections with other given subsets
I am given
a finite set $X$,
$n$ subsets $X_1,...,X_n\subseteq X$,
$n$ integers $k_1,...,k_n\ge 0$, and
a number $K\ge 0$.
My goal is to choose a subset $Y\subseteq X$ with $|Y|=K$ and $|Y\cap X_i|\...
- 995
1
vote
0
answers
294
views
Algorithm to find maximum sum over weighted overlapping intervals
Suppose we are given n open intervals $(a_1, b_1), ..., (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. Define a "good subset" of intervals to be a subset of those $...
- 173
3
votes
0
answers
142
views
Number of rounds required to decide a "more swiss" competition given P players and L lives
In a regular Swiss tournament, as described in a previous post (How many rounds are required in a "Swiss tournament sorting algorithm"?), all players stay in the competition until the last ...
- 39
1
vote
2
answers
177
views
proof of diamond lemma
I am trying to prove the diamond lemma: Suppose we have two elementary cancellations of a word
$w$
then there exists some $w'$ such that there are (possibly trivial) cancellations
The diamond lemma,
...
- 39
1
vote
1
answer
366
views
Given an integer base 10, is there a known way of calculating how many 1s and 0s it has in binary without counting?
Example
Given the number $12045_{10}$,
how many 1s does it have in its binary representation?
how many 0s does it have in its binary representation?
Question
Is there a way of doing this that is ...
- 4,124
3
votes
0
answers
71
views
Detect randomness: How to calculate this combinatorics formula
I read this question about detecting whether a file/partition is encrypted. That got me thinking and I came up with a function that takes a file as input and gives a number between 0 and 1 as output. ...
- 2,895
1
vote
0
answers
35
views
Approximate estimation of number of occurrences using hash functions
Let $h: U \to \{0, \dots, M-1\}$ be a universal hash function.
Let $C$ be a counter of size $M$, initially $C[i] = 0$ for $i \in \{0, \dots, M-1\}$
Define $\operatorname{update}(x): C[h(x)] = C[h(x)] +...
- 11
3
votes
2
answers
1k
views
Algorithm to generate all combinations of list of sets with up to one element per set
For a given list of sets where the elements of the sets do not share any elements between the sets I want to compute all possible combinations where a combination can have up to one element per set. ...
- 803
1
vote
1
answer
73
views
Trivial approximation ratio of $n/2$ for 2-Opt for TSP
I recently read that the 2-Opt algorithm for the TSP yielded an approximation ratio of $n/2$ by trivial reasons. However, there was neither proof nor further context provided and I am curious how this ...
- 177
1
vote
0
answers
59
views
Is there a general term formula for 3 queens problem?
The specific question description is: Put 3 queens on a chessboard of M columns and N rows, how to determine the number of ways that no two of them are in attacking positions?
Note that M is not ...
- 11
1
vote
0
answers
39
views
Count the Number of Positive Integer Solutions to $\prod_{i=1}^{k}x_i\le N$
Given a fixed integer $k$ and a large positive integer $N$, I'd like to count the number of positive integer solutions to the equation $\prod_{i=1}^{k}x_i\le N$ in sublinear time.
Note that when $k=2$,...
- 1,586
1
vote
1
answer
163
views
Algorithms to check Pattern Avoidance Permutations
My question is the following: Given two permutations $\pi \in S_{n}$ and $\mu \in S_{k}$, decide whether $\pi$ is $\mu$-avoiding or not.
I think the formal definition is quite hard to write in the ...
- 108
2
votes
1
answer
510
views
(Upper bound on) Tree width of an $n \times n$ grid graph
Given any $n \geq 1$ consider the $n \times n$ grid graph.
For example, for $n = 3$, this looks like:
$$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&...
- 21
3
votes
1
answer
105
views
Show that a minimal solution has degree at most 2
Given a graph $G=(V,E)$, and a set $T\subseteq V$ of terminals, we say that $S \subseteq V\setminus T$ is feasible if $G[T\cup S]$ is connected.
In other words, a feasible solution is a set of non-...
- 578
3
votes
1
answer
410
views
How to find a set of combinations of 5 that cover all the combinations of 3 once?
I have a set of n numbers (e.g. 1 to n). For the sake of clarity, in the remaining I will use n = 10.
From these 10 numbers there is $\binom{10}{3} = 120$ combinations of 3, for instance (1, 3, 5), (3,...
- 33
0
votes
0
answers
67
views
Greedy algorithm for variation of bin packing
Consider the bin packing problem where an input array of weights have to be packed in the minimum number of bins possible. Consider the two following restrictions. First, for any bin, a heavier weight ...
- 127
3
votes
0
answers
115
views
Triangulating a graph of nCr, r=3?
Given (non-repeating, order does not matter) combinations nCr, where r=3, and n is [dozens...hundreds]:
Is it always possible to construct a planar 2D graph of connected triangles on a uniform grid, ...
- 31
1
vote
0
answers
55
views
How do I find unique rearrangements when given items & the item distributions?
I'm not sure what this type of question is called, but this what I'm trying to solve:
I own
3 hats
1 hat is red
2 hats are blue
4 shirts
1 shirt is red
1 shirt is blue
2 shirts are green
5 pairs ...
- 19
2
votes
0
answers
854
views
Find all minimal cycles (Graph Theory)
I am facing the following problem, let $G(V, E)$ be an unweighted planar graph, find all the minimal cycles of $G$.
[UPDATE 1] A minimal cycle $c$ of $G$ is a cycle in $G$ such that there is no edge ...
2
votes
0
answers
106
views
A question about Fomin's local rules for growth diagrams
Let $w\in S_n$. Define the growth diagram of $w$ as follows: Start by an array of $n\times n$ squares, with an $X$ in the i'th column and row $w(i)$ from bottom. Then we obtain $(n+1)^2$ vertices (the ...
- 3,052
5
votes
0
answers
292
views
Faster Algorithm for counting non-negative tripple(a, b, c) satisfied (a + b + c <= S) and (a * b * c <= T) and subproblem divisor summatory function
Statement
This problem
Code
Used this Paper
Given $S, T (0 \leq S, T \leq 10^{18})$
I need to count the number of tuple $(a, b, c)$ satisfied $(\min(a, b, c) \geq 0)$ and $(a + b + c \leq S)$ and $(a ...
- 85
3
votes
2
answers
106
views
select sequence without "ABCD"
There are an infinite number of coupons bearing one of the letters A,B,C,D. Find the number of ways for selecting $10$ of these coupons so that there shouldn't be sequence of "ABCD", which ...
- 281
2
votes
1
answer
274
views
Partition the edges of a bipartite graph into perfect $b$-matchings
Any $r$-regular bipartite graph can be partitioned into $r$ disjoint perfect matchings.
I want to know whether a version of this extends to perfect $b$-matchings.
Suppose we have a bipartite graph $G =...
- 578
3
votes
2
answers
147
views
Select five vectors that upon undergoing elementwise multiplication are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
- 31
0
votes
0
answers
161
views
NP completeness of a variant of assignment problem
I have the following variant of assignment problem:
Suppose we have $m$ machines and $n$ jobs. Each machine is capable of doing a subset of jobs and each machine $i$ has capacity $C_i$. Each job $j$ ...
- 422
0
votes
1
answer
544
views
Algorithm to find the largest intersection of sets
Edit:
I've tried to be more precise, clear up my examples, and to clarify the problem. Hopefully the problem makes more sense now.
The problem is this:
I have a list of sets $$S_1, S_2,... S_N$$ ...
- 171
2
votes
0
answers
45
views
Does submodularity provide guarantees for "backwards" greedy elimination algorithms?
The submodularity condition, besides having a definition that "makes sense," is also nice because it offers guarantees for the maximum coverage problem (as well as the related set cover ...
- 390
1
vote
0
answers
108
views
Generate a new planar graph via edge subdivision and edge addition
Given a simple planar graph $G$, let $G'$ be a subdivision of $G$. Examples of $G$ and $G'$ are shown below:
The graph $G'$ is clearly planar. Let $W = \{w_{i,j} : (v_i, v_j) \in E(G)\}$ be the set ...
- 250
2
votes
1
answer
103
views
Number of ways to form a binary number of length N containing n ones, given that each bit is selected from one of N sets of 4 arbitrary bits.
This is a combinatorial problem encountered in calculating the relative occurrence of certain outputs produced by an algorithm based loosely on genetics, in order to predict the probability that a ...
- 21
0
votes
0
answers
57
views
Combinatorial problem about finding optimal subsets of numbers forming pairs
I am trying to solve a combinatorial problem computationally (currently using python) and cannot find a good algorithmic solution for it.
I have n individual numbers (eg. 0,1,2,3,4,5). These numbers ...
2
votes
0
answers
65
views
Count unique prime numbers
Suppose I have a large collection of prime numbers $P$, with size $n$.
There are duplicates in $P$, my goal is to count how many distinct prime numbers there are in $P$.
Since $P$ is large, it might ...
- 1,271
0
votes
0
answers
148
views
Algorithm to find all possible combinations of a group of LEGOs?
The other day I walked by a LEGO store in The Mall I was shopping at, and it brought back some memories. Then that got me thinking: There's got to be some mathematical algorithm to find all the ...
- 101
1
vote
0
answers
149
views
Finding conditions for certain intersections to be nonempty
During my research in algorithms I came up with the following problem which I didn't manage to solve after weeks of efforts.
Let ${\cal A}={A_1,\dots\,A_n}$ be a set of $n$ finite sets, similarly ${\...
- 804
1
vote
0
answers
205
views
Find the number of compatibility relations of [n] containing k maximal irredundant set C n,k
Let [n] denote the set of n elements {1, 2, ... , n}. A relation on the set [n] is a subset of the Cartesian product [n] × [n]. Equivalence relations are relations that satisfy self-reflexivity, ...
- 11
0
votes
1
answer
64
views
Formulate counting problem using polynomial multiplication
Suppose I have some weights: two 2g weights, two 3g weights, and one 4g weight.
I can find all possible weights I can add up to by the following polynomial multiplication:
$(1+x^2+x^4)(1+x^3+x^6)(1+x^...
- 175
1
vote
1
answer
639
views
Change making problem - Pearson algorithm to check the optimality of greedy solution
This is a question regarding the common version of the Change making problem, which is:
"how can a given amount of money be made with the least number of coins of given denominations (we have ...
- 113
12
votes
1
answer
331
views
Searching radioactive balls
There are $n$ balls, and $m$ of them are radioactive. You can test any set of balls and find out whether there is at least one radioactive ball in this set (but it is impossible to know how many of ...
- 15.7k
5
votes
0
answers
45
views
Number of lines of $3$ points in an arrangement of points and lines
It is well known that a finite set of $n$ points cannot form more than
$$\bigg\lfloor \frac{n(n-3)}{6} \bigg\rfloor+1 $$
lines that include $3$ points. Would this result still hold if we assume that ...
user920720
0
votes
1
answer
135
views
General interval scheduling
We shall start with below problem.
Problem: Given a list of classes for student to subscribe for a week:
Math: Monday 1pm-3pm; Wednesday 4pm-6pm
(That means Math class learn from 1pm to 3pm on Monday ...
- 55
0
votes
0
answers
58
views
How to calculate the different combinations of an N×M grid with 3-valid values [duplicate]
I have 3 valid values: a,b,c I can insert them in a N×3 grid in such a way that no row or column contains cells that are the same values. How can I calculate the number of valid patterns that can be ...
- 207