# Simple ArrayList conundrum?

Mike Smike
Ranch Hand
Posts: 33
Hi guys!

Just a quick problem I have here. Basically I have an ArrayList of ArrayLists of some object. So it would look something like this:

[ [1,2,3], [4], [5,6,7,8,9], [10,11] ]

Now I want to get every possible combination of elements, selecting at least one from each arraylist. So I'd need:

[1,4,5,10], [1,4,5,11], [1,4,6,10], [1,4,6,11].... [3,4,9,11]

But my problem is that I could have any number of ArrayLists in the ArrayList, containing any number of elements, so a simple combination of for loops won't work. I was hoping there might be a method in the API which multiplies out every possible combination of elements in an ArrayList, but there doesn't appear to be.

I wonder if I'm just being a bit dim, but it's been giving me a headache for days. Does anyone have any ideas? Or am I heading down a bit of a dead end

Thanks for your time and help

Mike
[ March 03, 2005: Message edited by: Mike Smike ]

Corey McGlone
Ranch Hand
Posts: 3271
Seems like recursion might be a possibility...

Mike Smike
Ranch Hand
Posts: 33
Yeah, but how do recursively iterate through loops, combining all combinations of the elements... I'm sure there is a way, I'm just having real issues trying to hammer it out as code...

Layne Lund
Ranch Hand
Posts: 3061
I don't understand why you can't use a for loop. Will the number of items change while you are looping? If not, you can call ArrayList.size() to get the number of items that are currently in the list and use that in your for loop condition. In fact, this is a common way to iterate through an ArrayList.

Alternatively, you can use an Iterator. You obtain one from an ArrayList by calling ArrayList.iterator(). You also use Iterator.hasNext() and Iterator.next() during a while loop to iterate over the ArrayList. Also, if you are using Java 5.0, you can use the new for-each loop syntax.

I strongly suggest that you visit the Collections trail in Sun's Java tutorial. It should explain a lot about the classes available in the Collections framework and how to use them. You should also keep the Java API documentation handy. If you are not familiar with these docs yet, I strongly encourage you to learn how to navigate them. The API docs are a crucial tool for any decent Java programmer, imo.

Layne

Mike Smike
Ranch Hand
Posts: 33
I think you've misunderstood the question. I know very well how to iterate through a loop, both with iterators and with for loops. But that is not my problem. I need to combine all the elements within the ArrayLists in every possible combination... This is not a very simple task...

Corey McGlone
Ranch Hand
Posts: 3271
I assume that this is a homework problem so I don't really want to give you the answer outright. However, I have no problem at all giving some guidance.

First of all, whenever I attack a recursion problem, I take plenty of time to look at the problem on paper and figure out what the process would be to get the result that I want. Make sure you understand that very well. I imagine you've already done this but I can't stress how important that is. It's impossible to write code to do something that you don't fully understand.

Next, I took a page from my days programming ML. Most folks don't have much, if any, experience with ML, so let me fill you in on what I'm talking about. In ML, there are two major operations on a list. The first operation is called "Head." That operation returns the first element of the list. The second operation is called "Tail." That method returns everything except the first element of a list. So, Head + Tail would be equivalent to your original list.

Chew on that for just a bit and see what you can come up with. I don't know if that'll be enough of a hint to get you there, but I'm trying to start with something simple. See what you can come up with and let me know what you get.
[ March 03, 2005: Message edited by: Corey McGlone ]

marc weber
Sheriff
Posts: 11343
Hmmm...

If I'm understanding this: From the first ArrayList (with x elements), you might select 1 element, or you might select 2 elements, or 3, or ... x. Then from the second ArrayList (with y elements), you might select 1 element, or 2, or ... y. And so on.

If so, I'm envisioning a method that runs on each ArrayList to systematically return all combinations of elements within that particular List. For example, if the ArrayList has 3 elements, the method returns all combinations in which 1 element is selected: [1], [2], [3]; and all combinations in which 2 elements are selected: [1, 2], [1, 3], [2, 3]; and all combinations in which 3 elements are selected: [1, 2, 3]. (In general, you'll have (2^n)-1 combinations for each ArrayList, since we're not including the possibility of selecting zero elements.)

These results could be returned in the form of a new ArrayList. In other words, running the method on list1 (with x elements) would return a new Arraylist called list1combos (with (2^x)-1 elements). Running it on list2 (with y elements) would return a list2combos (with (2^y)-1 elements).

At this point, you've reduced the problem to selecting only 1 element from each of the combo lists (since each of these elements is itself a list of elements).

Corey McGlone
Ranch Hand
Posts: 3271
Originally posted by marc weber:

