Binomial coefficient – C#

Binomial coefficient C#

What is called a binomial Coefficient in two ways-a Symbol of the Newton?

Sometimes a situation where we need to determine the number of combinations of the elements of the collection. This is a situation that, contrary to appearances, it happens very often, but not always, there is a need to make calculations, and decisions are made intuitively.

For example, you can consider several situations where such choice is made:

-Released a series of 4 collectable cards of famous athletes, and we can afford only 2 of them. With this set you can choose the card numbers {1,2}, {1,3}, {1.4}, {2,3}, {2,4}, {3,4}, and so we can make 6 different choices.

-Favourite number game draws 5 non-repeating numbers from 60 available. The number of combinations is much greater than in the previous example, and print all it would take a lot of space in this article.

-The company employs 100 workers, and half of them will receive earlier this month. How many combinations of employees can check here to occur? Many employers do not reflects on this and doing your own breakdown.

The Definition Of The Binomial Coefficient

What if, however, we would like to find out how much we really choice and what are they? Then with the formula defined by Newton, called Binomial or binomial coefficient. This is a function of two arguments which are nonnegative integers. The solution is Newton’s Symbol how many possible combinations of your choice can be obtained by selecting the k elements from a set of n-element set. The definition of the model is as follows:

Symbol_Newtona binomial coefficient-Binomial

The result of Newton’s Symbol in the code

The code presented represents the solution to the above formula, without the use of recursion for the strong. It is applied in the relationship that is created at the time of shortening parts counter with more the product of denominator. Clarification on a particular example should dispel doubts. Counter in Newton’s Symbol is always going to be greater than the denominator. Selecting n = 8 and k = 5 you get a fraction:

symbol_newtona_przykład binomial coefficient-BinomialReducing the counter (8!) with a higher factor of the denominator (5!) we get:

-in the numerator 6 * 7 * 8 (because 1 * 2 * 3 * 4 * 5 will be shortened),

-to use in the denominator of 1 * 3! (so 1 * 2 * 3).

In the following code, the number 1 is multiplied by another counter values (6 * 7 * 8) and divided by the following elements of the denominator (1 * 2 * 3). This relationship simplifies entry and working code for one condition and one loop.

Group code combinations

Sometimes information about the number of possible combinations is not sufficient and we would like to find out what items they make up. The code is relatively simple in the case when it is the number of elements that has be drawn and how much is available. The situation becomes more complicated when the function is supposed to be universal and useful for any values.

The following is the code for the function that gets the previously presented the parameters n and k, and returns an array of arrays. Returns an array of typed array stored in each row with the values of belonging to the group. The rows so you can interpret it as just another of the group, and their columns as drawn in them.

The algorithm requires clarification, but frogs better understand it also follows the example of n = 6, k = 4.

Define drawn values is done in the while loop. Her first call stores originally defined group (1, 2, 3, .., k-in our example 1, 2, 3, 4). Subsequent calls to the loop increases the last item in the original array, up to the maximum value on it equal to n (i.e.-> 1, 2, 3, 5-> 1, 2, 3, 6). When this value, the variable is decremented by 1, which creates a reference to an element with a lower index (at this stage, it is the value of the 3 position equal to 3, which is changed to 4). Elements with larger indices from it are incremented by 1 in respect of a new variable (1,2 remain unchanged, 4 amended a moment ago and subsequent elements 4 + 1 = 5, which gives another group of 1, 2, 4, 5), and the variable p is again a value of k so that the reference to the last element.

Referencing elements with more and smaller indexes is carried out when the last item assumes the maximum value more than once, for the consecutive elements (eg. for the first time for a group of 1, 2, 4, 6 where p is reduced to 3, the second time 1, 2, 5, 6 where p is reduced to 2). The last group of reduce variable to 0 and thanks and we counter that this is the last of the possible combinations.

View all combinations

The following code was introduced in the collector a string variable data on the composition of the groups and their numbering in a manner pleasing to the human eye:

1-1 2 3 4 5
2-1 2 3 4 6
3-1 2 3 4 7
4-1 2 3 4 8

Loading Facebook Comments ...

Leave a Reply