Java Programming

Permutations and combinations are two separate things. Although we often use them interchangeably in English, we need a more precise definition in mathematics, such that ABC and CBA are regarded as being two different permutations of the same combination. In other words, the order of the elements is important in a permutation but is completely irrelevant in a combination.

First we have to define what it means to create a combination or permutation. Typically we have a set from which we must make a subset. The number of elements in the set is typically defined using the variable n while the number of elements in the subset is r. Thus we can formally define a permutation mathematically using the function P(n,r) and a combination as C(n,r).

We must also consider whether elements may be repeated within a combination or a permutation. For instance, when selecting numbers for a lottery, no number may be repeated in any combination but in a 4-digit combination lock, any digit may be repeated in a permutation.

Note that a combination lock is really a permutation lock in mathematics and is the perverse way of remembering the mathematical difference between a combination and a permutation.

Thus we have 4 possible variations to cater for. In order of difficulty, they are:

1. Permutations with repetition
2. Permutations without repetition
3. Combinations without repetition
4. Combinations with repetition

Let's deal with them one at a time.

1. Permutations with repetition

To calculate P(n,r) with repetitions, for every selection, r, there are always n possibilities, thus we have n^r permutations.

In a 3-digit combination lock, each digit has ten possibilities, 0 through 9, so there are 10^3=10x10x10=1000 permutations. This stands to reason because the permutations form all of the numeric values from 000 through to 999, which is 1000 different values.

In C, we can write this function as:

unsigned long long permutations (unsigned long long n, unsigned long long r) {

return pow(n,r); /* use standard library function */

}

2. Permutations without repetition

To calculate P(n,r) without repetitions we must reduce the set by one element each time we make a selection. If we go back to our 3-digit combination lock, we have 10 choices for the first digit which leaves 9 choices for the next and 8 for the next. So instead of 10x10x10=1000 permutations we only have 10x9x8=720 permutations.

Although fairly simple to work out in this case, we need a formula that is generalised to cater for all cases, just as n^r works for all permutations with repetitions.

We can see that 10x9x8 is the initial product of 10! (factorial 10) which is 10x9x8x7x6x5x4x3x2x1. So we need a formula that ignores everything after the 8. The portion after the 8 is 7x6x5x4x3x2x1 which is 7! and we can calculate that from (n-r)!=(10-3)!=7!

Having determined the portion we need to ignore, the rules of multiplication and division state that if we multiply by x and subsequently divide by x, then the two x's must cancel each other out. Thus we get:

10!/7!=(10x9x8x7!)/7!=10x9x8=720

Using formal notation, P(n,r) without repetition is therefore n!/(n-r)!

In C, we must first write a function to calculate factorials:

unsigned long long factorial (unsigned long long n) {

return (n>1)?factorial(n-1):1; /* recursive function */

}

With that in place, we can now write a function to handle permutations without repetitions:

unsigned long long permutations_norep (unsigned long long n, unsigned long long r) {

return factorial(n)/factorial(n-r);

}

3. Combinations without repetition

C(n,r) without repetition is simply an extension of P(n,r) without repetition. Every combination of r has r! permutations, so if we divide P(n,r) by r! we will get C(n,r). Expressing this formally, C(n,r) without repetition is n!/((n-r)!r!)

Going back to our 3-digits from 10, there are 10!/((10-3)!3!)=10!/(7!3!)=(10x9x8x7!)/(7!3!)=(10x9x8)/3!=720/6=120 combinations without repetition.

Using the factorial function shown above, we can write a C function to handle combinations without repetition:

unsigned long long combinations_norep (unsigned long long n, unsigned long long r) {

return factorial(n)/(factorial(n-r)*factorial(r));

}

4. Combinations with repetition

Combinations with repetition is the hardest concept to wrap your head around.

Going back to our 3-digits from 10, let's begin enumerating all the combinations so we can verify the answer at the end. We start by enumerating all those that combinations that begin with a 0:

000, 001, 002, 003, 004, 005, 006, 007, 008, 009

011, 012, 013, 014, 015, 016, 017, 018, 019

022, 023, 024, 025, 026, 027, 028, 029

033, 034, 035, 036, 037, 038, 039

044, 045, 046, 047, 048, 049

055, 056, 057, 058, 059

066, 067, 068, 069

