Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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).

0
votes
1answer
55 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 ...
2
votes
0answers
31 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. ...
3
votes
1answer
34 views

Software for finding a minimum vertex cover for a hypergraph

A hypergraph $H = (V,E)$ consists of a finite set of vertices, say $V=\{1, \dots, n\}$ and a set of hyperedges $E \subseteq \mathcal{P}(V)$. We call $H$ a $k$-hypergraph if all $|e| = k$ for all $e\in ...
0
votes
1answer
25 views

combinatory exploration c++ [closed]

I have n spots with 2 possible positions each. I would like to explore all of this possibilities in C++ using loops (or something else if there is a better option). I was thinking of looping from 0 ...
1
vote
0answers
40 views

Create n matrices

I conducted a fuzzy likert scale questionnaire (multiple answers possible instead of only one). Each question is answered under 3 different scenarios, which, in the traditional Likert case would ...
4
votes
1answer
105 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 ...
0
votes
1answer
66 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 ...
5
votes
1answer
150 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/...
1
vote
0answers
36 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 ...
1
vote
0answers
24 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 ...
1
vote
1answer
3k views

Looking for a C/C++ implementation of the Hungarian method for real-valued cost matrix

I am looking for a C/C++ implementation of the Hungarian method for solving the linear assignment problem with real-valued cost matrix. Some implementation I found, such as this one, only work for ...
4
votes
1answer
216 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 ...
1
vote
1answer
71 views

Algorithm for generating the next m-tuple of integers, subject to constraints

I am looking for an algorithm with the following characteristics: It is used to generate the set of integer vectors $\mathbf k=(k_1,\ldots,k_m)$, where $k_i\leq K_i$, $k_i\geq 0$, and $K_i$ are ...
5
votes
1answer
66 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 ...
1
vote
0answers
57 views

Solving an LP greedily

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 ...
3
votes
0answers
68 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 ...
1
vote
0answers
92 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 ...
1
vote
1answer
106 views

Comparison of the time efficiency of an optimization problem formulated as a Network Flow model and Mixed Integer Programming

In combinatorial optimization, there are many problems that can be formulated as either Network Flow model or Mixed Integer Programming (MIP), e.g. supply chains, transportation, and graph-base ...
2
votes
1answer
148 views

enhancing a MIP formulation of Ising model [closed]

I want to construct a MIP formulation for Ising model. For simplicity, I will only include terms involving nearest-neighbor pairs and triangular terms. I propose one formulation and ask whether there ...
2
votes
0answers
80 views

About Convex Geometry

A consistency notion in constraint programming: Let $P = (X, D, C)$ be a CSP. Given a set of variables $Y \subseteq X$ with $|Y| = k -1$, a locally consistent instantiation $I$ on $Y$ is $k$-...
2
votes
3answers
3k views

calculate Binomial coefficient over $2^n$ in Matlab

I want to calculate ${n \choose k}/2^n$ for moderate $n$ and $k$. In Matlab, use nchoosek(n,k) with $n=60$ and $k=30$ will give a warning: "Warning: Result may not ...
4
votes
2answers
64 views

gradient for ternary functions?

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 ...
2
votes
1answer
513 views

Evolutionary algorithm - Traveling Salesman -fitness function

I'm trying to solve this problem using genetic algorithms and am having difficulty choosing the fitness function. My problem is a little different than the original Traveling Salesman Problem, since ...
4
votes
1answer
183 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 ...
1
vote
1answer
735 views

How can I compute whether a sequence is an even or odd permutation of an increasing sequence? [closed]

Variants of this question have been crossposted to Stack Overflow and Mathematics Stack Exchange. Additional answers may be found at these other sites. Computational Science People: I originally ...
2
votes
1answer
474 views

Trying to implement a simple/efficient combinations function in MATLAB

So, recently, I have found myself in the position of having to implement a combinations function in MATLAB. What I mean by this is the following: I simply need to list all possible combinations for an ...
3
votes
0answers
74 views

Parallel algorithm to use in place of PORTA?

We currently use PORTA software to find the list of facet-defining inequalities (FDI) for polytopes that we work with. For certain polytopes, PORTA works fine. But because it is a serial algorithm (...
3
votes
1answer
83 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 ...
4
votes
1answer
170 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 ...
6
votes
1answer
155 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 ...
4
votes
1answer
544 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 ...
5
votes
2answers
225 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 ...