If I'm understanding this: From the first ArrayList (with x elements), you might select 1 element, or you might select 2 elements, or 3, or ... x. Then from the second ArrayList (with y elements), you might select 1 element, or 2, or ... y. And so on.

I was under the impression that you'd only ever select one element from each list. Each combination in made up of one element from each list.

Horatio Westock
Ranch Hand
Posts: 221
Start by writing a function that gets all the combinations for two lists, and returns the results as a list. Remember to take into account when either list is empty.

Then think about how to apply this to all of the data.

marc weber
Sheriff
Posts: 11343
Originally posted by Corey McGlone:
I was under the impression that you'd only ever select one element from each list. Each combination in made up of one element from each list.

That's what was illustrated in the original example, but the associated text says, "selecting at least one from each arraylist." So it's not entirely clear.
[ March 03, 2005: Message edited by: marc weber ]

Corey McGlone
Ranch Hand
Posts: 3271
Originally posted by marc weber:

That's what was illustrated in the original example, but the associated text says, "selecting at least one from each arraylist." So it's not entirely clear.

Hmmm...good catch. The solution I worked selects exactly one element from each list, not at least one element. So which is it, Mike?

Mike Smike
Ranch Hand
Posts: 33
Hi guys, thanks for the responses

To clarify things, I am not trying to generate every combination of elements in each list. Instead I am trying to generate every combination of elements from all lists, but with only one element from each list appearing in each configuration.

Does that help? I'm sorry it's not too clear... I think Horatio's post seems to have a good point. I'll have a bash at coding it tomorrow and post what I manage to achieve. It's 12:30 pm for me now, so I'm off to bed

Thanks for all the advice guys, I'll let you know how it goes.

Mike

ps - it's not really a homework problem, but part of the program I am writing for my disertation. The objects in the ArrayList are moves, and each ArrayList represents a unit. I need all possible combinations to use in my minimax agent.

James Carman
Ranch Hand
Posts: 580
If you can believe it, I wrote something like this today for someone at work! Try this...

Horatio Westock
Ranch Hand
Posts: 221
Hi again,

As it's not for plain old homework, I've added some code below. This is a simple implementation that works on where there is only one nesting of lists. It would be easy to alter for a case where the lists were arbitrarily nested.

I didn't spend long on this, so please point out any obvious glaring errors!

Mike Smike
Ranch Hand
Posts: 33
Wow - guys, thank you SO MUCH! Espiecailly James and Horatio - your solutions both worked tremendously! This site never ceases to impress me more and more every time I visit. I wish I could reward you with lots of cattle!

I finally have a properly implemented minimax search for my AI player! I now must somehow reduce the complexity, as a board of just 3 by 3 manages to generate 96 possible moves on the first turn alone! The exponential increase in complexity is such that when I run a 4 by 4 board, it crashes!

Thanks guys for getting me past a sticky point. My disertation says a big thankyou too Pints all round

Mike

Jeroen Wenting
Ranch Hand
Posts: 5093
Why were you expecting there to be a method in the core API for your rather obscure task?
It's not as if it's something anyone is very likely to ever need...

Corey McGlone
Ranch Hand
Posts: 3271
For the sake of throwing it out there and explaining my previous "ML" statement, here's the code I used to solve the problem:

[ March 04, 2005: Message edited by: Corey McGlone ]

Horatio Westock
Ranch Hand
Posts: 221
I like your implementation - useful to reuse whenever you want to do tail recursion type things

ML reminds me of long nights in the CS lab. Prolog reminds me of long nights in the AI lab. Now while I appreciate what those nights taught me (aside from how to play human bowling using office chairs) - I never want to do it again!

Corey McGlone
Ranch Hand
Posts: 3271
Originally posted by Horatio Westock:
ML reminds me of long nights in the CS lab. Prolog reminds me of long nights in the AI lab. Now while I appreciate what those nights taught me (aside from how to play human bowling using office chairs) - I never want to do it again!

My friends and I used 2 very important words to get us through those nights of ML and ProLog AI homework...

Nerf Weapons!

Nothing like a great nerf war at 2 in the morning...

Geoffrey Falk
Ranch Hand
Posts: 171
1
Mathematically you are just talking about a Cartesian product. So write a function to obtain the Cartesian product of two Lists, and then extend it to n lists.

Geoffrey

Geoffrey Falk
Ranch Hand
Posts: 171
1
The result set may be large, so you probably don't want to keep it all in memory. Instead, implement an Iterator to generate the results one at a time. Here is my solution.

[ March 08, 2005: Message edited by: Geoffrey Falk ]