• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

All possible combinations of the elements in the string array

 
Parth Bhatt
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi everyone,

i have been workin on a small program but failed to come up with a solution... Here's the problem :

Create a java program that has a method which takes in a String array, say somethin like



and produces a list of all possible combinations of the elements of the array. i.e. it should produce output like




NOTE :
(1) The output should contain strings that are of length 1 to arg-arr.length()

(2) The method that produces the combinations should be flexible enough to work irrespective of the size of arg-arr.
 
Ernest Friedman-Hill
author and iconoclast
Marshal
Pie
Posts: 24208
35
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, show us what you've tried so far.
 
Parth Bhatt
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hi,

This is what i could come up with & as is obvious; its hardly a satisfactory solution.




The method GenCombinations() has to have 2 (nested) loops to generate all possible combinations of length 2. Similar is the case with combinations of length 3, and so on...

What i need, precicely, is a function that would generate all possible combinations of length 1 to str_arr.length, irrespective of the length of str_arr.
[ November 13, 2006: Message edited by: Parth Bhatt ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Think more on how you might work it without a computer. Take an empty starting point and add "a". Then add one of the remaining letters. Then add one of the remaining letters. Repeat until you run out of letters. This is a classic recursion problem where a method calls itself to build up more stuff. Start by calling this builder with an empty string:

That doesn't produce output in quite the order you did. Get it running and see if you like it.

BTW: Start with very small sets of letters, like "ab" or "abc" and make sure it does what you expect first. Your example of a through i will have a VERY LARGE number of combinations.

Also to avoid arguments later, make sure you know if your problem says "ab" and "ba" are duplicates or not. Is an input set of letters with duplicates, say "aaa", allowed?
 
Parth Bhatt
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Stan... you have given me a good point to start...

Yes i am aware of the fact that it will generate a large set of combinations. Also, "ab" and "ba" are both to be generated (i.e. they should be considered different).

And sequence in which the combination strings are generated does not matter.

I shall post the solution as i figure it out. Meanwhile, as you said its a classical problem, if you have a web-link that throws some light on it please post it here...

Thanks a lot again...
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Parth Bhatt]: Also, "ab" and "ba" are both to be generated (i.e. they should be considered different).

I recommend you should not use the word "combinations" to describe what you are doing - these are permutations, not combinations. The difference is important when communicating with others.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And I'm a music major and I'm not sure what either one is.
 
Ken Blair
Ranch Hand
Posts: 1078
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Stan James:
And I'm a music major and I'm not sure what either one is.


Do you do birthdays?
 
Mahesh Shiwani
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Try this code... and tell me if this is what you were trying to do...

public void combinations(String s){
char[] original = s.toCharArray();
int original_size = s.length();
String sb = new String();
String temp = new String();
for(int i=0; i<original_size; i++){
sb = temp+sb+""+original[i];
temp = sb.toString();
//System.out.println("temp "+temp);
System.out.println(sb);
for(int j=i+1; j<original_size; j++){
if(i==j)continue;
sb = temp+""+original[j];
System.out.println(sb);
}
sb = "";
}
}

Regards,
Mahesh Shiwani.
 
Mahesh Shiwani
Greenhorn
Posts: 10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Here is the complete code this time... just check this out...

import java.util.HashSet;
import java.util.Iterator;

/*
* Created on Nov 15, 2006
*
* TODO To change the template for this generated file go to
* Window - Preferences - Java - Code Style - Code Templates
*/

/**
* @author shivanim
*
* TODO To change the template for this generated type comment go to
* Window - Preferences - Java - Code Style - Code Templates
*/
public class Conversion {

public static void main(String[] args) {
Conversion c = new Conversion();
c.combinations("Sanjeev");
}
public void combinations(String s){
char[] original = s.toCharArray();

int i=0;
int j=0;
HashSet hashset = new HashSet();
while(original.length != 0){

String sb = new String();
String temp = new String();
for(i=0; i<original.length-1; i++){

sb = temp+sb+""+original[i];
temp = sb.toString();

for(j=i+1; j<original.length; j++){
sb = temp+""+original[j];

hashset.add(sb);
}
sb = "";
}
original = removefirst(original);
}
printhashset(hashset);
}
public char[] removefirst(char[] aa){
char[] newarray = new char[aa.length-1];
for(int i=0; i<aa.length-1; i++){
newarray[i] = aa[i+1];
}

return newarray;
}
public void printhashset(HashSet hs){
Iterator iterator = hs.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
}

Save the file as Conversion.java; compile it and run.. let me know if desired effect is achieved or not...
Regards,
Mahesh Shiwani.
 
Parth Bhatt
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're very close Mahesh...

Actually for the string "abc", your program produces the following o/p


whereas it should produce

The sequence is in which these strings are generated does not matter; but all of them should be generated...
 
Parth Bhatt
Ranch Hand
Posts: 58
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You're very close Mahesh... This is, possibly, the closest solution to this problem...

Actually for the string "abc", your program produces the following o/p :


whereas it should produce


i.e. all possible combinations(or probably "permutations" is a better word) of "a", "b" & "c" should be generated.

The sequence in which these strings are generated does not matter; but all of them should be generated...
[ November 15, 2006: Message edited by: Parth Bhatt ]
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I made a 10-line recursive method that is almost a line per line translation of the p-code above. The only tricky bit was "for each letter that isn't in input". When I added a character to the input, I replaced it in the available array with a blank before the recursive call and restored it after. That seemed like less effort than copying the array less one letter or scanning the input for duplicates but still took four lines or so to implement one condition.

For "abc" it gives

a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
Count=15

For "abcdefg" it gives 13,699 combinations. Adding an "h" gets 109,600. They go up really fast from there.
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Off topic a bit ... I'm on my 2nd day of Ruby and this

translated to this

pretty quickly. Ruby experts, I wanted to use array- ... is that a reasonable way to do it? Is unpack the way to get a byte array?
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm hardly a Ruby expert, but using unpack looks reasonable to me. Alternately you could use split or scan to get an array of Strings (and then you don't need the chr calls):
 
Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Kool. I'll move any Ruby stuff off to the scripting forum in the future ...

So how's the OP doing with all the combinations & Java?
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic