

Apologies for the shouting but this is important.
When answering a question please:
 Read the question carefully
 Understand that English isn't everyone's first language so be lenient of bad spelling and grammar
 If a question is poorly phrased then either ask for clarification, ignore it, or mark it down. Insults are not welcome
 If the question is inappropriate then click the 'vote to remove message' button
Insults, slapdowns and sarcasm aren't welcome. Let's work to help developers, not make them feel stupid.
cheers,
Chris Maunder
The Code Project Cofounder
Microsoft C++ MVP





For those new to message boards please try to follow a few simple rules when posting your question. Choose the correct forum for your message. Posting a VB.NET question in the C++ forum will end in tears.
 Be specific! Don't ask "can someone send me the code to create an application that does 'X'. Pinpoint exactly what it is you need help with.
 Keep the subject line brief, but descriptive. eg "File Serialization problem"
 Keep the question as brief as possible. If you have to include code, include the smallest snippet of code you can.
 Be careful when including code that you haven't made a typo. Typing mistakes can become the focal point instead of the actual question you asked.
 Do not remove or empty a message if others have replied. Keep the thread intact and available for others to search and read. If your problem was answered then edit your message and add "[Solved]" to the subject line of the original post, and cast an approval vote to the one or several answers that really helped you.
 If you are posting source code with your question, place it inside <pre></pre> tags. We advise you also check the "Encode "<" (and other HTML) characters when pasting" checkbox before pasting anything inside the PRE block, and make sure "Use HTML in this post" check box is checked.
 Be courteous and DON'T SHOUT. Everyone here helps because they enjoy helping others, not because it's their job.
 Please do not post links to your question into an unrelated forum such as the lounge. It will be deleted. Likewise, do not post the same question in more than one forum.
 Do not be abusive, offensive, inappropriate or harass anyone on the boards. Doing so will get you kicked off and banned. Play nice.
 If you have a school or university assignment, assume that your teacher or lecturer is also reading these forums.
 No advertising or soliciting.
 We reserve the right to move your posts to a more appropriate forum or to delete anything deemed inappropriate or illegal.
cheers,
Chris Maunder
The Code Project Cofounder
Microsoft C++ MVP





Requirement: using recursion, size of array is an even number.
For example:
0 1 2 3 4 5 (order of index)
a b c d e f (array before arrange)
a c e b d f (array after arrange)
0.......1.......2......3.......4......5.......6......7 (order of index)
a1....b1....a2....b2....a3....b3....a4....b4 (array before arrange)
a1....a2....a3....a4....b1....b2....b3....b4 (array after arrange)
The problem looks easy to solve if we dont care about optimization, we can use temp array or use recursion combine with a loop to shift items ... I think this way is not best solution ....I try to use recursion combine with swap operation, without using loop ... but I fail.
Hope someone suggests me an idea to resolve the problem, thanks any help
modified 6hrs 20mins ago.





It is a fairly straghtforward matter of taking all the even numbered items (0, 2, 4 etc) first, followed by the odds.





Hi
I have a dataset and I want to perform Association Rules on it.
In other for it to predict accurately, the algorithm should have the ability to look at each attribute and decipher their association which mostly is a result of activities between each attribute in the form of multiplication, addition, subtraction, reappearance of common patterns etc
Common association algorithms follow a basic pattern deciphering method...'comparing the reoccurrence of item sets'....
The association algorithm I have in mind should have a dynamic god capability....it should be able to determine the relationship between the attributes by going deeper such as finding out if the multiplication of the data 'value' of an instance in one attribute with another data value of an instance in another attribute has a higher rate of predictive accuracy....my workflow is in WEKA and so a compatible algorithm is needed.
I will love to interact with any coder who believes such a task can be accomplished.
cheers





Have you done something or it is just an idea ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Its an idea for mining out patterns that is evident in football data.





Its an idea for mining out patterns that is evident in football data.





Its an idea for mining out patterns that is evident in football data.





How do I solve the recurrence T(n) = T (n  1) + c substitution method?





