Questions related to combinatorics and discrete mathematical structures

learn more… | top users | synonyms

3
votes
1answer
33 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 ...
5
votes
1answer
34 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
104 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. ...
-1
votes
0answers
17 views

Given a dimension, how to generate vertices of an n-cube (hypercube)?

I want to generate the vertices of a regular n-cube. Specifically the matrix [-1,1]n where n is the input. But I have no idea where to begin... E.g. generateVertices(2) would generate the vertices of ...
2
votes
1answer
68 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
68 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
55 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
34 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
57 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
112 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
83 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
47 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
30 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
112 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
27 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
54 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
54 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
39 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
191 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
17 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
39 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
57 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
51 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
253 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
0answers
48 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 ...
3
votes
1answer
73 views

Count all possible unions in a collection of sets

Say we have a collections of sets $\mathcal X = \{X_1, \dots, X_n\}$ (not necessarily disjoint), and we want to count the number of possible unions of sets in $\mathcal X$, i.e. the size of ...
0
votes
1answer
42 views

n-th non-decreasing sequence

I have a generator of non-decreasing sequences of numbers 0..M: ...
0
votes
1answer
13 views
0
votes
1answer
43 views

Which permutations can not be obtained by moving elements through two stacks?

I have a Stack1 which has the entries a,b,c ( with a on the Top) and Stack2 which is empty.The condition is. An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An ...
0
votes
1answer
37 views

Given two sequences of the same size, how many longest common subsequences can they have?

For simplicity assume that both have the same size N. the lengh of this subsequence can be at most N, so maybe it's max(C(N,1), C(N,2), ... , C(N,N))?
1
vote
0answers
14 views

State of art quadratic knacksack algorithms

What is the current status to quadratic knacksack problem? Say, how many variables can the state of art solver handle? Thank you.
1
vote
1answer
84 views

Given a pile of cards, how to program to get card combinations whose sum is closest to 21?

This is an interview question: Given a pile of cards, how to program to get card combinations whose sum is closest to 21? Example: input: Array : 2, 3, 4, 5, J, K output: 2, 4, 5, J 2, 4, 5, K ...
-1
votes
1answer
26 views

What algorithms solve the minimun multidimensional multidemand 0-1 knapsack problem?

I've found an heuristic algorithm[scatter search] that solves the common version of MDMKP(MultiDemand Multidimensional Knapsack Problem)[the one that maximizes] but what about the minimize version? is ...
2
votes
1answer
94 views

Finding a specific “balls-into-bins” partition given its index in the lexicographical ordering

Given numbers $n,k\in \mathbb{N}$, we consider $\mathcal P$ to be the set of all possible partitions of $n$ balls into $k$ bins. Alternatively, $\mathcal P$ is the set of all $k$-ary vectors in ...
3
votes
1answer
139 views

The buckets of water problem

Let's consider the following problem (buckets/pails of water problem) (This problem may be known with different name. If does, please correct me). Let $B=\{b_1,...,b_n\}$ be a set of $n$ buckets. ...
3
votes
2answers
230 views

How many structurally different trees can be formed with n nodes?

Is there any exact formula for finding number of structurally different unlabeled trees can be formed with $n$ nodes? I searched a lot and I found some approximation formulas, e.g. here.
1
vote
1answer
84 views

Permutations in an k-sorted array

Definition of $k$-sorted array: An array in which an element is at-most $k$ places away from its sorted order. I have a question in my Algorithms assignment which asks to prove the lower bound to ...
3
votes
1answer
153 views

Are there more partially recursive functions than and recursive functions?

Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?
1
vote
1answer
56 views

How many ways to find a sum totalling n using only certain Integers?

Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n? Clarification: The Integers are arbitrary, positive, and may not include 1. At first I thought it was ...
7
votes
2answers
62 views

Is there any hope to use a computer to guess combinatorial formulas for a sequence of integer values, given some initial terms?

So sometimes in combinatorics, you are computing the count $a_n$ of something that depends on a natural number parameter $n$. Either by hand or using a computer, you can often compute some initial ...
-4
votes
1answer
112 views

Count of all simple paths between two vertices in a Complete graph [closed]

A path is simple if it repeats no vertices. How many simple paths between two vertices in Complete graph? One way is listing the simple paths is to use depth-first search. but i think it should be ...
2
votes
1answer
76 views

Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where ...
1
vote
2answers
41 views

Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8

Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem? I was thinking of ...
3
votes
0answers
112 views

computing permanent of a 0-1 rectangular matrix

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1. All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired ...
0
votes
1answer
41 views

How to write all $r$-tuples with a certain property in a list [closed]

I have the following question: Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$. I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with ...
2
votes
0answers
40 views

Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula ...
2
votes
1answer
46 views

Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?

So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. If $m \leq n$, then we can use recursion on $n$ ...
1
vote
1answer
225 views

Computing binomial coefficients and factorials modulo a composite number

Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where ...
2
votes
1answer
91 views

Arrangement of numbers in a grid

I have a $n \times m$ matrix $M$ and a permutation of sequence $P$ of numbers from $1$ to $n$. I have to fill the matrix using numbers $1$ to $n \times m$ in such a way that for each row $i$, the ...
1
vote
0answers
46 views

the union of all the circuits and the intersection of all the bases [closed]

Is it correct that in a matroid, the union of all the circuits and the intersection of all the bases do not overlap? I susepect that is true from the equivalence in the definition for a coloop ...