All possible combinations of the elements in the string array

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.

Well, show us what you've tried so far.

hi,

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

public class Comb{
 
  public Comb(){
 
    String str_arr[]={"a","b","c"};
    GenCombinations(str_arr);
  }
 
 
  /**
    THE METHOD THAT TAKES AN ARRAY OF STRINGS AND PRINTS THE 
    POSSIBLE COMBINATIONS.
  */
  public void GenCombinations(String[] str_arr){
 
    System.out.println("Generating All possible Combinations for  the following "+str_arr.length+" strings.");        
 
    for(int i=0;i<str_arr.length;i++)
     {
        System.out.print(str_arr[i]+" ");
     }
    System.out.println("\n------------------------------------------");
 
    /*COMBINATIONS OF LENGTH ONE*/
    for(int i=0;i<str_arr.length;i++)
        System.out.println(str_arr[i]);        
 
    /*COMBINATIONS OF LENGTH TWO*/
    for(int i=0;i<str_arr.length;i++)
     {
       for(int j=0;j<str_arr.length;j++)
         {
            System.out.println(str_arr[i]+""+str_arr[j]);                   
         }
     } 
 
    /*COMBINATIONS OF LENGTH THREE*/
    for(int i=0;i<str_arr.length;i++)
     {
      for(int j=0;j<str_arr.length;j++)
       {
        for(int k=0;k<str_arr.length;k++)
         {  
            System.out.println(str_arr[i]+""+str_arr[j]+""+str_arr[k]);                      
         }
       }
     }
  } 
 
 
  public static void main(String[] args){
 
    new Comb();
  }
}

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 ]

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?

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...

[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.

And I'm a music major and I'm not sure what either one is.

Originally posted by Stan James:
And I'm a music major and I'm not sure what either one is.

Do you do birthdays?

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.

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.

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...

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 ]

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.

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?

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):

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?