Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

1
vote
1answer
19 views

Combinatorial optimization - is there a formal name for this problem?

I am looking for a formal name and an algorithmic approach to the following problem. Given is a set of services each coming with a price: {s1, 300} {s2, 400} {s3, 800} Additionally there is a ...
2
votes
1answer
33 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
1
vote
1answer
20 views

How can I efficiently find the optimal order to apply special offers to a shopping cart?

Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the ...
0
votes
0answers
15 views

Time varying handshaking problem with memory: optimal matching

I have to analyse the following problem. I have a set of users $M = [m_0,m_i,\ldots,m_n]$. Between each pair of users I there is a certain Temporal Affinity $F$ defined as $F(m_i,m_j,t_k)$ that is: ...
3
votes
2answers
127 views

Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

A test is consisted of $N$ multiple choice questions, each has $k$ possible answers. A test solution is the sequence of answers $S\in[k]^N$. Given is a black box which receives a solution as input ...
0
votes
1answer
55 views

Random uniform sampling of position restricted permutations

Is there any efficient algorithm which is able to generate nearly uniform samples of permutations in case of position restrictions? Consider $N \times N$ restriction matrices $R$, that is matrices ...
-2
votes
2answers
69 views

Undirected graph G that has 12 vertices, 66 edges and 3 connected components?

Why would it be impossible to draw an undirected graph G that has 12 vertices, with 3 connected components if G had 66 edges?
1
vote
1answer
90 views

Algorithm: Cracking the Safe

A safe is protected by a four-digit $(0-9)$ combination. The safe only considers the last four digits entered when deciding whether an input matches the passcode. For instance, if I enter the stream ...
3
votes
0answers
70 views

permutations sampling by probability matrix

I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = ...
0
votes
1answer
33 views

Is the number of nodes in an ORBDD 2n + 2?

Wikipedia says that the number of nodes in a ORBDD (Order Reduced Binary Decision Diagrams) of order $x_1 < x_2 < \dots < x_{2n}$ is $2n + 2$. But I can't find proof. Anyone?
5
votes
0answers
31 views

Upper bound on the number of hamiltonian cycles on a $n \times n $ grid graph

What is the best upper bound that is known for the number of hamiltonian cycles on a $n \times n $ grid graph? I did some searching and found that the number of hamiltonian cycles on a planar graph ...
6
votes
1answer
65 views

Algorithm to compose identity from a set of permutations

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity ...
1
vote
0answers
41 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
0answers
27 views

How many valid and unique Turing machines are there with restricted states and characters

This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of ...
6
votes
2answers
104 views

Real world applications for Steiner Tree Problem?

Are there real-world applications of the Steiner Tree Problem (STP)? I understand that VSLI chip design is a good application of the STP. Are there any other examples of real world problems that ...
1
vote
1answer
41 views

Combinatorial optimization problem - What would you call this?

I'm trying to solve an optimization problem which can be described as follows. There are four sets objects. For simplicity, let's call them : Apples Oranges Pears Lemons The sets can contain ...
3
votes
1answer
59 views

Why isn't chess an impartial game?

In Combinatorial Game Theory, a major distinction is drawn between impartial games and partisan games. To be impartial, a game must satisfy these conditions: (1) The game is finite; i.e. there is a ...
3
votes
0answers
51 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has $n$ different elements $[A_1, A_2, \ldots, A_n]$ (random order). We have a comparator $C$, but it has a probability p to ...
11
votes
2answers
297 views

Efficient algorithm to generate two diffuse, deranged permutations of a multiset at random

Background $\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak ...
-2
votes
1answer
51 views

How many ways are there to add a node to a digraph?

In a digraph with $n$ vertices, how many different ways a new vertex can be added to get the digraphs with $n$+1 vertices? Input digraph with $n$ vertices have following degree criteria : There ...
1
vote
1answer
22 views

Subset Sum algorithm, why not split by 3+?

A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of ...
0
votes
1answer
19 views

Allocating n processes to n servers, counting from the server perspective

In this question, I asked about a confusion I had counting the size of the sample space for allocation of n processes to n servers. Bangye gave a simple answer by approaching the counting problem from ...
0
votes
2answers
20 views

Number and probability of random allocations of n processes to n servers

I've been using the Stanford Algorithms (1) Coursera course, and in a description of a problem, the lecturer said that in the problem of allocating n processes to n servers at random, the sample space ...
4
votes
1answer
43 views

Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?

I've seen a few references [1], [2], [3] that say that for a Turing Machine with transition function defined by: $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}$ the number of ...
1
vote
0answers
14 views

Activity scheduling with activities that can move around

In this problem. I have a set of "activities" which can happen. Each "activity" is associated with several values: Duration: The length of time the activity takes Earliest time to start: The ...
0
votes
1answer
102 views

Minimum size of largest clique in graph

I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this: What is the minimum size of the largest clique in any graph with N ...
4
votes
1answer
46 views

Distribution of Ones in a Psuedorandom Sequence

Let S be a string in the set (0,1) produced by taking the AND of the output of two maximal length linear feedback shift registers of large period (say 128 bits). It's easy to see from the truth table ...
6
votes
1answer
51 views

