Better way to create samples

Question

I've done this piece of code for creating all possible samples without repetitions, but I think that it is a so heavy algorithm because every time I call this recursive function I create a new vector that is passed to it. What means create any samples without repetitions? it means creating every combination given a population. Is there a way for making this algorithm faster?

Here is the algorithm and the description:

As already said, this function creates samples without repetitions recursively. If n, that is the number of elements that should be found, is equals 0 I print the sample.

Else to the sample that is passed I add the elements of the population that there aren't yet in the combination in a way that there should't be samples that are equals between every samples(I have to create a vector for everyone of this new samples), and I call the function with this new sample and n(the number of element to be found) decremented and incrementing the element from wich I'll start to add.

private static void distribuzioneInBlocco(int n, int firstElementConsidered, Vector<Float> population, Vector<Float> sample){
 // exit condition, when n equals 0 the fuction doesn't self-calls
 if(n==0){ 
 JOptionPane.ShowMessageDialog(null, sample);
 return;
 }
 // for every element of the population the function adds this element
 // at the previous combination
 for(int x = firstElementConsidered; x<population.size();x++){
 Vector<Float> aggiunta = new Vector<Float>(sample);
 aggiunta.add(population.elementAt(x));
 distribuzioneInBlocco(n-1, x+1, population, aggiunta);
 }
}

for example if I give as population the vector 0 2 4 6 and n = 3 the answer will be

0 2 4
0 2 6
0 4 6
2 4 6

if I give the same population but n = 2 the result will be:

0 2
0 4
0 6
2 4
2 6
4 6

if n = 4

0 2 4 6

Moreover is there a way for doing it without recursion?

• amon: Related to, but not complete duplicate of Better way to create samples on programmers. Many points outlined in my answer there still hold here.
• giacomotb: this is different because there are combination instead permutation, and I fint it more difficult to do it without recursion
• Simon Forsberg: Could you provide an example of how to use this method? I seriously don't understand how it works. And there are actually two compiler errors in your code: campione is not declared, and it's called return (SEMICOLON), not return (COLON)
• giacomotb: I have corrected and added some example.

Answer 1

Your solution requires that you create a new Vector for every combination. You are right that there is no better algorithm. The way you have it implemented though, is not as efficient as it should be.

Float should be a primitive.... float. Using a Float object instead of the primitive float will require a lot more memory than you should need.

The Java Vector class is a synchronized implementation. Use of the Vector class is discouraged. If you need synchronization then use one of the java.util.concurrent.* classes. I would also use an array-of-primitives for the input population too):

private static void distribuzioneInBlocco(int n, int firstElementConsidered, float[] population, float[] sample){
 // not sure what this is.....
// exit condition, when n equals 0 the function doesn't self-calls
 //if(n==0){ 
 // JOptionPane.ShowMessageDialog(null, campione);
 // return:
 //}
 // for every element of the population the function adds this element
 // at the previous combination
 for(int x = firstElementConsidered; x < population.length; x++) {
 float[] aggiunta = Arrays.copyOf(sample, sample.length + 1);
 aggiunta[aggiunta.length - 1] = population[x];
 distribuzioneInBlocco(n-1, x+1, population, aggiunta);
 }
}

So, using an array of primitive will make a big difference for your performance.

I note that you are not keeping any of these samples. If you do not need to actually keep the agguinta array, it is possible that you can save a lot of time by moving the initialization to be outside the loop:

private static void distribuzioneInBlocco(int n, int firstElementConsidered, float[] population, float[] sample){
 // not sure what this is.....
// exit condition, when n equals 0 the function doesn't self-calls
 //if(n==0){ 
 // JOptionPane.ShowMessageDialog(null, campione);
 // return:
 //}
 // for every element of the population the function adds this element
 // at the previous combination
 // move the array initialization outside the loop, and reuse it for each
 // recursion at this depth.
 float[] aggiunta = Arrays.copyOf(sample, sample.length + 1);
 for(int x = firstElementConsidered; x < population.length; x++) {
 aggiunta[aggiunta.length - 1] = population[x];
 distribuzioneInBlocco(n-1, x+1, population, aggiunta);
 }
}

• Simon Forsberg: "using an array of primitives, and using something like ArrayList instead of Vector will make a big difference for your performance", even though that's correct, it's not possible to use both at the same time. Java doesn't support primitives as generic types.