• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Liutauras Vilda
  • Jeanne Boyarsky
Sheriffs:
  • Junilu Lacar
  • Rob Spoor
  • Paul Clapham
Saloon Keepers:
  • Tim Holloway
  • Tim Moores
  • Jesse Silverman
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Frits Walraven

Permutation (or Combinations?) Question

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi everyone

I've been wracking my brain for an efficient way of doing the following but I can't seem to come up with anything.

Let's say I have an ArrayList< ArrayList< String > > that looks like this:

[[BANK, BANQ, BANCO],
[COMPANY, CO, CIE],
[INT, INTL, INTERNATIONAL]]

I want to create combinations of these words where 1 gets chosen from each of the sub-ArrayLists. None of the combinations should be repeated and the order is important. The first word should be from the first array, the second from the second, etc... In this example there would be 27 such combinations:

BANK COMPANY INT
BANK COMPANY INTL
BANK COMPANY INTERNATIONAL
BANK CO INT
BANK CO INTL
BANK CO INTERNATIONAL
BANK CIE INT
BANK CIE INTL
BANK CIE INTERNATIONAL

BANQ COMPANY INT
BANQ COMPANY INTL
BANQ COMPANY INTERNATIONAL
BANQ CO INT
BANQ CO INTL
BANQ CO INTERNATIONAL
BANQ CIE INT
BANQ CIE INTL
BANQ CIE INTERNATIONAL

BANCO COMPANY INT
BANCO COMPANY INTL
BANCO COMPANY INTERNATIONAL
BANCO CO INT
BANCO CO INTL
BANCO CO INTERNATIONAL
BANCO CIE INT
BANCO CIE INTL
BANCO CIE INTERNATIONAL

I know there is a way to do this efficiently using recursion but I can't come up with it. Any ideas?

-Rey
 
author & internet detective
Posts: 40913
840
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ray,
Welcome to CodeRanch!

Recursion wouldn't make this problem easier. If you know the word recursion, I'm guessing that means you've already learned about nested loops. Any ideas of how you could use loops to output this?
 
Rey Otero
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Jeanne,

Thanks for your response and for the welcome

Nested loops work fine if the ArrayList< ArrayList< String > > was a fixed size, I suppose. In this case we have a 3 x 3 but the situation can arise where instead we could have:

[[BANK, BANQ, BANCO],
[COMPANY, CO],
[INT]]

In which case we would only need 6 combinations. I haven't found a way with nested loops either that would work regardless of the dimensions. Did you have an idea when you mentioned that?

-Rey
 
Jeanne Boyarsky
author & internet detective
Posts: 40913
840
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote: I haven't found a way with nested loops either that would work regardless of the dimensions. Did you have an idea when you mentioned that?


Yes. Let's use your example:

[[BANK, BANQ, BANCO], num(b) = 3
[COMPANY, CO], num(c) = 2
[INT]] num(i) = 1

The number of combinations is num(b) * num(c) * num(i) = 3 * 2 *1 = 6

In your original example, it is the same formula, num(b) * num(c) * num(i) = 3 * 3 * 3 = 27

Hint: ArrayList has a method that lets you determine how many elements are in it. If you include this in your loop, it doesn't matter if you know the sizes in advance.
 
author
Posts: 23912
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote:
[[BANK, BANQ, BANCO],
[COMPANY, CO],
[INT]]

In which case we would only need 6 combinations. I haven't found a way with nested loops either that would work regardless of the dimensions. Did you have an idea when you mentioned that?



Three nested loops should work fine in your second example. In fact, the same technique for your first example should work for your second example. What have you tried that didn't work?

Henry
 
Rey Otero
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Getting the amount of combinations isn't the issue. The issue I am having is in actually creating the combinations and displaying them.

Henry,

Yes, three nested loops work in both those cases but then if one day it receives something more or less than three then that code won't work.

-Rey
 
Henry Wong
author
Posts: 23912
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote:Getting the amount of combinations isn't the issue. The issue I am having is in actually creating the combinations and displaying them.



Jeanne's hint does more than just count the number of combinations. If you get the hint, it should work for both examples.

Henry
 
Rey Otero
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I guess I am just not seeing it right now. Thanks for the help.
 
Jeanne Boyarsky
author & internet detective
Posts: 40913
840
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Making the hint more explicit: how do you print out the number of elements in an ArrayList? What method do you call?
 
Rey Otero
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I use the size( ) to find out how large an ArrayList is. I can figure out how many combinations I need. I just can't figure out how to construct the actual combinations.

In the example in my original post I am having difficulty writing a nested loop that would output all 27 of those combinations.
 
Jeanne Boyarsky
author & internet detective
Posts: 40913
840
Eclipse IDE VI Editor Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote:I use the size( ) to find out how large an ArrayList is.


Good. The next steps is to create three nested loops with that list.size() as the terminating condition. For example


What comes next?

