Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Number of permurations an memory problems.

1. ## Number of permurations an memory problems.

Hello guys!

I'll give you the big picture of what I'm doing. I'm solving a combinatorial optimization problem. I find an initial solution and then try to improve it with some heuristics. One of them involves some local search techniques. Everything works well except that I encounter a memory problem. My local search works only for small instances of the problem (ie up to 600 nodes). For larger instances I get an OutOfMemoryError exception. The exception occures in the method that finds the "neighbors" of the current solution. You can think of this method as one that finds all possible permutations of a list (all possible triplets or quadraplets of arcs, more precisely).
Each neighbor-permutation is saved in an array (since I know its length) and the whole neighborhood in an ArrayList.
My thought is to find the number of permutations P(n,r) so that I can use an array for the neighborhood or at least an ArrayList of initial size -since the exception occurs while the ArrayList is increasing its size, ie copies its internal array to a bigger one, and I think it will avoid that if it has an initial size.

I implemented a recursive method to calculate P(n,r)
```public static long factorial(long n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}

//P(n,r) = n! / (n - r)!
public static long permutations(long n, long r) {
long arithmitis = factorial(n); //n!
long paron = factorial(n - r); //(n - r)!

return arithmitis / paron;
}```

This method works fine for a relatively small n (r is always 3 or 4) but when I try to find P(120,3) for example -which is near to what I will have to find for my program- it crashes, because the values of factorial(n) factorial(n-r) are very large and cannot be held in the long variables.

Here are my questions:
Firstly, do you think that saving the neighborhood in an array or an ArrayList with initial size would improve my memory problem or I'm just wasting my time?
And secondly, any thoughts on how to make the permutations(long n, long r) method to work?

PS:I have used the -Xmx option to increase the VM's heap space with some good results.  Reply With Quote

3. ## Re: Number of permurations an memory problems.

What is the actual error you're getting?

What happened when you tried increasing the initial size?  Reply With Quote

4. ## Re: Number of permurations an memory problems. Originally Posted by KevinWorkman What is the actual error you're getting?
When I try to solve a large instance of the problem I get the following error:
```Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Unknown Source)
at java.util.Arrays.copyOf(Unknown Source)
at java.util.ArrayList.grow(Unknown Source)
at java.util.ArrayList.ensureCapacityInternal(Unknown Source)
at msp.MSPImprover.opt_3(MSPImprover.java:61)
at msp.MSPImprover.opt_3(MSPImprover.java:114)
at msp.MSPImprover.opt_3(MSPImprover.java:114)
at msp.MSPSolver.main(MSPSolver.java:658)```

That's why I thought it would help if I used an ArrayList(int initialCapacity)
To be able to find the initialCapacity I tried the recursive method I posted which for large numbers of n throws the following exception:
```Exception in thread "main" java.lang.ArithmeticException: / by zero
at msp.MSPImprover.permutations(MSPImprover.java:411)
at msp.MSPImprover.main(MSPImprover.java:415)```

I did some debugging and found out that after some (big) number both variables arithmitis and paron become 0. Originally Posted by KevinWorkman What happened when you tried increasing the initial size?
I didn't tried that externally. I ment that the ArrayList increases its internal array's size (ie copies its elements to a bigger one).

Hope that makes sense.  Reply With Quote

5. ## Re: Number of permurations an memory problems.

Well, you're running out of memory. That's a different issue than trying to store a long in an int, and it probably won't be solved by increasing the initial capacity of your data structure- unless you're in a weird situation where the final size of your data structure is within the limits of memory, but Java is increasing it to a size that's outside the limits of memory.. but that's unlikely.

More likely, you're going to have to take a look at your algorithm and find ways of taming the memory consumption. How big does your data structure have to become in order to accommodate all the permutations? Do you really need to make so many copies?  Reply With Quote

6. ## The Following User Says Thank You to KevinWorkman For This Useful Post:

andreas90 (February 7th, 2013)

7. ## Re: Number of permurations an memory problems. Originally Posted by KevinWorkman How big does your data structure have to become in order to accommodate all the permutations?
It should be equal to the number of the permutations , if I'm getting right what you asked. Originally Posted by KevinWorkman Do you really need to make so many copies?
You mean if I need all the permutations? Yes, I need them because I want to search every possible neighbor. That was my purpose. At this point, I don't want to improve the computational time or the memory usage against the results (even though the way it is now it can be applied only in small instances - but it gives optimal solutions regarding the local search).
I'm planning to implement some more sophisticated techniques and algorithms that will be able to give good results in large instances of the problem.  Reply With Quote

8. ## Re: Number of permurations an memory problems.

How many permutations are you generating though? How large is each permutation?

I'm also asking whether you need to copy the data as many times as you do, since you mentioned copying arrays in your first post. You can generate different arrays without actually copying the values inside them. Compare an array that points to a million instances of String that contain the same text versus an array that contains a million references to a single String instance.

I don't actually know the answers to these questions, since you haven't posted an SSCCE, so I'm just guessing. But it's where I'd look if I were you.  Reply With Quote

9. ## Re: Number of permurations an memory problems. Originally Posted by KevinWorkman How many permutations are you generating though? How large is each permutation?

I'm also asking whether you need to copy the data as many times as you do, since you mentioned copying arrays in your first post. You can generate different arrays without actually copying the values inside them. Compare an array that points to a million instances of String that contain the same text versus an array that contains a million references to a single String instance.

I don't actually know the answers to these questions, since you haven't posted an SSCCE, so I'm just guessing. But it's where I'd look if I were you.
I didn't explain well what I'm doing. This is the method that causes the java.lang.OutOfMemoryError exception I posted in post#2. I generate P(n,r) permutations which for the following method is P(forObj.size, 4). If you are asking about the actual number of permutations the exception occurs for n > 60 approximately.
```public ArrayList<Edge[]> getQuadraplets(ArrayList<Edge> forObj) {

for (int i = 0; i < forObj.size(); i++) {
for (int j = 0; j < forObj.size(); j++) {
for (int k = 0; k < forObj.size(); k++) {
for (int l = 0; l < forObj.size(); l++) {
if ((i != j && i != k && i != l && j != k && j != l && k != l)) {
Edge[] qudraplet = new Edge;
qudraplet = forObj.get(i);
qudraplet = forObj.get(j);
qudraplet = forObj.get(k);
qudraplet = forObj.get(l);

}
}
}
}
}
}```

As you can see I'm not copying any array in my code. I thought that if I gave quadraplets an initial size that would improve my memory use.
I tested that and it didn't help - as you had told me in post#3.

I realized that I can accomplish what I want to do with a different approach which will hopefully decrease my memory consumption. I'm working on the new design right now. I will update the thread when I complete the tests and have some results.  Reply With Quote

10. ## Re: Number of permurations an memory problems.

You've specified n, but how do your permutations grow? Is it really (60!), which is 8.3209871e+81, which is definitely not going to fit in memory? Or is it something else?

Basically, as n gets bigger, how does the size of quadraplets grow?  Reply With Quote

11. ## Re: Number of permurations an memory problems. Originally Posted by KevinWorkman You've specified n, but how do your permutations grow? Is it really (60!), which is 8.3209871e+81, which is definitely not going to fit in memory? Or is it something else?

Basically, as n gets bigger, how does the size of quadraplets grow?
The number of permutations is P(n,r) = n!/(n-r)!
So for n=60 and r=4 I have P(60,4) = 60! / (60 - 4)! = 11703240 permutations.

I tried the same method with each quadraplet being a String instead of an Edge array but I got again a java.lang.OutOfMemoryError exception. That's why I'll try a new approach (without trying to find all the permutations).  Reply With Quote

12. ## Re: Number of permurations an memory problems. Originally Posted by andreas90 The number of permutations is P(n,r) = n!/(n-r)!
So for n=60 and r=4 I have P(60,4) = 60! / (60 - 4)! = 11703240 permutations.
I get it: You want to calculate the number of permutations of (n,4) in Java, where n can be something on the order of 104 (as indicated in your first post). Then you can specify the initial size of the ArrayList of arrays of Edges so that the loop does not have to spend time garbage collecting and re-allocating space as the ArrayList grows.

Now, here's the thing: The largest number whose factorial fits into a Java long variable (64-bit signed integer) is 20, so you certainly can't use Java's built-in integer or long data types to calculate P(104,4) with a naive implementation of the expression 104!/(104-4)! = 104!/100!

However...

If you think of what happens if you divide 104 factorial by 100 factorial, you should realize that the result is equal to the first r terms of the numerator: 104*103,*102*101.

See? The other factors in the numerator are 100*99*98*....*1, and they get canceled exactly by the 100 factorial in the denominator. It makes no sense to multiply 100*99*98* ... *1 in both numerator and denominator then cancel that much out by division.

In general, the scheme is
```P(n,r) = n * (n-1) * (n-2) * ... * (n-r-1)
|<----------- r terms ----------->|```

You can do this programmatically by starting with a product value of 1 and making a loop that is traversed r times.

You want to multiply the product by n the first time through the loop and n-1 the second time and n-2 the third time, etc.