Looks like a partial definition of a linear suite.
What do you want to solve ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





I have thought of an algorithm that would really aide the work I am doing but cannot think of a name for it to search if there is an online algorithm created for it that I could use.
Algorithm example + explanation: For the work I am doing I have lots of different amounts of money and a total figure. I know that the sum of some of these amounts will equal the total figure but I have no clue which amounts they are and am not too sure how many of these figures would reach the total. I would input the amounts of money and the total figure and the algorithm would have to evaluate every single combination of these amounts of money until it reached the total amount and would output which amounts of money were used to create that total.
I am not asking anyone to create this algorithm I am just asking whether there is a website with this algorithm on it that I could use or if this algorithm is really easy to create + therefore I could create it for myself.
Any comments would be helpful + please ask if you have any queries for clarity! Many thanks!





this is the "coin change problem".
but, it's not an exceptionally hard problem. and it's probably worth trying to think it through on your own.





You have a set of data, and you search which subset will match a criteria.
This is a classical problem, I am not sure there is a name to this problem, or as mentioned in previous answer, it is related to the coin change problem.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Hi.
I was recently interested in literature regarding what a good hash table load factor is for rehashing. Wikipedia mentions 0,7, 0,75 and 2/3, but with no explanation as to why performance degrades at these numbers.
The problem intrigued me, and I came to the conclusion that, mathematically speaking, the load factor threshold is at exactly log 2 (~0,7), which I found rather beautiful in it's own way.
I am posting this in case somebody else finds it interesting as I could not find any reference to a similar solution. Please also reply if you find any errors.

Chaining can be avoided and branch prediction exploited by predicting if a bucket is empty or not. A bucket is probably empty if the probability of it being empty exceeds 0,5.
Let s represent the size and n the number of keys added. Using the binomial theorem, the probability of a bucket being empty is:
P(0) = C(n, 0) * (1/s)^0 * (1  1/s)^(n  0).
Thus, a bucket is probably empty if there are less than
log(2)/log(s/(s  1)) keys.
As s reaches infinity and if the number of keys added is such that P(0) = 0,5, then n/s approaches log(2) rapidly:
lim (log(2)/log(s/(s  1)))/s as s > infinity = log(2) ~ 0,7.






Split the larger triangle into two rightangled triangles, and apply Pythagoras:
L1² = x² + y²
L2² = (X1  x)² + y² = X1²  2·X1·x + x² + y²
L2²  L1² = X1²  2·X1·x
2·X1·x = X1²  L2² + L1²
x = (X1²  L2² + L1²) / 2·X1
y = ± √(L1²  x²)
NB: there will be two solutions  one with a positive value for y , and one with a negative value.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
 Homer





Use Pythagoras.
Let Pen tip = P. We know L1, L2, X1.
Define line segments R1 > P = L1, R1 > x = A, (x,0) > P = B.
A^{2} + B^{2} = L1^{2}
We know the length of A is X, since it's (0,0) > (x,0), and we know length of B is y, since it's (x,0) to (x,y)
x^{2} + y^{2} = L1^{2}
Let R2 > P = L2, x > R2 = C
B^{2} + C^{2} = L2^{2}
A + C = X1 => C = X1  A
So we have
x^{2} + y^{2} = L1^{2}
y^{2} + (X1  x)^{2} = L2^{2}
Solve these and you get x and y
cheers
Chris Maunder





Im inputing three numbers of users choice
number 1
number 2
final number
what i want to find out is , how many combinations of number 1 and number 2 would result in final number = number1 *x + number2*y = final number.
I am using nested loops
int i;
int j;
long long int pocet=0; long long int one; long long int two; long long int last; long long int one_max;
long long int two_max;
long long int add=1; long long int reduc=1;
if((one%2==0) && (two%2==0)){
if(one>two){
add=two/2;
reduc=one/2;
}
}
one_max=last/one;
two_max=last/two;
for(i=0;i<=one_max;i+=add){
for(j=two_max;j>=0;j=reduc){
long long int tmp_one=(one*i);
long long int tmp_two=(two*j);
if(tmp_one+tmp_two==last){
two_max=j;
pocet++;
}
}
}
if i input these numbers
one = 10;
two = 13;
final =100;
the only possible combination of first two numbers to result in final number is
10 * 10 + 13 * 0
modified 7Nov15 11:37am.





