CODEWITHSUNDEEP
javaarraysalgorithm
Snow_Mac
Snow_Mac

Reputation: 5797

List all possible combinations

Here's what I am trying to do:

Given a list of names, print out all combinations of the names taken three at a time. If the list has too few elements, don't print anything. Names must occur in the same order that they appear in the list. So, if the list contains the names Kennedy, Johnson, Nixon, Ford, you program prints:

[Kennedy, Johnson, Nixon]
[Kennedy,Johnson, Ford]
[Kennedy, Nixon, Ford] [Johnson, Nixon, Ford]

Put the values in an array and then use the Arrays.toString() method to print the results, one per line.

Parameters: list - - a list of name.

Right now I'm using print statements to see if I am on the right track, if I am, I'll finish adapting this into an array.

Here's my code:

int x = 0;
 int y = 1; 
 int z = 2; 


 for(int i = 0; i<list.length;i++){

  for (int j = 0;j<3;j++){

   System.out.print(list[x]);
   System.out.print(list[y]);
   System.out.print(list[z]);

   if (j>=1){y++;}
   if (z != list.length){z++;}

  }
  x++; 

 }

Here's the error I get: 

Enter commands:
trio Kennedy, Johnson, Nixon,ford
Kennedyjava.lang.ArrayIndexOutOfBoundsException: 1
 at MyAssign1.trio(MyAssign1.java:204)
 at Assign1.processOneCommand(Assign1.java:109)
 at CmdInterpreter.processCommands(CmdInterpreter.java:198)
 at CmdInterpreter.processCommands(CmdInterpreter.java:230)
 at CmdInterpreter.ooMain(CmdInterpreter.java:243)
 at MyAssign1.main(MyAssign1.java:20)

Line 204 is: 

System.out.print(list[y]);

What am I doing wrong?

Upvotes: 0

Views: 18823

Answers (6)

user3208512
user3208512

Reputation: 1

Below method takes any number of Strings as input list. And will generated possible number of Permutations/Combinations. In case of Permutations you can also mention if you need repeated String or not. please note if ComboOnly is true then isRepeat does not effect.

private static void generatePerms(List<String> list, boolean isRepeat, boolean comboOnly) {     
    int n = list.size();
    List<List<Integer>> lists = new ArrayList<List<Integer>>();

     for (int i = 0; i< n;i++) {
         int j = (comboOnly?i+1:0);
         for ( ; j < n;j++) {
             if (!isRepeat && i == j) continue;
             int k = (comboOnly?j+1:0);
             for (; k< n ;k++) {
                 if ( !isRepeat && (k ==i || k ==j)) continue;
                 System.out.println(list.get(i),list.get(j),list.get(k)));
             }
         }
     }

    return lists;
}

Upvotes: 0

ch0kee
ch0kee

Reputation: 746

Try to compare with my solution, with a less complicated logic:

import java.util.ArrayList;
import java.util.Arrays;

public class PrintCombinations
{
    private final static int LEN = 3;

    //for example: args = [Kennedy, Johnson, Nixon, Ford]
    public static void main(String[] args)
    {
        if (args.length < LEN)
            return; //too few data

        //collect combinations
        String[][] combinations = collectCombinations(args);

        //print result, one per line
        for(String[] comb : combinations)
        {
            System.out.println(Arrays.toString(comb));
        }
    }

    //collects all combinations and returns the result array 
    private static String[][] collectCombinations(String[] list)
    {
        int n = list.length;

        java.util.ArrayList<String[]> combinations = new ArrayList<String[]>();

        //the last possible 'i' is list[n-LEN], so no need go further
        for(int i = 0; i <= n - LEN; ++i)
        {
            //the last possible 'j' is list[n-(LEN-1)]
            for(int j = i+1; j <= n - (LEN-1); ++j)
            {
                //the last possible 'k' is list[n-(LEN-2)]
                //n-(LEN-2)==n-(3-2)==n-1, its the last element in the list
                for(int k = j+1; k <= n - (LEN-2); ++k)
                {
                    combinations.add(new String[] {
                            list[i],
                            list[j],
                            list[k]});  
                }               
            }
        }
        return combinations.toArray(new String[0][]);
    }
}