Bottom line: If the loop counter is i, start with i = 0 and multiply by (n-i) each time through the loop. You never have to explicitly calculate the factorial of anything.

Next... Originally Posted by andreas90 I tried the same method with each quadraplet being a String instead of an Edge array but I got again a java.lang.OutOfMemoryError exception
I don't know, exactly, what your "real" Edge object is, but let's suppose its object field is an array of four floats. (Each float takes four bytes of memory in Java.)

Now, here's the thing: I'll try to compile and execute a "toy" program that uses an Edge consisting of an array of four floats:
```public class Z {
public static void main(String [] args) {
ArrayList<Edge> x = new ArrayList<Edge>();

//
// Do whatever you need to do to populate the ArrayList
//
//   In other words:
//   Put code here to add Edges to the ArrayList
//
//       code, code, code, code, ...
//
// Suppose it turns out to have 110 elements
//

int n = x.size();

int np = numPerms(n, 4); // Calculate P(n,4) with a scheme like the one I described

System.out.println("For the ArrayList x:");
System.out.printf("  Number of Edges    = %4d\n", x.size());
System.out.printf("  Number of bytes    = %4d\n\n", new Edge().arraySizeInBytes()*x.size());
System.out.printf("Number of permutations P(%d,4) = %d\n\n", n, np);

System.out.printf("For the ArrayList of Edge arrays, ax, with P(%d,4) elements:\n", n);
System.out.printf("  Number of elements = %10d\n", ax.size());
System.out.printf("  Number of Edges    = %10d\n", new Edge().arraySize()*ax.size());
System.out.printf("  Number of bytes    = %10d\n", new Edge().arraySizeInBytes()*ax.size());```

I created methods for my Edge class that report the size of the array and the number of bytes in the array

Now when I compile like this:

```javac Z.java
javac Z```

I get the following
```For the ArrayList x:
Number of Edges    =  110
Number of bytes    = 1760

Number of permutations P(110,4) = 138556440

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.ArrayList.<init>(ArrayList.java:132)
at Z.main(Z.java:32)```

Apparently the default heap space for the JVM is not large enough to hold an ArrayList consisting of 138556440 arrays of four floats.

As you already know, you can give it more heap space by using the -Xmx java command line option. How many bytes do you think will be needed by the ArrayList of P(110,4) arrays of floats?

To get 2500 Megabytes heap space, the command that I used is
`java -Xmx2500m Z`

And now the output is
```For the ArrayList x:
Number of Edges    =  110
Number of bytes    = 1760

Number of permutations P(110,4) = 138556440

For the ArrayList of Edge arrays, ax, with P(110,4) elements:
Number of elements =  138556440
Number of Edges    =  554225760
Number of bytes    = 2216903040```

(This is for java version 1.6.0_24 on my 32-bit Centos 6.3 Linux workstation.)

For your program, if an Edge object takes more memory than an array of four floats, your requirements will be larger.

Note that the maximum heap size that the JVM can use is Operating System dependent and implementation dependent. For a 32-bit Linux system, the maximum is (probably) something between 2500 and 2600 Megabytes (roughly 2 Gigabytes), assuming you have a sufficiently large swap partition. For 64-bit Linux systems it is (probably) much larger, but, again, it will (probably) be limited by the size of the swap partition.

Note that if you ask for more heap space than your system supports, you will get an error message to that effect. For example, on my system:
``` java -Xmx2700m Z
Error occurred during initialization of VM
Could not reserve enough space for object heap
Could not create the Java virtual machine.```

