how to find all possible combinations of charcters in string

[Mike Gari]

hi all ,

this the example , i have a string contains 4 chars (A,B,C,D). size =4 , now all possibel cimbinations = N! which N = length of the String
i want to find all possible combinations like
ABCD
ABDC
ACBD
ACDB
ADCB
ADBC

BACD
BADC
BCAD
BCDA
BDAC
BDCA

AND etc ...... till we reached to N! .

[Darryl Burke]

Not a great recommendation for the SCJP, that.

[Peter Taucher]

What do you mean when you say 'find all combinations'?

I'd say all combinations could be 'found' in such way:

public class Foobar
{
    public static void main( String[] args )
    {
       char[] chars = "ABCD".toCharArray();
       int i = 0;
       
       for ( char a : chars )
       {
           for ( char b: chars )
           {
               for ( char c : chars )
               {
                   for ( char d: chars )
                   {
                       System.out.println( ++i + " " + a + b + c + d );
                   }
               }
           }
       }
    }
}

[Mike Gari]

hey Darry! ,

the question is algorithmic question it's not about strings ,it's a part of a huge algorithm currently implement it ,i've just simplified the questions to strings so you may understand what do i want ?

i want to find the best solution recursively or not recursive from the public
you dont' need to talk about recommendation in SCJP , i'm currently doing a SCJD FYI .

Hi Peter ,

i want to stor every solution as described in my last post in char array .it's not ABCD . it may be ABCDEFGJKSLDLFD .
the length is variable .

[Campbell Ritchie]

Peter Taucher wrote:I'd say all combinations could be 'found' in such way:

That will include duplicates, giving n^n results rather than n!

[Mike Gari]

if you mean abcd and dcba is a duplicate , this wrong .

[David Newton]

@alaa: No, he was referring to the difference between permutations (*not* combination, by the way) with, and without, repetition. Without repetition you get N!, with repetition you get N^2. The code shown is N^2, "duplicates" referring to the use of a single letter in more than one position.

[Mike Gari]

I mean you can reverse and but the size of each array should be N .
EX: let ABCD the string , ACB will not be accepted the length should be the same length of the original string ,So
it's not permutation , and we will get N!.

[Henry Wong]

alaa salameh wrote:I mean you can reverse and but the size of each array should be N .
EX: let ABCD the string , ACB will not be accepted the length should be the same length of the original string ,So
it's not permutation , and we will get N!.

Actually, what you just described is exactly what a permutation is. Regardless...

alaa salameh wrote:
i want to find the best solution recursively or not recursive from the public
you dont' need to talk about recommendation in SCJP , i'm currently doing a SCJD FYI .

This is pretty much a standard problem for recursion to solve. In fact, what you described is a homework problem for recursion, in many cases.

So... IMHO, recursive is the best solution to this problem.

Henry

[Lalit Mehra]

even with recursion it'll take quite a lengthy algorithm if you have variable string length

[Mike Gari]

find below the solution i have.

@SuppressWarnings("unchecked")
    private void findPossibleSolutions(List<ArrayList<Point>> solutions,
            ArrayList<Point> left, ArrayList<Point> right) {
        if (right.size() == 1) {
            //merger two lists
            left.addAll(right);
            solutions.add(left);
        } else {
            for (int index = 0; index < right.size(); index++) {
                ArrayList<Point> newLeft = new ArrayList<Point>();
                newLeft = (ArrayList<Point>) left.clone();
                newLeft.add(right.get(index));

                ArrayList<Point> newRight = new ArrayList<Point>();
                newRight = (ArrayList<Point>) right.clone();
                newRight.remove(index);

                findPossibleSolutions(solutions,newLeft, newRight);
            }
        }
    }

[David Newton]

Lalit Mehra wrote:even with recursion it'll take quite a lengthy algorithm if you have variable string length

Do you mean it'll take a long time (relatively speaking) to execute?

[Mike Gari]

yes it's just an algorithm and i need to find an better solution , is that the wrong forum i posted in ???

[David Newton]

Do it iteratively.

[Ireneusz Kordal]