First of all, I fear your code don't work or is not complete.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





this is not full code , its just half pseudo code for illustrating my problem , i can provide full code if it helps





If it's pseudo code, ho wdo you know it runs slow?





i have updated my question , i wrote actual code which does works slow





You should consider this
long long int MyFunc (long long int one, long long int two, long long int last) {
int i;
int j;
long long int pocet=0; long long int one_max;
long long int two_max;
long long int add=1; long long int reduc=1;
if((one%2==0) && (two%2==0)){
if(one>two){
add=two/2;
reduc=one/2;
}
}
one_max=last/one;
two_max=last/two;
for(i=0;i<=one_max;i+=add){
for(j=two_max;j>=0;j=reduc){
long long int tmp_one=(one*i);
long long int tmp_two=(two*j);
if(tmp_one+tmp_two==last){
two_max=j;
pocet++;
}
}
}
return pocet;
}
as the source code to provide. Because we can't use your source code as is. In the form of a function, we can do test without changing a single line in this code.
First remark: using int for i and j may be short and should be replaced with long long int to match other variables.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Here is code with first batch of changes. the code is changed to a function for practical reasons.
long long int MyFunc (long long int one, long long int two, long long int last) {
long long int i;
long long int j;
long long int pocet=0;
for(i=0;i*one <=last;i++){
if ((last  one*i )% two == 0) { j= (last  one*i) / two;
pocet++;
}
}
return pocet;
}
I just stick to the problem here.
I just take advantage of mathematics to change the equation as i is known. This should already improve the runtime.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





thanks for reply , i have also improved my code , but both , my and yours fail to be fast and calculate the number of combinatiosn when big numbers such as
5098109
25279297
36821491225502191
are inputed





If you compare speed of both solutions with smaller values, mine should consistently faster the yours.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





yes no doubt about that , but both takes very long time to calculate numbers with big values such as i posted earlier





To go further, change the code to print each solution in order and look at changes between solutions.
Try 3, 4, 150
Try 3, 4, 151
Try 3, 4, 153
And look at each set of answer, you should see a repeating patern. This what Harold is speaking about in http://www.codeproject.com/Messages/5156686/ReFastestwaytocountnestedloops.aspx[^]
And when you have a repeating pattern, you can know very fast the number of solutions without loop at all.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





That looks like Bézout's identity[^], the result depends on what algebraic structure you want to use, which is a bit unclear here. What size of integer do you want to consider?
You can see there what form the pairs of (i,j) take if they are solutions (called (x,y) on the wiki page). x increments in steps of b/gcd(a,b) and y decrements in steps of a/gcd(a,b). k can also go negative though. The problem then is counting how many of those things are in the valid range of your integer type. It has some weird edge cases but obviously you can do it without counting every possibility explicitly.





hello everyone... first of all im reading a book about algorithms analysis and im in the topic called counting the primitive operation of an algorithm
and the algorithm is finding the largest element in an array ....
and it comes up to this formula:
the best case is :
2 + 1 + n + 4(n  1) + 1 = 5n
and the worst case is
2 + 1 + n + 6(n  1) + 1 = 7n  2
my question is how does he come up to those answet ? sorry guys im not very good at math.. and im still working on my algebra skills
thanks guys for the help
this.is.the psuecode.that.have been used for the example.in the book
Algorithm arrayMax(A, n):
Currentmax = A[0]
for (i = 1; i < n  1; i++) do:
If CurrentMax < A[i] do:
CurrentMax = A[i]
return CurrentMax