I have included some range optimalization to avoid unnecessary runs inside the loops. You can't simply change LEN to modify the sequence length, it is only for eliminating the "magic number" 3 from the code.

Remark:If you want longer sequences instead of 3, you need to embed a new loop depth.

Hope it helps!

Upvotes: 0

Nicholas Hirras
Nicholas Hirras

Reputation: 2596

I think your problem is not in the code you posted, but in the code you didn't show us. How are you creating and populating the list array? It looks like list is initialized wrong, and only actually contains one element.

Try adding something like this to your code to check it:

// Check size of list array.
System.out.println("list.length=" + list.length);

// Print out contents of list array.
for(int i=0; i<list.length; i++) {
   System.out.println(i + "=" + list[i]);
}

Upvotes: 0

Andrzej Doyle
Andrzej Doyle

Reputation: 103837

Looking at your code (and I don't wish to be unkind), I don't think you're on the right track with this one.

I recommend that as a first step you forget about code altogether, and think simply about the algorithm or process you'd use. You should be able to write it down in English as a list of steps. Only once you have that list, should you then think about how you'd implement it in code.

To answer your actual question, you're currently getting the exception because you're accessing elements past the end of the list. This is due in part to the fact that incrementing until z equals list.length stops too late; an array with length 4 has elements with indices 0-3, so list[4] will throw the exception you're encountering.

(Right now your combination-finding logic won't do the right thing. x is never changed, so every combination (given the example) will start with Kennedy. As z hits the length of the list it stops growing, but y continues to grow, so you'll get some iterations where the second and third entries are identical, and you haven't considered whether y will exceed the bounds. You're also looping over i but doing nothing with it. Your program, if it didn't crash, would output something like this:

Kennedy, Johnson, Nixon
Kennedy, Johnson, Ford
Kennedy, Nixon, Ford
Kennedy, Ford, Ford
Kennedy, Johnson, Nixon
Kennedy, Johnson, Ford
Kennedy, Nixon, Ford
Kennedy, Ford, Ford
Kennedy, Johnson, Nixon
Kennedy, Johnson, Ford
Kennedy, Nixon, Ford
Kennedy, Ford, Ford
Kennedy, Johnson, Nixon
Kennedy, Johnson, Ford
Kennedy, Nixon, Ford
Kennedy, Ford, Ford

And you have a lot of special-casing in there. The assumption that you need to iterate while j < 3 only works when there are exactly four elements in the input. The check that you should increment y if j >= 1 is again a special-case that only creates the right result with exactly four elements. Again, I encourage you to think about the process you you might use to find every permuation of three elements in an input of arbitrary length, without thinking about code at all.)

Upvotes: 3

vz0
vz0

Reputation: 32923

As the comments on your question suggest, the ArrayIndexOutOfBoundsException exception occurs because you are accesing an index outside the limits of the array list. Take a look:

if (j>=1){y++;}

The value of y is always being increased. After list.length iterations the exception surely will raise. The solution to the exception is simple: do not access an array with an index outside its bounds.

While many solutions to the combinations problem exists, the most simple one to put you back on track is:

for (int a = 0; a < list.length; a++) {
    for (int b = a + 1; b < list.length; b++) {
        for (int c = b + 1; c < list.length; c++) {
            System.out.print(list[a] + ", ");
            System.out.print(list[b] + ", ");
            System.out.println(list[c]);
        }
    }
}

Upvotes: 5

Joseph Erickson
Joseph Erickson

Reputation: 2294

I assume you're using this to wrap your code: http://www.cs.colostate.edu/~cs161/assignments/PA1/src/CmdInterpreter.java

I think you're main problem is probably the way you're executing the command. It looks to me like it's only thinking Kennedy is part of the Array and not the other names. Try this command instead:

trio Kennedy,Johnson,Nixon,Ford

Leaving the spaces out might help the parser interpret the Array.

Upvotes: 0

Related Questions