(and yes, we are intentionally giving you tiny pieces of information to guide you to a solution)
 
Rey Otero
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I can see what you're doing ;) and it doesn't bother me. Here is what I have so far:



As you can see in the combine method I only have two nested loops but all that does is print out each individual word obviously. It doesn't create the combinations. You are mentioning a third nested loop which is probably where I am paralyzed.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote:Here is what I have so far:


OK, before I give you any more hints, a word about coding style. Many of these things are only convention, but a lot of companies enforce them; so it's worth getting into the habit of using them now:

1. Don't use ALL-CAPS for field names or parameters, unless they specifically refer to a constant (and furthermore, usually a public one). These (and method names) should always start with a lowercase letter, and normal convention is to use camelCase.

2. While I'm all in favour of spacing out code, don't do it with diamond operators because people can confuse them with 'less than' and 'greater than'.
So: 'ArrayList<ArrayList<String>>', not 'ArrayList< ArrayList< String > >'.

3. (along the same lines) Use '()' for no-args method and constructor calls, viz: new Combiner2(). Again, it's just style, but many Java oldies will find yours "odd".

There are several sites that offer advice on this stuff, not the least of which is our own.

HIH

Winston
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote:In this case we have a 3 x 3 but the situation can arise where instead we could have:
[[BANK, BANQ, BANCO],
[COMPANY, CO],
[INT]]
In which case we would only need 6 combinations.


Or indeed:
[[BANK, BANQ, BANCO],
[COMPANY, CO],
[INT]
[PLC, LTD, AG]]
in which case you'd have 18, and four initial "rows", not three.

Bascially, you need to work out how to get "all combinations" for each "next" row, which is where recursion might help; although Jeanne is quite right, you can do it without - indeed, you can "unroll" ANY recursive code; the question usually is whether the "unrolled" version is as easy to follow as the recursive one.

In this case (specifically, a two-dimensional structure with a variable number of rows and columns), I'd say that the important delimiters of your problem are the first and last rows of your structure.
For each element of your first row, you need to process each element of all your other rows and, in each case, after you've processed each element of your last row, you need to add a newline.

And since you need to keep track of where you are on each row, you could keep an array of indexes to help you print out each "line". Personally, I think I would be tempted to use recursion for this, but it's entirely up to you.

Hope it helps.

Winston
 
Henry Wong
author
Posts: 23912
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Winston Gutkowski wrote:
And since you need to keep track of where you are on each row, you could keep an array of indexes to help you print out each "line". Personally, I think I would be tempted to use recursion for this, but it's entirely up to you.



I would be very tempted to go the recursion route too -- especially, if there is even a small chance to have the example you proposed. However, the OP seems to be having some difficulty envisioning the solution with loops, and for cases that can be done with a fixed number of loops. It will be an order of magnitude to provide the hints for a recursive solution.

Henry
 
Rey Otero
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Winston,

The example you propose is one that does actually come up which is why a recursive solution was what I first thought of since it would probably be the most elegant looking. However, I managed to find an iterative way to do it. This is for personal use, not to be judged or graded so it does not matter how I get to the solution honestly. Also, thanks for the coding style tips. In the solution I am writing below I didn't update it to reflect what you mentioned but I'll keep it in mind for next time.



This code uses your example that requires 18 combinations, like you mentioned. The output for this is:

Combinations Required: 18
[BANK, COMPANY, INT, PLC]
[BANK, COMPANY, INT, LTD]
[BANK, COMPANY, INT, AG]
[BANK, CO, INT, PLC]
[BANK, CO, INT, LTD]
[BANK, CO, INT, AG]
[BANQ, COMPANY, INT, PLC]
[BANQ, COMPANY, INT, LTD]
[BANQ, COMPANY, INT, AG]
[BANQ, CO, INT, PLC]
[BANQ, CO, INT, LTD]
[BANQ, CO, INT, AG]
[BANCO, COMPANY, INT, PLC]
[BANCO, COMPANY, INT, LTD]
[BANCO, COMPANY, INT, AG]
[BANCO, CO, INT, PLC]
[BANCO, CO, INT, LTD]
[BANCO, CO, INT, AG]



It works really fast as well. Thanks everyone for all your input.

-Rey
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Rey Otero wrote:However, I managed to find an iterative way to do it....
It works really fast as well. Thanks everyone for all your input.


You're most welcome. And WELL DONE!!!

Just a minor efficiency point (although if it's fast enough, don't worry about it too much):
for( int i = 0; i < COUNTS.get( 0 ); i++ )
requires the loop to do a redundant get() call for each iteration of the loop. You can eliminate this by establishing the value at the start, viz:
for( int i = 0, rows = COUNTS.get(0); i < rows; i++ )

In your case, the savings will probably be unnoticable; but if you have a loop that needs to do a million iterations...

HIH

Winston
 
WHAT is your favorite color? Blue, no yellow, ahhhhhhh! Tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic