|
No.
n!
nPr = ------
(n-r)!
n!
nCr = ---------
(n-r)!*r!
Permutations = a set of elements in which order matters.
Combination = a set of elemets in which order does not matter.
nPr = nCr * r!
Permutations = (elements of subset)*(# of ways to order subset)
Example
-------
SET = {a,b,c,d}
4P3 = 24:
{a,b,c},{a,c,b},{b,a,c},{b,c,a},{c,a,b},{c,b,a}
{a,b,d},{a,d,b},{b,a,d},{b,d,a},{d,a,b},{d,b,a}
{a,c,d},{a,d,c},{c,a,d},{c,d,a},{d,a,c},{d,c,a}
{b,c,d},{b,d,c},{c,b,d},{c,d,b},{d,b,c},{d,c,b}
4C3 = 4:
{a,b,c}
{a,b,d}
{a,c,d}
{b,c,d}
in this case r=3 => r!=6
4P3 = 4C3 * 3! = 4 * 6 = 24
Notice that each line under 4P3 is the number of permutations of the corresponding line under 4C3.
-Sean
----
Shag a Lizard
|
|
|
|
|
Wonderful, thanks for the detailed answer,as i might going to produce a buggy application 
|
|
|
|
|
I give up. I've fiddled with this problem for months (in a part-time way) and can't find a solution. In a power system using overhead lines we have to design to meet certain minimum heights above ground for electric lines. As it would require infinite tension on the line to make it perfectly horizontal, all lines have some amount of sag. I was raised to believe in the laws of physics and mathematics, and in my ignorance assumed that there is some simple equation that is well known in the industry for calculating this important factor. It turns out that there isn't; engineers use tables of empirical data for various types of wire to do their designs. That's just plain wrong!
Given a pair of poles, with a cable rigidly affixed at each end, set a known distance apart, it should be possible to calculate how much sag will exist for any applied tension. I haven't a clue how to do it, however. The cable types are well characterized, with weights per foot, modulus of elasticity, and tensile strength published. Why should this be so hard?
So, the challenge is to derive an algorithm to calculate the sag from known data, without having to first build it. A second part of the challenge is to calculate the final sag (after the wire has stretched a bit from its initial sag), which should occur a few days after stringing.
Extra points will be awarded for an adjustment factor that allows for temperature variations of +/- 100C. More than that would be futile, as aluminum anneals badly above 200C.
Any tries?
"...a photo album is like Life, but flat and stuck to pages." - Shog9
|
|
|
|
|
Tell the truth, this has something to do with boobs and not power lines?
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
I admit only that it might have multiple applications...;)
"...a photo album is like Life, but flat and stuck to pages." - Shog9
|
|
|
|
|
Roger Wright wrote: Why should this be so hard?
Ask the Bernoulli brothers.
A cable hanging under the force of gravity from 2 fixed points makes a catenary curve. It took the Bernoulli's a long time to discover the equation of this curve (using the calculus of variations).
Y = a*cosh(x/a)
where a = height of the cable above ground at it's lowest point.
Y(0) = a
Y(-d/2) = Y(d/2) = h
where d is the distance between poles and h is the height of the attached wire at the pole. (Each end is assumed to be at the same height on level ground).
Y(d/2) = h = a*cosh(d/(2a)) = a/2 * [exp(d/(2a)) + exp(-d/(2a))]
=> h = a/2 * [exp(d/(2a)) + exp(-d/(2a))]
solving for a is not trivial, thus the tables of empirical data.
http://www.powline.com/products/sagsec.html[^]
-Sean
----
Shag a Lizard
|
|
|
|
|
Also known as the brachistochrone problem.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
Bassam Abdul-Baki wrote: Also known as the brachistochrone problem.
Related to the catenary problem, but not exactly the same. Brachistochrone problem is the problem of finding the path of shortest time between two points.
An example of the brachistochrone problem is the problem of finding the path light travels between two points (optical path length). Contrary to popular belief, light does not travel the shortest distance between two points, but the path of shortest time between two points.
-Sean
----
Shag a Lizard
|
|
|
|
|
I stand corrected. Light is overrated anyway.
"I know which side I want to win regardless of how many wrongs they have to commit to achieve it." - Stan Shannon
Web - Blog - RSS - Math - LinkedIn
|
|
|
|
|
Cool!
I've looked at Sagsec before, but I doubt the boss wants to buy it at that price. But it would be fun to write my own version. Thanks! I knew I could count on 3.3 million geniuses to find some practical solutions.
"...a photo album is like Life, but flat and stuck to pages." - Shog9
|
|
|
|
|
If you do finish it, send a post.
Perhaps we can turn it into a cool game. :->
Any ideas? 
|
|
|
|
|
Here (scroll down past the parabola stuff)[^] is an interesting derivation that solves for the height of the poles above the lowest point of the catenary in terms of the weight per unit length and the tension at the poles, which is at least a close starting point to what you are looking for (same as sag). Calculating the initial deformation (final sag) is left up to you, it changes the weight per unit length, but how much? I'm sure the solution assumes perfect inelasticity along the length of the cable, so it is a starting point at best. The derivation might give some additional clues, since it is based on the solution for the length of such a curve. Perhaps deriving the stretch due to tension first, would be a useful direction to go.
|
|
|
|
|
Interesting article! Thanks!
"...a photo album is like Life, but flat and stuck to pages." - Shog9
|
|
|
|
|
It's your lucky day Roger.
I have decided to grace your question with my massive intelect.
Roger Wright wrote: The cable types are well characterized, with weights per foot, modulus of elasticity, and tensile strength published.
Ok,you can go a s far as the "Sagsec" type of solution quoted elsewhere in this thread, but I believe you would be better off looking for a good Rule of Thumb, that can be applied to other areas and applications.
Ok weights per foot, modulus of elasticity and tensile strength mumbo jumbo are irrelevant. You must ascertain a maximum usable length per strand and be done with that. The other factors are only of real use when discussing the virtues of a tether for an orbitting satellite. You and your decent Injun bretheren have not ventured into this field yet I pressume.
I percieve the savings from using the best solution for this on a new power route to be substantial so working on a solution is admirable.
Ok lets say we have Pole1 at height h1 and Pole2 at height h2 and a hypoteneuse of distance dh.
What we now need to know for in the field rules of thumb are
i.) The lowest point of the power line (clue the lesser of Pole1 and Pole2 is the maximum boundary.)
ii.) The distance the lowest point is reached from either Pole.
iii.) A formula to calculate the lines height at any other distance from a Pole.
note this is easiest to do once kwowledge of i and ii are achieved.
The guts of this is that gravity on earth is generally consistent from one location to another, so a section if not all when Pole1 and Pole2 heights are equal will be symmetrical.
To calculate the new shape and dimesions of the line for the remainder of the line will use the already calculated figures to calculate the rest.
So guess what you now need to use interpolation.
Regardz
Colin J Davies
The most LinkedIn CPian (that I know of anyhow)
|
|
|
|
|
I need an algorithm for combining values from a variable number of variable length categories.
For example, I might have an array of the following values with their associated categories:
value1 - category1
value2 - category1
value3 - category2
value4 - category2
value5 - category2
The result should be sets containing every possible combination of 1 value from each category:
{value1, value3}
{value1, value4}
{value1, value5}
{value2, value3}
{value2, value4}
{value2, value5}
I can't use C(n,k) because k is variable. Can anyone help? My brain has short-circuited on this one.
Thanks!
|
|
|
|
|
you may try something like this
static void Main(string[] args)<br />
{<br />
int[] nItems = { 2, 3 };<br />
int[] number = new int[nItems.Length];<br />
Generate(nItems, number);<br />
}<br />
<br />
static void Generate(int[] CategoryItemCount, int[] currentCombination)<br />
{<br />
for (int i = 0; i < CategoryItemCount[0]; i++)<br />
{<br />
currentCombination[CategoryItemCount.Length - 1] = i;<br />
<br />
if (CategoryItemCount.Length != 1)<br />
{<br />
Generate(new List<int>(CategoryItemCount).GetRange(1, CategoryItemCount.Length - 1).ToArray(), currentCombination);<br />
}<br />
else<br />
{<br />
}<br />
}<br />
}<br />
regards
|
|
|
|
|
|
|
|
Yes your test passed.
As of how to accomplish that have you ever tried Google?
Failing that try ![Badger | [badger,badger,badger,badger...]](https://codeproject.freetls.fastly.net/script/Forums/Images/badger.gif) .
|
|
|
|
|
Hi Guys,
I’m creating an animation program and have built a Bezier spline motion editor. The user-controllable curve plots time(x) against value(y). So my challenge is to retrieve the 'y' value from a given 'x' on the curve. However, all the articles I've been able to find/understand only give a formula for calculating an x or y from 't' - the percentage along the given cubic bezier curve.
As 't' is more concentrated around areas which heavily curve (to make a smooth curve), it's not possible to calculate y from x. So I'm using what seems to be a recognised work around and iteratively guessing at which 't' value produces x, continually reducing the difference until I find the correct 't' which produces my required x. I then use this 't' to calculate y.
This all works perfectly well. However, this is an animation program so I need to optimize this process. My current technique requires up to 15 iterations before it finds an accurate value for 't'. I found an article online by Don Lanaster, “Some more cubic spline math BEZMATH.PS”. He mentions using the Newton-Raphelson method to reduce this process down to 3 iterations. Apparently this technique uses the slope of the curve to make the approximation of 't' more accurate. However, the formula he uses doesn't match the formula I currently have working to calculate a value on the curve. I'm sure I'm misunderstanding it!
At this point I have to confess I am a Math dummy. I can work my way around practical mathematical issues as long as I don’t have to resort to long formulas full of ancient Greek!
Here's an extract from Don's article:
--- Quote ----
Let's use a better ploy to get our approximation to close quickly. It is called the NEWTON-RAPHELSON method, but is much simpler than it sounds. Say we get an error of x - x1. x1 is the current x for our current guess. At x1, our spline curve has a slope. Find the slope.
The slope is expressed as rise/run. Now, on any triangle...
rise = run x (rise/run)
This gives us a very good improvement for our next approximation. It turns out that the "adjust for slope" method converges very rapidly. Three passes are usually good enough. If our curve has an equation of...
x = At^3 + Bt^2 + Ct + D
...its slope will be...
x' = 3At^2 +2Bt + C
And the dt/dx slope will be its inverse or 1/(3At^2 + 2Bt +C). This is easily calculated. The next guess will be...
nextguess = currentt + (curentx - x)(currentslope)
----- end quote ----
So here's the function I call iteratively with varying values for 't' and it returns 'x' for me to compare with what I want:
public float CalcBezierValue(float t, float A, float B, float C, float D)
{
t = 1 - t; // Reverse the normalised percentage
float F1 = t * t * t; // These vars used purely for visual clarity
float F2 = 3 * t * t * (1 - t);
float F3 = 3 * t * (1 - t) * (1 - t);
float F4 = (1 - t) * (1 - t) * (1 - t);
return A * F1 + B * F2 + C * F3 + D * F4;
}
As you can see the base formula which produces the return value is quite different from the one in the article (x = At^3 + Bt^2 + Ct + D). Consequently I’m failing to comprehend how to calculate the slope value or its inverse which seem to be required to reduce the number of calls to this function.
Can anyone help me?
Many thanks for your time,
Simon
-- modified at 12:01 Wednesday 13th September, 2006
|
|
|
|
|
srev wrote: I’m creating an animation program and have built a Bezier spline motion editor. The user-controllable curve plots time(x) against value(y). So my challenge is to retrieve the 'y' value from a given 'x' on the curve. However, all the articles I've been able to find/understand only give a formula for calculating an x or y from 't' - the percentage along the given cubic bezier curve.
This is one of many, many reasons why I won't use a Bezier spline for camera or motion control. A) its always more difficult B) it is always more time-consuming and cpu-hogging.
I tend to use Catmull subdivision surface variants. Catmull-Rom for splines although I have my own variation of it. The original code was from a motion spline in AI Game Programming Wisdom[^] I modified it for uneven weighted distances and some other actions. If you are trying to do smooth motion cameras without a huge CPU overhead, I highly recommend the book. I use it for just about everything within, it's a great book all around, but in related to this there is a chapter on least-acceleration motion curves, PID controllers and subdivision splines, all slightly different approaches to motion control.
If you don't want the book, take a peek at these:
http://www.mvps.org/directx/articles/catmull/[^]
http://www.lighthouse3d.com/opengl/maths/index.php?catmullrom[^]
http://www.cubic.org/docs/hermite.htm[^]
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
Jeffry thanks for these links, they look really usefull. And Amazon has my money for the book you recommended.
Thanks again!
|
|
|
|
|
Hi,
If this is your function, y = CalcBezierValue(t, A, B, C, D), the slope function may be (I have not tested it at all)
public float CalcBezierSlope(float t, float A, float B, float C, float D)
{
t = 1 - t; // Reverse the normalised percentage
float F1 = 3 * t * t; // These vars used purely for visual clarity
float F2 = 6 * t - 9 * t * t;
float F3 = 3 * (1 - t) * (1 - t) - 6 * t * (1 - t);
float F4 = -3 * (1 - t) * (1 - t);
// I am not sure about the minus, but since there's function composition t = 1 - t ...
return ( -1 ) * A * F1 + B * F2 + C * F3 + D * F4;
}
and your iteration function may look like
public float CalcBezierNextGuess(float x0, float t, float A, float B, float C, float D)
{
// I am not sure about the minus sign, may be a plus
return t - (CalcBezierValue(t,A,B,C,D) - x0) / CalcBezierSlope(t, A, B, C, D);
}
I might be completely wrong, but I have no time to test this.
Regards,
|
|
|
|
|
Guys,
Thanks so much for everyone's feedback. From all the feedback on this and other forums I have the answer.
The function CalcBezierValue() computes the cubic Bézier curve as the polynomial:
x = A*t^3 + 3*B*(t^2)*(1-t) + 3*C*t*(1-t)^2 + D*(1-t)^3
To use the technique in the article I need the derivative:
x' = 3*A*t^2 + 6*B*t*(1-t) - 3*B*t^2 + 3*C*(1-t)^2 - 6*C*t*(1-t) - 3*D*(1-t)^2
The final code looks like this:
// Calc the derivative value of the curve at the specified percentage (rather than the polynomial)
public float CalcBezierDerivative(float P, float A, float B, float C, float D)
{
P = 1 - P; // Reverse the normalised percentage
float tR = 3 * A * (P * P);
float tS = 6 * B * P * (1 - P);
float tT = 3 * B * (P * P);
float tU = 3 * C * ((1 - P) * (1 - P));
float tV = 6 * C * P * (1 - P);
float tW = 3 * D * ((1 - P) * (1 - P));
return tR + tS - tT + tU - tV - tW;
}
Many thanks for all your responses.
Simon
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