Basic algebra:
Member 11897566 wrote: 2 + 1 + n + 4(n  1) + 1 = 5n
2 + 1 + n + 4(n  1) + 1
== 2 + 1 + 1 + n + 4(n  1)
== 4 + n + 4n  4
== 4  4 + 5n
== 5n
Member 11897566 wrote: 2 + 1 + n + 6(n  1) + 1 = 7n  2
2 + 1 + n + 6(n  1) + 1
== 2 + 1 + 1 + n + 6(n  1)
== 4 + n + 6n  6
== 4  6 + 7n
== 2 + 7n
== 7n  2
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
 Homer





hi Homer, thanks for the reply and for the effort to answer it. it makes a little more sense to me right now..
last request for you is can you please tell me what topic is this in algebra so that i could study it more...
very much thanks..





I'm not sure it really qualifies as its own topic. Rearranging expressions containing constants and variables is the most basic part of algebra, from which all other topics flow. This is usually covered fairly early on in any highschool maths course.
Here's a basic introduction to algebra[^] which might help.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
 Homer





Member 11897566 wrote: last request for you is can you please tell me what topic is this in algebra so that i could study it more...
Myself I doubt there is any point.
You are never going to use this as a professional programmer.
If you want to become a theoretical computer theory professor specializing in this then be assured.
1. You need to learn a lot more math including algebra
2. The field has been very well studied for a very, very long time so think long an hard if this particular aspect is what you want to specialize in.





How can this be done?
Polynomials(x^6+x^4+1) and (x^7+x^4+x^3+1) should be mutiplied in binarycoding and after this I should divide it with polynomial (x^8+x^4+x^3+x+1).
Please, any assistance would be appreciated :/





Look up GF(2^{k}) multiplication and division. Various implementations are also easily findable with google once you know that keyword.





Thank you! Found several pages of information. Now just have to study it





