Every combination of object array

Question

Basically, I have an array containing 25 different people, I need to select 5 of these people and have every single combination possible, without using duplicates of the same person.

The only logical way I can think of doing it is by having 5 for loops and checking if person has already been used, although this seems like there's probably a better method involving recursion.

If anyone can help I'd be very appreciated.

Here's an example of my class;

public class Calculator {

    final Person[] people = new Person[25]; //Pretend we have filled in this info already

    public List<Group> generateList()
    {
        final List<Group> possible = new ArrayList<>();
        for (int a = 0; a < 25; a++)
        {
            for (int b = 0; b < 25; b++)
            {
                for (int c = 0; c < 25; c++)
                {
                    for (int d = 0; d < 25; d++)
                    {
                        for (int e = 0; e < 25; e++)
                        {
                            final Group next = new Group();
                            next.set = new Person[] {
                                people[a],
                                people[b],
                                people[c],
                                people[d],
                                people[e]
                            };
                            possible.add(next);
                        }
                    }
                }
            }
        }
        return possible;
    }



    class Group {

        Person[] set = new Person[5];

    }

    class Person {

        String name;
        int age;

    }

}

However I'm not sure the best way to do this and if that would even get every combination. I also know there's no duplicate checking here, which I'd do by checking;

if(b == a) continue;

Etc.

I would appreciate any help.

A Better Link : Very much possible using recursion. Another way is to do is using the property of binary combinations — Extreme Coders
– Extreme Coders, Commented Dec 17, 2012 at 15:00

Simon · Accepted Answer · 2012-12-17 14:53:39Z

9

One possibility would be to use a combinatorics library like: http://code.google.com/p/combinatoricslib/.

// Create the initial vector
   ICombinatoricsVector<String> initialVector = Factory.createVector(
      new String[] { "red", "black", "white", "green", "blue" } );

   // Create a simple combination generator to generate 3-combinations of the initial vector
   Generator<String> gen = Factory.createSimpleCombinationGenerator(initialVector, 3);

   // Print all possible combinations
   for (ICombinatoricsVector<String> combination : gen) {
      System.out.println(combination);
   }

The example is from the project page (see link). It should be pretty easy to transfer it to your use case.

answered Dec 17, 2012 at 14:53

Simon

9,4054 gold badges40 silver badges56 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sanjay Manohar · Accepted Answer · 2012-12-17 15:19:07Z

There are many options.

(1)

you can improve your algoritghm by using

for a = 0 to 25 
  for b = a+1 to 25  // use ascending-order rule 
    for c = b+1 to 25

etc - this eliminates duplicate checking, taking advantage of the factorial nature of the problem

(2)

you can alternatively implement these as a single for loop over the whole N^R items (if you chose R items from N), and discard permutations that are not in full ascending order. This is good if you don't know R beforehand. Imagine you are counting in base N

for i = 0 to N^R // count in base N
  for digit = 0 to R 
    value[digit] = (i/N^digit) mod (N^(digit+1)) // extract the required digit
    if digit>0 && value[digit]<value[digit-1], SKIP

In other words, you count sequentially on these R indexes.

(3)

The final option, which is longer to code but more efficient for large R and N, is to use a set of indices:

// i is an array size R, with items ranging from 0 to N
i = int[]{ 0, 1, 2, 3, 4 }; // each is an index of the items in N

while !finished
    j=0; // index to start incrementing at
    i[j] ++;

then if you go above N on any index, increase j, increment i[j], and set all the i[k<j] to [0 1 2 ... j-1], and start counting again! this cycles most efficiently through all combinations.

Collectives™ on Stack Overflow

Every combination of object array

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related