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
108
questions
92
votes
4
answers
55k
views
How to create a new "person curve"?
Wolfram|Alpha has a whole collection¹ of parametric curves that create images of famous people. To see them, enter WolframAlpha["person curve"] into a Mathematica ...
36
votes
6
answers
7k
views
Finding all elements within a certain range in a sorted list
Suppose we have a sorted list of values. Let's use list = Sort@RandomReal[1, 1000000]; for this example.
I need a fast function ...
29
votes
8
answers
2k
views
Splitting words into specific fragments
I am looking into splitting words into a succession of chemical elements symbols, where possible. For example:
Titanic = Ti Ta Ni C (titanium, tantalum, nickel, carbon)
A word may or may not be ...
55
votes
2
answers
3k
views
Adaptive sampling for slow to compute functions in 2D
EDIT: Although I have posted an answer based on my current progress, this in incomplete. Please see the "open issues" section in the answer.
Most plotting functions in Mathematica adjust the ...
19
votes
5
answers
4k
views
Implement the Bisection algorithm elegantly and easily
Description:
Rencently, I have finished my course Numerical Analysis, so I'd like to implement many algorithm that I have learned from that course.By this practice, I hope that I can improve my ...
17
votes
2
answers
4k
views
Bresenham's line algorithm
Bresenham's line algorithm is producing discretized line for given two points for purpose of plotting for example.
Like that:
I have to stress that I'm interested in positions, not a plot.
...
30
votes
3
answers
12k
views
Plotting a set of trajectories (not a vector field) in 3D
Consider a set of trajectories in 3D space, that possibly converge. By visualizing trajectories as arrows the result will look crowded as each arrowhead will be placed where the attractor is. In 2D, ...
13
votes
5
answers
7k
views
How to deal with recursion formula in Mathematica?
In engineering problems, I am always seeing many recursion formula.
For instance, In the book "The NURBS book", I discovered many recursion formula
Fibonacci $$f(...
26
votes
2
answers
3k
views
Implementation of Balaban's Line intersection algorithm in Mathematica
I'm trying to implement a Brillouin Zone algorithm within Mathematica, including the generation of Brillouin zones of higher order in 2D and 3D. There is a nice implementation of generating these ...
42
votes
4
answers
5k
views
Finding a percolation path
I would like to examine percolation on a random lattice. To be exact, I wish to find the minimum length of a 'bond' needed such that the leftmost site can be connected to the rightmost site.
Here is ...
38
votes
4
answers
2k
views
How to implement the sample-point process like the built-ins of Mathematica?
Consider this:
pts = {{0, 0}, {1, 1}, {2, -1}, {3, 0}, {4, -2}, {5, 1}};
f = BSplineFunction[pts]
I can use ParametricPlot to ...
33
votes
3
answers
2k
views
Computing polynomial eigenvalues in Mathematica
MATLAB offers a function polyeig for computing polynomial eigenvalues, which appear, for instance, in quadratic eigenvalue problems (see here for some applications) ...
12
votes
2
answers
966
views
Determining whether two $k$-chromatic graphs are isomorphic (respecting vertex coloration)
Consider the case where I have two $k$-chromatic graphs $G_1$ and $G_2$, i.e. two graphs where individual vertices can be colored with one of a set of $k$ total colors, and I would like to determine ...
20
votes
1
answer
701
views
Simulating Theatre puzzle
I have been trying to simulate the process of the theatre puzzle from the Joy of X (Strogatz).
The puzzle, and some relevant material are here.
My simplistic coding for this process follows:
...
10
votes
3
answers
625
views
Faster Alternatives to DateDifference
I need a faster implementation of FractionOfYear and FractionOfMonth, which do the following:
Input: A time/date specified by <...
80
votes
4
answers
16k
views
Programmatic approach to HDR photography
Update
Submitted answers here are tour de force, and very educational comp-sci-wise, -- thanks folks! Tech is developing though, and here is the current implementation in the Wolfram Language. Please ...
25
votes
4
answers
2k
views
Detecting patterns of black and white stones on a 2D board
I'm writing a program to play a game of Pente, and I'm struggling with the following question:
What's the best way to detect patterns on a two-dimensional board?
For example, in Pente a pair of ...
23
votes
11
answers
3k
views
Generating an ordered list of pairs of elements from ordered lists
I have a pair of ordered lists. I want to generate a new ordered list (using the same ordering) of length n by applying a binary operator to pairs of elements, one from each list, along with the index ...
22
votes
1
answer
3k
views
How to extract metadata from an image of a business card?
I'm trying to digitize some documents, and I came across a very cool app called camscanner app which performs parallax transform and ocr very nicely, now I'm implementing it in mathematica...
Given a ...
18
votes
7
answers
3k
views
Given a large binary matrix, find the largest submatrix containing non-zero elements
I'm looking for a way to reduce a binary matrix containing zeros at some positions into a matrix that contains no zeros by deleting rows and columns of the original matrix until only non-zero values ...
15
votes
2
answers
3k
views
Simple algorithm to find cycles in edge list
I have the edge list of an undirected graph which consists of disjoint "cycles" only. Example:
{{1, 2}, {2, 3}, {3, 4}, {4, 1}, {5, 6}, {6, 7}, {7, 5}}
Each ...
15
votes
2
answers
1k
views
How to fill a grid make its total be largest
I have a blank grid whose dimension is 5*5.
I want to fill it with some number using 1, 2, 3 and 4. But in every blank space if you fill 2, its neighbor (include four direction, such as left, right, ...
14
votes
4
answers
4k
views
Finding elementary cycles of (directed) graphs
I need to enumerate all the simple cycles (i.e. elementary cycles where no vertex is repeated other than the starting) of a graph which has both directed and undirected edges, where we can treat the ...
0
votes
3
answers
310
views
How to compute higher iterations in mathemtica
I have the equation $u^{\prime\prime}(t)+u^{2}(t)-t^{4}-2=0$ such that $0\leq t\leq 1$and also I have $u(0)=0$ as well as $u(1)=1$. Noe the exact solution of the equation is $u(t)=t^{2}$. Now I ...
30
votes
2
answers
3k
views
How can I pack circles of different sizes into a spiral?
Given a list of circles of different areas, I need to arrange them tangentially in order of increasing area and spiraling outward. An example of the type of packing I'm attempting is shown by the ...
30
votes
7
answers
1k
views
Alternative ways to implement a triangular recursion
Triangular recursions are a class of algorithms that frequently turn up in computational mathematics. These recursions are expressible in the general form
$$T_k^{(n)}=f(T_{k-1}^{(n)},T_{k-1}^{(n+1)})$...
23
votes
1
answer
692
views
Underlying Algorithms for List Manipulation Functions
Does anyone know, or know of a link for the underlying algorithms used for list manipulation functions?
Specifically:
Union with and without the ...
21
votes
3
answers
2k
views
Build a refined grid based on intersecting line
I honestly have no idea where to begin with this problem. In summary, I have a 2D coarse grid with an intersecting line. For an easy example, let's assume it's a 4x4 grid.
I wish to pass through each ...
16
votes
2
answers
1k
views
3D tree in Mathematica?
Searching the web for information about the affine transformation, I found the one page, which called my attention for the tree that show and is this
but unfortunately do not give information about ...
14
votes
5
answers
3k
views
Match opening and closing parentheses?
Suppose I have a List of the form:
lst={"(", "(", "(", ")", "(", ")", ")", ")"}
By running ...
6
votes
2
answers
640
views
Finding all minimal paths in site percolation?
I want to find all minimal site percolation paths from the left side to the right side, small demo grid.
A related question is here on finding bond percolation paths instead of minimal site ...
5
votes
5
answers
2k
views
How can I compute the chromatic number of a graph?
I'm starting in Wolfram Mathematica.
I saw that MinimumVertexColoring [g] could be used to calculate the chromatic number of a graph, but ...
2
votes
3
answers
180
views
Reversibly merging sets of $k$ adjacent elements in an array
Say I have an array of the form:
ExampleArray = {{1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}, {12}};
I'd like to be able to reversibly merge sets of $...
48
votes
1
answer
2k
views
How to construct a treemap using non-rectangles?
I've written the standard version of a tree map (a graphic that shows nested data) and I'm looking to improve on this layout by switching to different types of polygons or perhaps circles. Can anyone ...
29
votes
5
answers
4k
views
Mathematica Implementations of the Random Forest algorithm
Is anyone aware of Mathematica use/implementation of Random Forest algorithm?
21
votes
4
answers
1k
views
What's wrong with this FFT-based Von Kármán vortex street simulation?
About 9 years ago, I came across this interesting website, and found the following paragraph with a broken Mathematica code sample:
When fluid passes an object, it can leave a trail of vortices ...
20
votes
2
answers
1k
views
How to quickly calculate intersections of filled curves?
I am trying to quickly calculate the intersection of polygons with more than 6,000 points. A compiled solution would be preferable.
Here is one example of the problem:
...
18
votes
4
answers
4k
views
How to get actual triangles from DelaunayTriangulation[]?
The ComputationalGeometry package has a DelaunayTriangulation[] function. It returns a list of points connected to each point, ...
18
votes
2
answers
1k
views
How can I speed up the classic GA for graph coloring?
I'm trying to compute the chromatic number of this graph (which is 28):
g = Import@"http://www.info.univ-angers.fr/pub/porumbel/graphs/dsjc250.5.col";
My genetic ...
16
votes
3
answers
477
views
Visibility Polygon
Description
Based on recent assignment at work, I have become interested in computational geometry. So, I am trying to implement a visibility polygon as to explore some fundamental concepts and ideas....
16
votes
1
answer
2k
views
Efficient backtracking with Mathematica
Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("...
15
votes
3
answers
825
views
Partitioning with constraints on subsets
Given the following data:
constraints = {{11, 2}, {11, 3}, {11, 4}, {11, 6}, {11, 9}, {1, 6}, {5, 6}, {2, 5}};
weights = {3, 7, 3, 2, 4, 2, 2, 2, 3, 2, 1};
I ...
13
votes
9
answers
918
views
Replace interior of matrix with zeros
I have f.e. the following square matrix:
...
10
votes
3
answers
708
views
Find intersection points with V10
My question departs from this one: Find intersection of pairs of straight lines
but now I want to find the points with the new V10 Region-functions.
...
10
votes
2
answers
397
views
Partitioning a superset of coordinates into subsets that generate continuous curves
Consider the data set corresponding to recorded trajectories for a particle:
...
9
votes
1
answer
523
views
How can I extend BinCounts to work on Times and Dates?
I want to extend BinCounts to work on a list of times or dates, binning them by Day, Week, Hour of the Month, Day of the Year, etc... So given a list of times and a time bin spec, I need to calculate ...
8
votes
2
answers
444
views
find subsequences of constant increase
A list like
l = {0, 1, 2, 3, 4, 5, 7, 9, 12, 13, 18, 19}
may have subsequences of constant increase, $a_{n+1} = a_n + k$.
For example:
...
8
votes
4
answers
3k
views
Calculating an integral by the Romberg Algorithm
In my "Numerical Analysis" course, I learned the Romberg Algorithm to numerically calculate the integral.
The Romberg Algorithm as shown below:
$$T_{2n}(f)+\frac{1}{4^1-1}[T_{2n}(f)-T_{n}(f)]=...
7
votes
2
answers
412
views
Is there something akin to "SubgraphIsomorphismQ" in Mathematica 9?
Provided two unlabeled graphs, $G$ and $H$, I would like to test where $H$ is a subgraph of $G$. In other words, I'd like to test whether we can prune some fixed number of vertices or edges from $G$ ...
5
votes
3
answers
484
views
Finding the dangling free part of a cluster connecting two nodes
I am trying to learn how to use Mathematica for analyzing graphs, more specifically in the context of connectivity and percolation.
For the sample graph that I have included in this post, we have a ...