Not sure what you want to do. Do you have more details ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Here is the algorithm I'm stuck on (and sorry it's not in proper pseudocode):
a = number to be converted b = base to be converted from c = base to be converted to d = number of places in a (can use builtins such as len(str(a))
e = a  (a modulo (d * b)) to establish top digit f = e floor divided by c to establish number of digits in output number (works even if c > b) g = e modulo c for first digit or output number
...and this is where I get stuck
Please help.





Help with what? What is the assignment?
The difficult we do right away...
...the impossible takes slightly longer.





Where did you find this ?
Google not working ?
What test dataset have you tried ?
What is your language ?
You are wrong at step e ...
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Hi!! I got some information related on this as below but I was wondering what sort of problems exactly does this Fiestel Cipher Algorithm solves? Any ideas and resources specifically on problems aim to solve would be appreciated. Cheers!!
Related infos but did not exactly get regarding problems aim to solve:
• A Feistel network is a symmetric structure used in the construction of block ciphers. A block cipher is a deterministic algorithm operating on fixedlength groups of bits, called blocks. Block ciphers are important elementary components in the design of many cryptographic protocols, and are widely used to implement encryption of bulk data.
• Data Encryption Standard (DES) was the result of a research project lead by Horst Cipher in IBM which resulted in a cipher known as Lucifer.
• As with most encryption schemes, DES expects two inputs  the plaintext to be encrypted and the secret key. The manner in which the plaintext is accepted, and the key arrangement used for encryption and decryption, both determine the type of cipher it is. DES is therefore a symmetric, 64 bit block cipher as it uses the same key for both encryption and decryption and only operates on 64 bit blocks of data at a time5 (be they plaintext or ciphertext).





It does not solve problems, it is an algorithm for encrypting and decrypting information to allow for secure storage. transmission etc.





But surely storing and transmitting data securely is a problem that needs to be solved, and an encryption algorithm is a solution to that problem?
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
 Homer






Recently, a question on QA here about implementing a RockScissorsPaper (RSP) game [^], to which I responded, left me with a curiosity to see how efficiently/tersely I could implement the possible analysis of the result of game play.
Which got me interested in the more general question of how, given a complex matrix of values and criteria which can be expressed in typical De Morgan table form can be ... possibly ... analyzed by code in such a way that either an optimal implementation of the matrix (codegeneration) is generated, or, some set of heuristics is generated that the programmer can interpret and use to write optimized code.
To use the RSP possible outcomes as a simple example, and excluding the obvious condition that if two "players" select the same "object," the game is a tie:assume 0 => Rock , 1 => Scissors, 2 => Paper
0 1 true ... rock breaks scissors => player1 wins
1 2 true
2 0 true
0 2 false ... paper covers rock => player1 loses
1 0 false
2 1 false
Of course, it's straightforward to write a simple switch statement, or if/else/ chain to "solve" this.
"Eyeballing" such a table, and looking for "patterns" in the outcomes, the mind may naturally think about various boolean operations like XOR, or using modulo some number, looking for "heuristics;" look for "threshold" values that can "prune" the possible comparison matrix.
Looking further than this simple example, one can think about the complexity of an airfare reservations system where there might be twenty different factors resulting in the selection of the final airfare price from some list of pricing levels.
And, of course, the programmer will (hopefully) have (or create somehow) some clear description of the "business rules" that describe the calculation process.
Let's say the outcome in the airfare scenario is a matrix of 1000 combinations (to be conservative). To our brains it's pretty easy to look at the criteria and use the business rules to select the criterion (like passenger Age) that may have the most "impact" on the matrix of combinations: i.e., you'd want to first "prune" the matrix by a switch statement using Age as the selector.
And, it would be logical, as you eyeball the criteria to consider those with the fewest number of "states" and use testing those in the "outer" switch statements to reduce computation.
However, an interesting complication may be that some criterion with only one, or a few states may be, in practice, rarely of predictive value: that, imho, takes you into the analysis of the criterion based on context (worldknowledge, statistics of use, etc.). I want to exclude that from this post.
Then there are the interactions of variables; in the airfare scenario a discount for early booking may not apply to the fare calculation for accompanied children between age 5~11, for example. While some variables may be inherently "binary," such as, perhaps, the need for a wheelchair, many variables may have a number of "levels," like, for example, age broken out by infant, child, teen, adult, senior.
I'm sure that Decision Table theory which has been around for so long has generated some algorithms/heuristics for analyzing complex boolean matrices and optimizing code.
Appreciate your thoughts !
«I want to stay as close to the edge as I can without going over. Out on the edge you see all kinds of things you can't see from the center» Kurt Vonnegut.
modified 1Nov15 2:33am.





Problems of this sort I usually approach by first doing some data / frequency analysis.
Then start "slicing" (usually) from the variable that has the least unique values for a given context.
e.g. If I wanted to select all males in California, would I first slice on "gender" or on "State" (of residence)? The point is, it's hard to generalize on strategies and it all "depends". (This also applies to complex SQL queries which the "optimizer" isn't getting quite right since the optimizer depends on an a particular "execution plan").





I don't use a standard way to deal with this problem.
My solution is always context dependent and language dependent. No heuristics will do it for me.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





I know the brute force method. can someone help me find a good solution!!
Input Format
The first line contains an integer, T, which is the number of test cases. T test cases follow, each having a structure as described below:
The first line contains two spaceseparated integers, R and C, indicating the number of rows and columns in the grid G, respectively.
This is followed by R lines, each with a string of C digits, which represent the grid G.
The following line contains two tabseparated integers, r and c, indicating the number of rows and columns in the pattern grid P.
This is followed by r lines, each with a string of c digits, which represent the pattern P.
Constraints
1≤T≤5
1≤R,r,C,c≤1000
1≤r≤R
1≤c≤C
example
INPUT
2
10 10
7283455864
6731158619
8988242643
3830589324
2229505813
5633845374
6473530293
7053106601
0834282956
4607924137
3 4
9505
3845
3530
15 15
400453592126560
114213133098692
474386082879648
522356951189169
887109450487496
252802633388782
502771484966748
075975207693780
511799789562806
404007454272504
549043809916080
962410809534811
445893523733475
768705303214174
650629270887160
2 2
99
99
output
Yes
No
pls help!!



