Questions tagged [algorithm]
Questions about algorithms used or which might be used to implement a procedure known by name or loosely but not in detail. The subject of the question may be a procedure mentioned in the literature or a Mathematica built-in function
58
questions with no upvoted or accepted answers
7
votes
0
answers
609
views
Hopcroft's Algorithm for Minimization of Deterministic Finite State Automaton
Background
Given a deterministic finite state automaton, Hopcroft's algorithm is a $O(n \log(n))$ algorithm for finding an automaton that generates the same language with a minimal number of vertices....
6
votes
0
answers
1k
views
How to find the a minimum cost perfect matching
Crossposted on Wolfram Community
A a minimum cost perfect matching is very useful tool.This three links about this demand just related me,let alone all MMA.SE.
How to get some pairing with smallest ...
6
votes
0
answers
345
views
Challenge: Speeding up MaxDetect for application in 3D blob detection
In image segmentation it is a common problem that objects appear clustered and are therefore undistinguishable from each other when using simple algorithms. Based on this post I obtained efficient ...
5
votes
0
answers
1k
views
A* algorithm for finding shortest path in a graph
FindShortestPath finds the shortest path between two vertices in an edge-weighted graph, allowing a choice between the Dijkstra and Bellman-Ford algorithms. In my (limited) understanding, both of ...
4
votes
0
answers
246
views
Approximate Nearest Neighbors in Mathematica?
Is there any support for Approximate Nearest Neighbors (ANN) in Mathematica or third-party packages? I'm looking for a good implementation of locality sensitive hashing for applications where ...
4
votes
0
answers
365
views
Problem with the accuracy of the real-coded Genetic algorithm
Since there is no Genetic algorithm implemented in the Mathematica i tried to write a very simple genetic algorithm myself. The accuracy of the results depend upon rounding up the obtained parameters. ...
4
votes
0
answers
285
views
Finding all Minimal Cut Sets for Site Percolation?
Bug introduced in 9.0 and persisting through 11.3.0
FindVertexCut and FindMinimumCut are new in 9.0.
I want to disconnect the ...
3
votes
0
answers
69
views
How to ask Mathematica to give me possible closed forms from a given numerical approximation
Imagine I am solving a some Infinite Series and I cannot directly compute the value using Mathematica.
The value of this series approximates $ 0.785398....$ (Actually is $\frac{\pi}{4}$). I want to be ...
3
votes
0
answers
421
views
How to achieve with Mathematica the effect a closure has in other languages?
Motivation
I want to write an auxiliary function (brief auxf) for testing the output of another function that evaluates its body repeatedly using ...
3
votes
0
answers
107
views
Mathematica algorithms made possible with Wolfram's NKS?
In Wolfram's NKS he mentions that the Rule-30 Cellular Automata is used as a random number generator in Mathematica. What other algorithms in Mathematica have been made possible with Wolfram's NKS?
3
votes
0
answers
145
views
Converting a Recursive algorithm to Iterative?
I have a recursive algorithm and I want to make it iterative
I found this command
RecurrenceTable[eqns, expr, {n, n_max]}]
but I don't know how I make my recurrence relation because there is ...
3
votes
0
answers
228
views
How to compute the longest non-contiguous common sequence?
LongestCommonSequence[] works well, but what about finding the longest common sub-sequence (not necessarily contiguous)? Is this function built in to the genome ...
3
votes
0
answers
952
views
Solving recursion relations using Mathematica
I want to solve the recursion relation given in equation 2.7(a/b) on page $6$ of this paper. (..the initial seed is $F_1 = G_1 = 1$ and the functions $\alpha$ and $\beta$ are defined on page $5$ in ...
2
votes
0
answers
51
views
Memorization for Rule + ReplaceRepeated?
Question
When build packages of noncummutative algebras I met the choice:
Rule + ReplaceRepeated
...
2
votes
0
answers
131
views
Implement of faster(maybe paralleled) K-Means clustering
I am writing an algorithm that needs to add noise to the centroid of each iteration on top of KMeans. Therefore, I need to implement a custom KMeans function. I checked out the methods in Mathematica ...
2
votes
0
answers
32
views
When displayed in a 1000 x 1000 window, why would a 1000 x 1000 image look more pixelated than a 500 x 500 image?
Yes, you read that correctly. I am especially concerned about the white pixels bordering the black curves. As you see, I have increased the line width 2-fold in the higher resolution image.
This ...
2
votes
0
answers
89
views
How to show recursive computation graphically?
I am studying the book "Computer Science with Mathematica" from R. Maeder. The following piece of code solves the Knapsack Problem recursively:
...
2
votes
0
answers
51
views
How algebraic (or more general) expression is represented (memory level, data structure) in Mathematica?
This is not a question about the usage of Mathematica, it is more about implementation. Mathematica is a very huge system, it can provide a series of very advanced operation against a Mathematica ...
2
votes
0
answers
141
views
Combinatorics with booleans equations
I have variables $X_i \in \{1,0,-1\}$. Now I add up $m=3$ variables
$$S=X_1 + X_2 + X_3
$$
and want to find all combinations that give me, $S=1$. I can do this with (see this solution):
...
2
votes
0
answers
57
views
How to iterate over Orbit of PermutationGroup?
Another day, another permutation group question.
I'm given a g=PermutationGroup[...], and a list l={1, 3, 3, 2, ...}. I know I ...
2
votes
0
answers
68
views
Dean's apportionment
I would like to program Dean's apportionment. https://www.maa.org/press/periodicals/convergence/apportioning-representatives-in-the-united-states-congress-deans-method-of-apportionment
Here is my ...
2
votes
0
answers
322
views
Integration of graphs with datasets
Mathematica has a rich family of graph algorithms. I would like to leverage some of these for a very large tree structure. Because of the size of the structure, I would like to store it in a Dataset ...
2
votes
0
answers
306
views
AVL binary search tree implementation
Is there any text-book implementation of self-balancing binary search trees such as AVL or red-black in Mathematica?
2
votes
0
answers
232
views
Implementation of Lubaehevsky-Stillinger Algorithm to pack hard spheres
To generate a model of a polycrystalline material with specified grain size distribution (e.g coming from a Monte Carlo Grain Growth simulation) the Paper "Effects of grain size distribution and ...
2
votes
0
answers
255
views
What's a non-trivial Mathematica program involving conscious choice of stack vs. queue data structure?
In a typical computer science algorithms course, much attention is given to the discussion of queues vs. stacks as a data structure programmers need to consciously choose from to achieve algorithmic ...
2
votes
0
answers
332
views
Fast calculation of commute distances on large graphs (i.e. fast computation of the pseudo-inverse of a large Laplacian / Kirchhoff matrix)
I have a large, locally connected and undirected graph $G$ with $\approx 10^4$ vertices and $\approx 10^5$ to $\approx 10^6$ edges. Moreover I can bound the maximum vertex degree as $Q_{max}$. I ...
1
vote
0
answers
87
views
Solving system of linear equations in specific order
I know how to solve set of linear equations using Solve, or by hand of course. However, my current problem requires me to solve the equations in a specific order, ...
1
vote
0
answers
101
views
Solving the Unbalanced Assignment Problem with FindMinimumCostFlow?
I want to adapt this code from this answer to work with unbalanced bipartite graphs:
...
1
vote
0
answers
274
views
Particle Swarm Optimization implementation in mathematica
Hi I am new to mathematica, I want to use it to implement PSO instead of using matlab. Could anyone suggest me how to find some implementation examples with code or its general implementation for ...
1
vote
0
answers
91
views
Shortest paths Knights Tour
I am trying to print the minimum steps needed to traverse a chessboard as a knight from one diagonal position to the other. I have the following code:
Building the chessboard
I started with creating ...
1
vote
0
answers
76
views
“Largest” symbolic common factor of an integer sequence (not simply GCD)
Suppose, I have a finite fragment of a quickly increasing sequence of integers $\{a_n\}$ that is too complex, unusual, or irregular for FindSequenceFunction to find ...
1
vote
0
answers
66
views
Optimal code generation for evaluation of a fixed set of multivariate rational polynomials
Given a set of multivariate rational polynomials, is it possible to find the optimal (shortest or least expensive in some other sense) sequence of arithmetical operations, such that it results in ...
1
vote
0
answers
103
views
How to use Mathematica to find the coordinates of 7 points?
Could anyone please help me with using Mathematica to find the coordinates of 7 equally spaced points on the unit sphere $S^3$ in $\mathbb{R}^4$? Thanks a lot!
1
vote
0
answers
73
views
Finding same output values by varying input values of function
I have written a function in Mathematica that needs five input variables.
The function outputs a single real number. The underlying model is a complex model for option pricing. To ease things up, let ...
1
vote
0
answers
342
views
Make Person Curve from a Picture
I recently read this; http://blog.wolfram.com/2013/05/17/making-formulas-for-everything-from-pi-to-the-pink-panther-to-sir-isaac-newton/
In this post, newton curve is made by using the image "...
1
vote
0
answers
322
views
Solving a rod cutting problem with recursion
I'm trying to use Mathematica 10.0. to solve a rod cutting problem with naive recursion. The problem is taken from Introduction to Algorithm, 3rd edition.
The length price for rod is defined in the ...
1
vote
0
answers
89
views
Depth limited search in mathematica
I often use
FindPath[G, 1, 2, {L}, All]
where $G$ is some graph. This finds all paths of length exactly $L$ edges which run between nodes $1$ and $2$.
In large ...
1
vote
0
answers
53
views
How to determine three last bindings made to a variable when evaluating an expression?
How can I create a list of bindings made to a certain variable when evaluating an expression? I want to determine three bindings made.
0
votes
0
answers
69
views
Missing "StructuredAlgorithms"in the installation
I typed the following
array = SymmetrizedArray[{{1, 3} -> a, {2, 2} -> b}, {3, 3},
Symmetric[All]]
array["StructuredAlgorithms"]
which should ...
0
votes
0
answers
63
views
How can a program be configured for these steps?
Is it possible to create a program that implements sequential mathematical steps... in order to be circulated to more than one selected set?
Step 1: For the following sets:
$$S_1=\{x_1,x_2,x_3\},S_2=\{...
0
votes
0
answers
79
views
Which algorithms are implemented in community detection based on AdjacencyGraph[.] and WeightedAdjacencyGraph[.]?
The following code generates two distinct community structures: one uses a simple adjacency matrix (with 1 and 0), another uses a weighted adjacency graph (with positive real numbers). I like to know ...
0
votes
0
answers
58
views
How to use quasi-Newton methods to solve a non-linear system?
Consider the following function, for $\mathbf{x}=\{x_1,...,x_n\}$
$$
F(\mathbf{x})=\sum_{k=0}^n \frac{e^{A_k\mathbf{x}}-e^{B_k\mathbf{x}}}{C_k\mathbf{x}}-\mathbf{b}
$$
where $\{A_k\}$, $\{B_k\}$ and $\...
0
votes
0
answers
61
views
What strategy would you adopt for this deep search on a function?
Ok, so I have a problem where I have a function that depends on 9 parameters and a bound condition
$$f(x,y,z,w,t,u,v,r,s)<K$$
Now all these variables take discrete values such as:
$$x \in \{x_1, ...
0
votes
0
answers
64
views
Algorithm: Permutations & Signature
Theoretical side
Simple example: If I have two sets $A_1=\{1,3\} ,A_2=\{2,3\}$
and Permutations[{1, 2, 3}]= $\left(
\begin{array}{ccc}
1 & 2 & 3 \\
1 &...
0
votes
0
answers
56
views
Algorithm consisting of modules returning multiple errors
I'm trying to write a genetic algorithm that will take a list of lists of reals in interval [0,1], my "starting population", "score" them according to a fitness function, append ...
0
votes
1
answer
326
views
How to obtain the convolution of these functions?
I am starting to use Mathematica. I wanted to compute
$$\nabla F*\phi(x),\;x\in\mathbb{R^2}$$
where $F(x)=\ln\|x\|$ and $\phi(x)=\chi_{B(0,2)}(x)$.
I am a new user of this software, so I don't know ...
0
votes
0
answers
138
views
On the numerical computation of polynomial roots
In the guide on the NRoots[] function I read:
...
0
votes
0
answers
50
views
Numerical minimization of function
So I have the following equation:
3 Sqrt[9.15753*10^-6 + 25.1556 TolC^2 + 25.1556 TolL^2]==1;
Now TolC and TolL can take respectively the values of these lists:
<...
0
votes
0
answers
59
views
Fortune's Algorithm (Conditional Step Size in `Manipulate`)
I am trying to implement Fortune's Algorithm. Here is my code so far.
...
0
votes
0
answers
157
views
What's going on in this Newton-Raphson algorithm?
I'm looking at this post, over on Mathematics SE. I'll summarize here:
A signal with a known velocity, c is emitted by some source. We're given the coordinates of ...