The semi-final note:
The maximum amount of heap space is not (that's not) limited by the actual amount of physical RAM your system has, but, generally speaking, performance is better for larger amounts of RAM than for smaller amounts. Originally Posted by andreas90 new approach (without trying to find all the permutations).
The final note: Maybe that's a good idea, if you can do it. My "toy" test program wasn't very useful, and, in fact, there were several problems that would make me abandon attempts to keep all of the more than 100 million permutations in memory at the same time.

I mean, just because it can allocate storage for all of those Edge arrays, doesn't mean that it can actually process them in a useful way and in a reasonable amount of time. I really wouldn't try it if there were any other way to approach the problem.

Cheers!

Z  Reply With Quote

13. ## The Following 2 Users Say Thank You to Zaphod_b For This Useful Post:

andreas90 (February 8th, 2013), curmudgeon (February 13th, 2013)

14. ## Re: Number of permurations an memory problems.

Hello Z!

Thanks for the time you spent on my problem. I tried calculating P(n,r) as you suggested and it worked as I thought. I don't get a java.lang.OutOfMemoryError exception in the internal processes of the ArrayList as before. However I still get one. Unfortunately, my Edge keeps a lot more data and my 32-bit win7 machine can only accept a 1500m parameter in the -Xmx option. Therefore I'm still trying to get my new approach to work.

PS: Your posts and work is what this kind of forums is all about. Happy to see you here. Keep up the great work.  Reply With Quote

15. ## Re: Number of permurations an memory problems.

OK, a few things. If you want to store every single possible combination, you're going to have to post specs, specifcally, how much RAM you have. I'll take a guess at 3 gigs. Windows 7 takes about 1.5 gigs depending on what's running. I have 12 gigs of RAM and can't store, as a boolean (1-bit) an array larger than... well idk, but not large enough that I need. You're going to have to find another way. Now, my question to you, do you need to record how many combinations of something or the number of combinations. Also, are you looking for combinations or permutations as there a LOT more permutations for a set than there are combinations. There are also ways around the primitive types that allow the more range than a double and more precision than a long, but it depends on what you need to do.  Reply With Quote

16. ## Re: Number of permurations an memory problems.

Hello aesguitar!

You are right about my RAM, it's 3GB. As you can see from the code I posted I keep the permutations, not combinations. My new approach involves finding the combinations (which are far less than the permutations as you pointed out). I know my workarounds (even with combinations) are limited by my memory. I just want to be able to apply my methods in larger instances of the problem. ie now I can apply them in instances with 500 nodes approximately, I wish I could apply them in instances up to 1000 nodes - I know it's impossible with 5000 nodes.  Reply With Quote

17. ## Re: Number of permurations an memory problems.

Ok, what's your purpose is storing the combinations? Are you trying to find the number of combinations or permutations, or are you actually trying to store all the combinations for whatever reason? If you are simply trying to find the number of combinations or permutations, there are some easily code-able combinatric formulas that you can use.  Reply With Quote

18. ## Re: Number of permurations an memory problems. Originally Posted by aesguitar Ok, what's your purpose is storing the combinations? Are you trying to find the number of combinations or permutations, or are you actually trying to store all the combinations for whatever reason? If you are simply trying to find the number of combinations or permutations, there are some easily code-able combinatric formulas that you can use.
Unfortunately I need the combinations/permutations themselves. Finding the number of them was a "trick" to improve the time and memory usage. ie using an ArrayList with initial size (which is the number of permutations) to store all the permutations.  Reply With Quote

19. ## Re: Number of permurations an memory problems.

I saw you were using nested for loops

```for(/*conditions blah blah blah*/)
{
for(/*conditions blah blah blah*/)
{
for(/*conditions blah blah blah*/)
{
for(/*conditions blah blah blah*/)
{
}
}
}
}```

What you could try is every nth iteration of the top for loop, write the contents of the ArrayList to a text file. the clear the ArrayList. It'll solve the Java heap issue and it will save the permutations.  Reply With Quote

20. ## The Following User Says Thank You to aesguitar For This Useful Post:

andreas90 (February 20th, 2013)

21. ## Re: Number of permurations an memory problems. Originally Posted by aesguitar What you could try is every nth iteration of the top for loop, write the contents of the ArrayList to a text file. the clear the ArrayList. It'll solve the Java heap issue and it will save the permutations.
Unfortunately, at some point I'll need all the permutations together in the ArrayList to do some stuff with them, so the exception may be avoided when I'm generating them but it will occur when I'll try to read the text file. Also, writing to and reading from the text file will effect the computational time of my program.

I'm marking this thread as solved as the first part of my problem (calculating P(n,r)) is solved and the second (OutOfMemoryError) cannot be solved with my approach. I'll start a new thread if I have problems with the new approach I'm working on.

Thanks again to anyone contributed to this thread.  Reply With Quote

22. ## Re: Number of permurations an memory problems.

Create an arraylist of files containing the permutations, then simply get the required permutations from the containing file.  Reply With Quote

23. ## Re: Number of permurations an memory problems. Originally Posted by aesguitar Create an arraylist of files containing the permutations, then simply get the required permutations from the containing file.
As I said in my previous post this will effect the computational time of the program.
In each run of the algorithm, the method that creates the permutations is called many times. Therefore the computational time will be increased if I write the permutations and then read them.
I should note that the computational time of the algorithm is very important since this is how I'm measuring how "good" it is (along with the results - the cost of the solution it returns).  Reply With Quote

24. ## Re: Number of permurations an memory problems.

The only other way I could think of is to create a 2d array. I don't know how that effects how much memory is available though.  Reply With Quote

25. ## Re: Number of permurations an memory problems.

I have given up the approach with the permutations since it seems like a dead end. I'm working on a different approach now.  Reply With Quote