077, 078, 079

088, 089

099

Note that there is no 010 because it is a permutation of 001. Similarly with 021 which is a permutation of 012. As a result of this, each row has one less combination than the one above. Thus there are 10+9+8+7+6+5+4+3+2+1=55 combinations.

If we now enumerate all those that begin with a 1, we see a similar pattern emerges:

111, 112, 113, 114, 115, 116, 117, 118, 119

122, 123, 124, 125, 126, 127, 128, 129

133, 134, 135, 136, 137, 138, 139

144, 145, 146, 147, 148, 149

155, 156, 157, 158, 159

166, 167, 168, 169

177, 178, 179

188, 189

199

This time we have 9+8+7+6+5+4+3+2+1=45 combinations.

Following the same logic, the next section must have 8+7+6+5+4+3+2+1=36 combinations, followed by 28, 21, 15, 10, 6, 3 and finally 1. Thus there are 220 combinations in total.

The formula to work this out is quite complex, however it becomes simpler when we look at the problem in a different way. Suppose we have 10 boxes and each box holds at least 3 of the same digit. We can number these boxes 0 through 9 according to those digits. Let us also suppose that we can only move in one direction, from box 0 to box 9, and we must stop at every box along the way. This means we must make 9 transitions from one box to the next.

While we along the row, we carry a tray with 3 slots. Whenever we stop at a box (including box 0 where we start from) we can either pick a number from the box or we can move onto the next box. if we pick a number, we place it in the first slot. We can then pick another or we can move on. When we have filled all the slots, we simply move on until we reach box 9. If we reach box 9 and still have slots available, we must pick as many 9s as we need to fill the remaining slots.

It probably sounds far more complex than it really is. By imagining a selection being done this way we can create a convenient binary notation. For instance, if we say that 1 means pick a number and 0 means move onto the next box, the sequence 101010000000 would tell us we selected the combination 123 while the sequence 000000000111 tells us we selected 999. Every combination is therefore reduced to 12-bit value containing exactly three 1s and nine 0s, and it is these specific combinations we are actually looking for.

C(n,r) with repetition is formally expressed as (r+n-1)!/(r!(n-1)!)

If we plug in the actual numbers we find:

=(3+10-1)!/(3!(10-1)!)

=12!/(3!9!)

=(12x11x10x9!)/(3!9!)

=(12x11x10)/3!

=1320/(3x2x1)

=1320/6

=220 combinations with repetition.

This type of problem might be expressed in other ways. For example, how many different ways can we fill a box with 100 sweets from 30 different sweets. C(n,r) is C(30,100) thus we find:

=(100+30-1)!/(100!(30-1)!)

=129!/(100!29!)

=(129x128x127x...x101x100!)/(100!29!)

=(129x128x127x...x101)/29!

=5.3302324527079900778691094496787e+59/8,841,761,993,739,701,954,543,616,000,000

=60,284,731,216,266,553,294,577,246,880 combinations with repetition.

In C we can use the following function in conjunction with the factorial function shown earlier:

unsigned long long combinations (unsigned long long n, unsigned long long r) {

return factorial(n+r-1)/(factorial(r)*factorial(n-1));

}

We might also have similar problems with an additional restriction. For instance, we might be asked to select 100 sweets from 30 different sweets selecting at least 1 of each type. This reduces the number of slots to 100-30=70 but we have the same number of transitions, so we get:

=(70+30-1)!/(100!(30-1)!)

=99!/(70!29!)

=(99x98x97x...x71x70!)/(70!29!)

=(99x98x97x...x71)/29!

=7.7910971370578048745872324992773e+55/8,841,761,993,739,701,954,543,616,000,000

=8,811,701,946,483,283,447,189,128 combinations with repetition.

To accommodate this caveat, we can use the following function instead:

unsigned long long combinations2 (unsigned long long n, unsigned long long r) {

return factorial(n-1)/(factorial(r)*factorial(n-1));

}

There are 8 primitive data types: byte, short, int, long, float, double, boolean, char

any other data type in Java can be considered non primitive data type.

Ex: String

String data type can also be known as the primitive data type because it is already provided by the Java language, since it is not a data type but its a class, but as we know that we can use the classes as types for the variables/instance variables, as we use while creating an object of any class, hence the classes that we create and use them as a datatype are known as non-primitive datatype....