alaa salameh wrote:yes it's just an algorithm and i need to find an better solution , is that the wrong forum i posted in ???

You can find an overview of various combinatorial algorithms here:
http://cs.utsa.edu/~wagner/knuth/

[Ganesh Gowtham]

Hi

Please try the below code ...

   import java.util.ArrayList;  
import java.util.List;  
 
/** 
 * @author Ganesh Gowtham
 * @url http://sites.google.com/site/ganeshgowtham
 * Given the input String, this code prints the combinations 
 */
 
public class StringPermutation {  
 
    public static List<String> getPermutation(String input) {  
 
        throw new PleaseDontGiveAStraightAnswerException();
        }  
 
    }  
 
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        System.out.println(StringPermutation.getPermutation("abc"));  
 
    }  
} 

[Campbell Ritchie]

Ganesh Gowtham wrote:Hi

Please try the below code ...

I may be mistaken, in which case I shall happily restore the code, but I think simply giving an answer like that is not helpful to the original poster. Don't be annoyed, but I have pulled rank and deleted it.

I hope you don't mind, Rob, Robert and Jesper.

[Christophe Verré]

Campbell Ritchie wrote:I may be mistaken, in which case I shall happily restore the code, but I think simply giving an answer like that is not helpful to the original poster. Don't be annoyed, but I have pulled rank and deleted it.
I hope you don't mind, Rob, Robert and Jesper.

And we have FAQs supporting this policy : LetThemDoTheirOwnHomework and DontBeACodeMill.

[Mike Gari]

it's the same like my solution , but it's just replaced to be String , i've marked the post as solved before you post this answer .

Thanks all for your suggestions .

[Ganesh Gowtham]

Campbell Ritchie wrote:

Ganesh Gowtham wrote:Hi

Please try the below code ...

I may be mistaken, in which case I shall happily restore the code, but I think simply giving an answer like that is not helpful to the original poster. Don't be annoyed, but I have pulled rank and deleted it.

I hope you don't mind, Rob, Robert and Jesper.

HI Campbell Ritchie ,

I thought might helpfull for him ,Since he might have already invested considerable time of this research ...

Correct me if i am wrong ....

[David Newton]

@Ganesh: Please read the FAQ entries that were pointed out--thanks!

[Ganesh Gowtham]

Ganesh Gowtham wrote:Hi

Please try the below code ...

   import java.util.ArrayList;  
import java.util.List;  
 
/** 
 * @author Ganesh Gowtham
 * @url http://sites.google.com/site/ganeshgowtham
 * Given the input String, this code prints the combinations 
 */
 
public class StringPermutation {  
 
    public static List<String> getPermutation(String input) {  
 
        throw new PleaseDontGiveAStraightAnswerException();
        }  
 
    }  
 
    /** 
     * @param args 
     */  
    public static void main(String[] args) {  
        System.out.println(StringPermutation.getPermutation("abc"));  
 
    }  
} 

Hi Campbell Ritchie ,

could you please delete this particular answer since it misleads all, Since in core algorithm it throws exception ....

[David Newton]

@Ganesh: that's the point.

[Campbell Ritchie]

Ganesh Gowtham wrote: . . . it throws exception ....

Did you read the name of the Exception class?

[Mike Gari]

Guys ,

I've seen method code when it has been posted and before has been changed to throw new DoHomeWorkException () ,
but i'm telling you it's the same code i posted earlier with some changes from point to string .

[Koushik Ghosh]

Try this code.. I have used hashset to avoid duplicate strings.

import java.util.HashSet;
import java.util.Set;

/**
 * @author Koushik Ghosh
 *
 */
public class AllCombinations {
	private static Set<String> hs = new HashSet<String>();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String str = "abaa";
		permutation("", str); 
		System.out.println(hs);
	}
	/**
	 * @param prefix
	 * @param str
	 */
	private static void permutation(String prefix, String str) {
		
		int n = str.length();
	    if (n == 0) 
	    {
	    	hs.add(prefix);
	    }
	    else {
	        for (int i = 0; i < n; i++)
	           permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
	    }
	}

}