Heaviest planar subgraph

Consider the following problem. Given: A complete graph with real non-negative weights on the edges. Task: Find a planar subgraph of maximum weight. ("Maximum" among all possible planar subgraphs.) ...
2
votes
1answer
114 views

How many permutations in a trainset?

If I have the following pieces to a train set: (12) Curve (4) Straight Such as this train set. I'm looking for an algorithm (to which I can write a program) that creates/lists all permutations. ...
2
votes
1answer
87 views

Computing a Sequence of People Entering and Leaving a Room

I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows. You start with an empty room and a group of n people waiting outside. At each step, ...
1
vote
2answers
150 views

How to find the Branch factor of 8 Puzzle

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that: Suppose,for example we wish to establish the ...
4
votes
2answers
72 views

Is the number of inequivalent elementary cellular automata rules really 88?

Everywhere from Wolfram's "New Kind of Science" (p. 57) to Wikipedia they say that, out of all possible 256 (=2^8) elementary cellular automata rules, 88 are inequivalent (as defined in the Wikipedia ...
6
votes
1answer
38 views

The XOR cut-set structure, and combinatorial designs

Given a graph $G(V,E)$ and a subset of vertices $T \subseteq V$, define $\mathsf{cutset}(T)$ = the set of edges connecting a vertex at $T$ with a vertex at $V\setminus T$. Our goal is to preprocess ...
2
votes
1answer
65 views

Using a binary heap to solve an equation

I have to find a solution for this equation: I have to find the set of solutions a, b, c, d for all possible combinations of values 1 <= x <= n. $a^5 + b^5 = c^5 + d ^ 5$ I first thought ...
5
votes
1answer
116 views

Fast solution for a combinatorial maximizaton problem

You are given a natural number n (n<20). We construct the set S from all binary numbers with n bits. We call two numbers "compatible" if they don't have any common substring of length n-1 ...
1
vote
1answer
179 views

Artificial intelligence - bridge and torch problem

I am doing a artificial intelligence course as part of my computer science degree. I am stuck on a question about searching. The question is a version of the Bridge and torch problem. Five people ...
0
votes
1answer
75 views

Binary digit problem?

Question: If a system has $32k$ bytes and each such byte has unique address(so $32k$ addresses), what is the smallest possible bits that can be use by every byte for the address ? All the bytes ...
1
vote
1answer
33 views

Probability of having a log(n) length monotone subsequence in a random permutation of {1,…,n}

How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$. I wish to upperbound it with $1/n$.
9
votes
2answers
123 views

Is this combinatorial optimisation problem similar to any known problem?

The problem is as follows: We have a two dimensional array/grid of numbers, each representing some "benefit" or "profit." We also have two fixed integers $w$ and $h$ (for "width" and "height".) And a ...
1
vote
1answer
30 views

Filling a matrix with the sum of conditional values

I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$. I would like to Fill a square matrix $M$ of size $N\times N$ in the following way: $$\forall i,j ...
2
votes
0answers
144 views

Constructing orthogonal latin square Parker/Knuth method

I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square. The ...
1
vote
0answers
59 views

Maximum flow problem with non-zero lower bound

Given $G = (V,E )$ a directed graph, if $ X \subseteq V $ we write $$\begin{align*} \delta ^{+}(X) &= \{ xy\in E \mid x \in X, y\in V - X \} \\ \delta ^{-}(X) &= \delta ...
1
vote
1answer
42 views

Smallest possible integer not obtained from sumset

Given a number N, and some set $A=\{a, 1\le a\le N\}$, and let $B=\{\text{every integer} \in [1,N]\}$, and $C=B\setminus A$ (Set C has all values from B not in A) What is the best way of finding the ...
13
votes
1answer
285 views

Complexity of finding binomial coefficient which equals to a number

Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding). How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m$$ ? ...
1
vote
1answer
23 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
0
votes
0answers
42 views

Is there a constant for size of disjoint clauses in 3-CNF

We are given a 3-CNF formula $\Phi$ on n variables, and a guarantee that at least $\epsilon$ fraction of $2^n$ possible assignments satisfy all clauses in $\Phi$. Now construct set $S$ of disjoint ...
0
votes
3answers
62 views

How can I keep track of the state of a sequence after rotating parts of it multiple times?

Given a sorted array 1 2 3 4 5 6 7 8 and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the ...
4
votes
1answer
57 views

Distribution of cycles length in a graph

Given a random directed Graph G: $$ G=(V,E) \\ \lvert V \rvert = n , \lvert E \rvert = k $$ where for each vertex, either: $$ d_{incoming}(v) = 1 , d_{outgoing}(v) = 1 $$ meaning - for each ...
2
votes
2answers
440 views

Efficiently enumerate all subsets of an ordered set

What's the most efficient way to enumerate all (ordered) subsets of an ordered set? So, for example, given the ordered set $\{2, 5, 6\}$ (using the normal ordering for integers), I need the following: ...
0
votes
1answer
102 views

How can I solve this constrained assignment problem?

The assignment problem is defined as follows: There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on ...