# Questions tagged [combinatorics]

Combinatorics (combinatorial analysis) is a branch of mathematics that studies the discrete objects, the set (a combination, permutation, deployment and transfer of elements) and the relationship to them (eg, partial order).

39 questions
Filter by
Sorted by
Tagged with
160 views

### Algorithm for generating all cartesian products, without rotations

(Not sure if that's the right SX site? I don't need actual code, so…) I'm looking for an algorithm that generates all cartesian products for a list of sets, but skips tuples that are just rotations ...
233 views

### Enumerating hexahedral cell vertices and faces in arbitrary dimension

I have a Cartesian mesh in $d$ dimensions, and I would like to enumerate all the subcells of a given hexahedral cell. If I am just enumerating the vertices of a cell (or cells that contain a vertex) I ...
221 views

### Striking examples of success of local search algorithms

In N queens problem https://en.wikipedia.org/wiki/Eight_queens_puzzle, trying to find solution by backtracking encounters difficulties quite fast (even for SWI-Prolog, http://swish.swi-prolog.org/...
109 views

The quadratic knapsack problem (QKP) $$\max_x x^TPx$$ $$\mathrm{s.t.}\;\;w^Tx\leq c,\; x\in\{0,1\}$$ where $P\geq0, w\geq0$ elementwise, is well studied and has existing solvers. My problem below ...
75 views

### Optimal partitioning of a graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
98 views

### Graph optimization for parallel processing

Consider the following example structure of overlapping images marked A,B,C,D. The possible overlaps are marked by gray color: The structure can be represented by a weighted undirected graph (images ...
64 views

I've got a function of form $$f: (\mathbb{Z}_3)^n \rightarrow \mathbb{R}$$ to optimize, where $n$ is relatively large (the order of hundreds). Is it there a gradient-like notion for these type of ...
495 views

### Sum of Inverse of Variables in an Optimization Problem

I have the following optimization problem: $$\begin{array}{ll} \text{Minimize} & \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{d_n} \\ \text{Subject to} & A x \leq b \end{array}$$ where ...
560 views

### What is the probabilistic model behind sudoku grids?

I'm talking about the vanilla sudoku game, with 9x9 grids equally split into 9 regions. I've tried a few approaches to estimate the probability that a specific number is in a specific location, but I ...
184 views

### What strategies one can use to keep maximum number of non attacking pieces on an $n \times n$ chess board? [closed]

What are the strategies one can use to keep maximum number of non attacking pieces (all pieces other than pawn) on an $n\times n$ board? It is like an $n$-queen problem but here instead of only queen ...
196 views

### Generating lattice clusters/graphs in parallel

I'm trying to generate all graphs with n or fewer vertices that can be embedded in some lattice, eg square, triangular, Kagome. Do there exist algorithms to both enumerate and draw these graphs? What ...
116 views

### Algorithm to generate all vectors of integers with magnitude between $n\pm \delta$

I am working on an program to compute the structure factor of a given configuration of particles, and I need an efficient algorithm to generate all the possible vectors with integer coordinates and ...
86 views

### Improve optimization over 'mapping' of indices

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference ...
94 views

### GPGPU/FPGA programming for Combinatorial Analysis

Recently, I have taken an interest in performing combinatorial analysis for the game of 21 (blackjack) and attempted to use my AMD APU to try and thread the program via the 4 cores on the chip. ...
127 views

36 views

### What is the generalization of the resource allocation problem I'm dealing with here?

I'm dealing with a problem as follows: I have a finite set of money 𝑚 to spend over 𝑟 different raffles, and I need to spend approximately to my budget, with the goal of maximizing my probability ...
41 views

### Optimal distribution of zeros and ones over matrix

I have the following problem: Given a matrix with n rows and m columns. Some elements of the matrix are unavailable. For each column, you have a set containing a number of zeros and ones which must ...
28 views

### Clustering by shared subsequence

I have a question that relates to the classical "longest common subsequence" problem. I'll give the background to the problem, but you could skip to the formulation below if you like Let's think of ...
60 views

### Solving an LP greedily [closed]

I have the following LP:  \begin{array}{ll} \text{Minimize} & \sum_{j=1}^n x_j \\ \text{Subject to} & \sum_{j=1}^n a_{ij} x_j \geq b_i,~~~i\in\{1,\ldots,M\} \\ & 0 \leq ...
102 views

### Is this problem statement good for a GPU?

I am used to using GPU hardware for large scale matrix operations and vectorizing mathematical operations on a continuous space which has been discretized for numerical computation, but this is a ...
67 views

### tea bag flavors mixing algorithm [closed]

I bought three boxes of tea bags with different flavors (A, B, C). I wish to mix them in such a way that - there is never two consecutive bags of the same flavor (ABCCAB is avoided) ; - the mixing ...
67 views

### Picking n integers from n different sets summing to a given value

Given a set of integers $\{l_1,l_2,\ldots,l_n\}$, where each integer is associated with a set $m_k\in\{-l_k,-l_k+1,\ldots,l_k\}$, I need to find all combinations $\{m_1,m_2,\ldots,m_n\}$ that sum to a ...
70 views

### Which algorithm is capable of solving a combinatorial optimization problem like this?

The problem I have at hand is a regression problem where each of $p$ inputs, $x_1, x_2, x_3, \cdots, x_p$, needs to undergo a variable transformation using one of $q$ basis functions from a set of ...
20 views

### Benchmark instances for directed 3-Cycle cover

The directed 3-Cycle cover asks for a vertex-covering set of oriented cycles with at least three vertices per cycle such that every vertex is covered by exactly one cycle. I have scrutinzed the ...