aspose file tools*
The moose likes Java in General and the fly likes All possible combinations of the elements in the string array Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "All possible combinations of the elements in the string array" Watch "All possible combinations of the elements in the string array" New topic
Author

All possible combinations of the elements in the string array

Parth Bhatt
Ranch Hand

Joined: Oct 19, 2005
Posts: 58
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.


If your new Big Idea doesn't scare the hell out of you, <br />it's probably not a "new Big Idea".
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24184
    
  34

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


[Jess in Action][AskingGoodQuestions]
Parth Bhatt
Ranch Hand

Joined: Oct 19, 2005
Posts: 58
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

Joined: Jan 29, 2003
Posts: 8791
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?


A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi
Parth Bhatt
Ranch Hand

Joined: Oct 19, 2005
Posts: 58
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

Joined: Jan 30, 2000
Posts: 18671
[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.


"I'm not back." - Bill Harding, Twister
Stan James
(instanceof Sidekick)
Ranch Hand

Joined: Jan 29, 2003
Posts: 8791
And I'm a music major and I'm not sure what either one is.
Ken Blair
Ranch Hand

Joined: Jul 15, 2003
Posts: 1078
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

Joined: Oct 04, 2004
Posts: 10
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

Joined: Oct 04, 2004
Posts: 10
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

Joined: Oct 19, 2005
Posts: 58
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

Joined: Oct 19, 2005
Posts: 58
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

Joined: Jan 29, 2003
Posts: 8791
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

Joined: Jan 29, 2003
Posts: 8791
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

Joined: Jan 30, 2000
Posts: 18671
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

Joined: Jan 29, 2003
Posts: 8791
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?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: All possible combinations of the elements in the string array