for any query, mail me on engineer.sooraj@gmail.com or call me on +92-331-350-6956.....

Overloaded Constructors

Overloading a constructor means typing in multiple versions of the constructor, each having a different argument list, like the following examples:

class Car {

Car() { }

Car(String s) { }

}

The preceding Car class has two overloaded constructors, one that takes a string, and one with no arguments. Because there's no code in the no-arg version, it's actually identical to the default constructor the compiler supplies, but remember-since there's already a constructor in this class (the one that takes a string), the compiler won't supply a default constructor. If you want a no-arg constructor to overload the with-args version you already have, you're going to have to type it yourself, just as in the Car example.

Overloading a constructor is typically used to provide alternate ways for clients to instantiate objects of your class. For example, if a client knows the Car name, they can pass that to a Car constructor that takes a string. But if they don't know the name, the client can call the no-arg constructor and that constructor can supply a default name. Here's what it looks like:

1. public class Car {

2. String name;

3. Car(String name) {

4. this.name = name;

5. }

6.

7. Car() {

8. this(makeRandomName());

9. }

10.

11. static String makeRandomName() {

12. int x = (int) (Math.random() * 5);

13. String name = new String[] {"Ferrari", "Lamborghini",

"Rover", "Spyker",

"Lotus"}[x];

14. return name;

15. }

16.

17. public static void main (String [] args) {

18. Car a = new Car();

19. System.out.println(a.name);

20. Car b = new Car("Proton");

21. System.out.println(b.name);

22. }

23. }

Running the code four times produces this output:

% java Car

Lotus

Proton

% java Car

Ferrari

Proton

% java Car

Rover

Proton

% java Car

Ferrari

Proton

There's a lot going on in the preceding code. Figure 2-7 shows the call stack for constructor invocations when a constructor is overloaded. Take a look at the call stack, and then let's walk through the code straight from the top.

• Line 2 Declare a String instance variable name.

• Lines 3-5 Constructor that takes a String, and assigns it to instance variable name.

• Line 7. Assume every Car needs a name, but the client (calling code) might not always know what the name should be, so you'll assign a random name. The no-arg constructor generates a name by invoking the makeRandomName() method.

• Line 8 The no-arg constructor invokes its own overloaded constructor that takes a String, in effect calling it the same way it would be called if client code were doing a new to instantiate an object, passing it a String for the name. The overloaded invocation uses the keyword this, but uses it as though it were a method name, this(). So line 8 is simply calling the constructor on line 3, passing it a randomly selected String rather than a client-code chosen name.

• Line 11 Notice that the makeRandomName() method is marked static! That's because you cannot invoke an instance (in other words, nonstatic) method (or access an instance variable) until after the super constructor has run. And since the super constructor will be invoked from the constructor on line 3, rather than from the one on line 7, line 8 can use only a static method to generate the name. If we wanted all Cars not specifically named by the caller to have the same default name, say, "Ford," then line 8 could have read this("Ford"); rather than calling a method that returns a string with the randomly chosen name.

• Line 12 This doesn't have anything to do with constructors, but since we're all here to learn...it generates a random integer between 0 and 4.

• Line 13 We're creating a new String object (just a single String instance), but we want the string to be selected randomly from a list. Except we don't have the list, so we need to make it. So in that one line of code we

1. Declare a String variable, name.

2. Create a String array (anonymously-we don't assign the array itself to anything).

3. Retrieve the string at index [x] (x being the random number generated on line 12) of the newly created String array.

4. Assign the string retrieved from the array to the declared instance variable name. We could have made it much easier to read if we'd just written

5. String[] nameList = {"Ferrari", "Lamborghini", "Rover", "Spyker","Lotus"};

6. String name = nameList[x];

• Line 18 We're invoking the no-arg version of the constructor (causing a random name from the list to be passed to the other constructor).

• Line 20 We're invoking the overloaded constructor that takes a string representing the name.

The key point to get from this code example is in line 8. Rather than calling super(), we're calling this(), and this() always means a call to another constructor in the same class. OK, fine, but what happens after the call to this()? Sooner or later the super() constructor gets called, right? Yes indeed. A call to this() just means you're delaying the inevitable. Some constructor, somewhere, must make the call to super().