An algorithm is a sequence of well-defined steps that defines in abstract the solution to a problem.
2
votes
1answer
92 views
Implementing Kane's Subset Sum Algorithm
In the following paper, D. Kane describes an algorithm for subset sum that runs in logspace: http://arxiv.org/pdf/1012.1336v2.pdf.
I am trying to implement it
...
3
votes
3answers
169 views
Can Mathematica solve $x^{b^2} + ax^b -1 = 0$ for $x$ with $a>0$, $b>1$?
I have a problem that I can't seem to solve neither analytically nor with Mathematica. Namely, I have the expression $$x^{b^2} + ax^b - 1= 0,$$ which I want to solve for $x$ with $a>0$, $b>1$.
...
0
votes
1answer
40 views
How do I find the all valid pairings between two sets?
I have a pretty hard problem to solve here, and I have no idea how to start. I have X kind of fruits and 5 colors (let's say Red, Green, Yellow, Blue and Purple). Each fruit can be available in ...
20
votes
4answers
912 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 ...
0
votes
1answer
72 views
How write this Function with many arguments? [duplicate]
F[x1_,x2_,...,x99_]:=expr
How to write this Function in mathematica whithout complete write it?
1
vote
0answers
45 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.
2
votes
1answer
73 views
Generating the set of all strings within a fixed edit distance of a initial string?
Provided a starting string initialString, and a particular alphabet of allowed characters {"A","B","C","D","E",...}, how can I ...
4
votes
1answer
191 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.
...
3
votes
0answers
70 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 ...
0
votes
0answers
66 views
how to write my own interpolation method
I was comparing results of spline interpolation in Mathematica and C++/gsl-library
Results of interpolation are different if I use:
...
0
votes
1answer
56 views
Implementation of a Hanning filter
I'm implementing a package for in-house signal processing.
I wrote here a quite trivial function implementing a Hanning windowing of the signal.
...
3
votes
0answers
188 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 ...
6
votes
2answers
86 views
Algorithm in RandomChoice[{w1,w2,…}->{e1,e2,…},n]?
I wonder if someone happens to know the actual algorithm implemented in the particular overload of RandomChoice that handles explicitly presented discrete ...
0
votes
1answer
120 views
6
votes
2answers
153 views
Generated Numbers under a constraint?
Let's say I have five four dimensional vectors $p_i^\mu=(p_i^1,p_i^2,p_i^3,p_i^4)$ with $i=1,2,3,4,5$. Now, I want to fill the entries of these vectors ($4\cdot5=20$ in total) with some numbers, but ...
0
votes
0answers
41 views
Write nth line to file [duplicate]
I have a code that I am running on a supercomputer. Currently the algorithm must finish before I can export any results from the algorithm. What I would like to do is to have the algorithm write out ...
3
votes
3answers
184 views
Fastest way to check if an expression contains all symbols from a list
I need to execute this function thousands of times, and the faster, the better. I came up with two versions, but wanted to see if you can come up with an even faster way. Is there a better way?
I use ...
4
votes
3answers
244 views
Creating a function with integral zeroes of the 0th, 1st, and 2nd derivatives
I would like to be able to randomly generate functions, each of which satisfies
$f : [-10, 10] \rightarrow [-10, 10]$
All the zeroes, critical points, and inflection points have an integral ...
3
votes
1answer
251 views
Specific Mathematica algorithms, for example LU Decomposition
Where I can find detailed information on algorithms used by Mathematica, especially for numerical methods. The Manual doesn't seem to iclude specifics in most cases.
For example I get a different LU ...
3
votes
2answers
128 views
Checking whether a number can be composed from the cube of its digit
How to check whether or not the sum of the cube of each digit of a number is equal to the number itself?
In the following code, I tried to return the number in question whenever it matches the ...
3
votes
0answers
118 views
Using mathematica to discover algorithms?
In Steven Wolfram's blog entries, he discusses using mathematica to discover algorithms. I have tried several different google searches for papers on such topics, and have found none. I suspect this ...
6
votes
4answers
427 views
Check if a matrix is Positive Semidefinite
I have a question concerning the check whether a given matrix is positive semidefinite or not. In mathematica the function PositiveDefiniteMatrixQ[m] tells me ...
5
votes
1answer
196 views
What algorithm and tools should I use to search a data set for the point nearest to a given point?
I have about 1,000,000,000 points, which are the longitudes and latitudes of some places in a city, formatted like this: $(106.1231233,41.43234234)$. I also have about 20,000 points which are the ...
2
votes
2answers
164 views
Write 199319989756262759279209 = 5x + y, where x and y are integers
$\frac{199319989756262759279209}{5} $ = $ 3.9864\times 10^{22}$
according to Mathematica, but I would like to see this number exactly in decimal form (not in scientific notation). I'm attempting to ...
2
votes
2answers
216 views
How does Accumulate work?
Accumulate can be used to compute the partial sums of a list.
The partial sums can also be computed using a For loop but this ...
14
votes
3answers
655 views
Generate a Random Polygon
Does some package exist with a function that takes a parameter $n$ and generates a random 2D $n$-sided simple polygon (convex or non-convex), possibly within a certain bounding box?
It does not ...
5
votes
2answers
189 views
Parallelizing or optimizing a script for calculating the size of all pairwise intersections between collections of sets
I need to speed up or parallelize an operation that looks essentially like this:
...
5
votes
1answer
166 views
Behavior of Graphics`Mesh`InPolygonQ with self-intersecting polygons
Playing around with some of the answers in the question How to check if a 2D point is in a polygon? I noticed that:
Graphics`Mesh`InPolygonQ[poly,pt]
Displays ...
1
vote
4answers
207 views
Calculating the median difference between elements with a (particular pair) of consecutive integer indices residing in the same sublist
NOTE: I formally made a serious mistake in the first example provided. pointLists[[1]] had an extra element, and we should have a guarantee that ...
6
votes
5answers
326 views
A fast way to calculate the median difference between pairs of elements
I have a list of coordinate pairs, take for example the following list of three pairs:
...
1
vote
3answers
440 views
Faster way to test if an expression equals zero
I want to test if expressions (mix of variables, functions and numbers) are zero valued, as fast as possible, and PossibleZeroQ is sometimes very slow. One solution ...
2
votes
2answers
206 views
Is there a way to parallelize the convolution component of EdgeDetect?
Provided an image like -
test = Import["http://upload.wikimedia.org/wikipedia/commons/d/d5/Sunflowers.jpg"]
We can run ...
1
vote
1answer
156 views
Efficiently determining if a morphological component overlaps a polygon with vertices at real number coordinates
I have a list of morphological components $m$, a set of vertices for a polytope $P$ (at real number coordinates), and I'd like to be able to calculate a list of morphological components $m'$ that ...
7
votes
1answer
248 views
Implementing an algorithm for finding the largest circle that contains a single point in a set (and no other point)
This question concerns the implementation of an algorithm proposed by Rahul Narain on a former question of mine that was migrated to math.stackexchange: ...
4
votes
3answers
176 views
Computing the mean difference between elements in a list with index $i$ and the closest elements with index $(i+1)$
I have a list that looks like this:
preprocessedList = {{1,5.3},{1,5.566},{1,1.4322},{2,3.443543},{2,3.444},{3,0.1223},{4,1.3243},{4,1.554343}}
Each element in ...
15
votes
3answers
508 views
How to partition a list to make each subset's size equal and mean as close as possible
Suppose we have 3 lists each with 18 numbers like this:
...
0
votes
0answers
142 views
17
votes
1answer
322 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 ...
0
votes
0answers
22 views
Pruning a list of points to find the largest clique of points with a minimum threshold point-to-point Euclidean distance [duplicate]
I have a array of points (which we'll just create randomly here):
pointList = Table[{RandomReal[{0, 5}], RandomReal[{0, 5}]}, {i, 1, 100}];
I'd like to find the ...
9
votes
2answers
209 views
Partitioning a superset of coordinates into subsets that generate continuous curves
Consider the data set corresponding to recorded trajectories for a particle:
...
5
votes
2answers
281 views
Pruning elements in an array based on the existence of similar elements in adjacent arrays
Imagine I have a series of particles floating around in $\mathrm{R}^3$, where, at any given time, particles can pop into and out of existence. Here, for some number of time points, $(t_1, \dots, ...
2
votes
3answers
100 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 ...
9
votes
6answers
361 views
Partitioning an integer into $k$ equal parts
Say I have an integer $M$. Is there a one-line command to create a partition of $M$ into $k$ integers s.t. the difference between any two integers is as small as possible?
For example, with $M = ...
2
votes
1answer
251 views
Finding a fixed vector which minimizes the pairwise distance between noisy elements in two unordered arrays
Let $A$ and $B$ be two sets of $d$-dimensional coordinates of comparible (though not necessarily equal length). For example, here we can set $d = 3$ and have normalized values like:
...
1
vote
1answer
106 views
Finding a mapping between elements in two lists that satisfy some criterion (such as being less than threshold Euclidean distance apart)?
I have two lists of $d$-dimensional coordinates, for example setting $d=3$ we might write:
...
4
votes
2answers
233 views
Efficiently determining the largest minimum cost to travel from a fixed source to an arbitrary sink in a weighted graph
Let $v_i$ be a vertex in a graph $G$ with vertices $(v_1,...,v_N) \in V$ and edges $(e_1,...,e_M) \in E$ with associated weights $(w_1,...,w_M)$. Let $v_s \in V$ be specified vertex in the graph. In ...
0
votes
1answer
124 views
Returning lists of pixels connected through their Moore neighborhoods
I have a binarized image in Mathematica 9, and I would like to generate a list of coordinates for clusters of pixels connected through their Moore neighborhoods, e.g. ...
1
vote
1answer
239 views
Understanding the computation of the geometric median
In the Wolfram Demonstration Fermat Point for Many Points, it appears that the geometric median is being calculated for an arbitrary set of five manipulable points. How might one extend this ...
1
vote
1answer
499 views
How to linearize an expression automatically?
I would like to automatically linearize some long equations in the scope of variational calculus. Here follows an example of what I need to do :
Given two variables $a_1 = q_1 + \delta q_1$ and $a_2 ...
13
votes
1answer
229 views
Baffling increase in runtime
Background of my question
I discovered Project Euler today, and decided I would work through the problems in Mathematica. I became obsessed with the first problem, which is essentially "sum all the ...
