String combinations & permutations

[Nick Georgides]

Hi,

I'm trying to program an algorithm that returns all the combinations & permutations that can be made out of a given string.

e.g. for a "abc" it must return:

    
a
b
c
aa
ab
ac
ba
bb
bc
ca
cb
cc
aaa
aab
aac
aba
abb
abc
aca
acb
acc
...
...
... etc. 

So far I've come up with:

String string1 = "abc";
char[] validCharacters = string1.toCharArray();
 
for (int i=0; i<validCharacters.length; i++){
String result = null;
result=validCharacters[i]+"";
String temp1 = result;
System.out.println(result);

for (int ii=0; ii<validCharacters.length; ii++){
result=temp1+validCharacters[ii];
String temp2=result;
System.out.println(result);
 
for (int iii=0; iii<validCharacters.length; iii++){
result=temp2+validCharacters[iii];
System.out.println(result);
}
}
} 

But that only works in the case of "abc". Any advice on how I could make this more dynamic?

~Nick

[Henry Wong]

But that only works in the case of "abc". Any advice on how I could make this more dynamic?

Notice the pattern in your code? You have a for loop that has an for loop that looks pretty much like itself.

Doesn't the pattern look recursive?

Henry

[Nick Georgides]

Hi Henry, thanks for your reply.

I don't seem to grasp the concept of recursion Any help is much appreciated.

So, I moved the for-loop in another method and created the following:

.....
for (int i=0; i<validCharacters.length; i++){
String result = null;
result=validCharacters[i]+"";
String temp1 = result;
System.out.println(result);
test(validCharacters, temp1);

}
}

public void test(char[] validCharacters, String temp){
for (int i=0; i<validCharacters.length; i++){
String result=temp+validCharacters[i];
System.out.println(result);
test(validCharacters, temp);
}
}    

which I guess is really stupid judging from its output.

~Nick

[Henry Wong]

I don't seem to grasp the concept of recursion. Any help is much appreciated.

There are two parts to any recursive algorithm. The first part is that the algorithm should do part of the work, which results in nearly the same problem, but closer to the solution. For example, you do the 1st character of the string permutation, but you depend on the algorithm to do the rest.

The second part is the end game. There comes a point where the problem is so easy that the recursive algorith is not needed anymore. For example, if there is only 1 letter left, then the result is simply a single output line.

You have done the first part. Now how do you determine when you are done?

Henry

[Sai Narasimha Reddy]

import java.util.*;
/**
 *
 * @author Sai
 */
public class MyPermutations {
    Set<String> permutations;
    String phrase;
    
    /** Creates a new instance of MyPermutations */
    public MyPermutations() {
    }
    public MyPermutations(String phrase) {
        this.phrase = phrase;
    }
    public static void main(String[] args) {
        MyPermutations p = new MyPermutations("abc");
        p.permutations = new HashSet<String>();
        p.permute("",p.phrase);        
        Iterator it = p.permutations.iterator();        
        while(it.hasNext()) {
            System.out.println(it.next());
        }
        System.out.println("count = "+p.permutations.size());
    }
    public void permute(String fixedPart,String variablePart) {
        if(variablePart.length()>1) {
            for(int i=0;i<variablePart.length();i++) {
                variablePart = shift(variablePart);
                this.permutations.add(fixedPart+variablePart);                
                permute(fixedPart+variablePart.charAt(0),variablePart.substring(1) );                
            }
        } else {
            this.permutations.add(fixedPart+variablePart);
        }
    }
    public static String shift(String var) {
        String result = ""+var.charAt(var.length()-1);
        result += var.substring(0,var.length()-1);
        return result;
    }
}

[edit]Add code tags. CR[/edit]
[ September 10, 2008: Message edited by: Campbell Ritchie ]

[Sai Narasimha Reddy]

output was
cab
abc
cba
bac
bca
acb
count = 6

[Brighton Kukasira]

Hi Nick,

I have only reached your question a couple of months later, but I hope my solution will still be helpful to you or other visitors to this page.


If you like this post please put some emoticons. I really enjoy it when viewers put these emoticons to express their emotions about my posts.

Regards,
Brighton Kukasira

package com.kukasira.brighton.perm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * This class provides combinations of different objects.
 *
 * If you have a set of objects and select some of them,
 * that selection without regard to their order is called a combination.
 * If you have n objects there are 2n (2 to the nth power)
 * possible combinations ranging from none present to all present.
 * Write a program or an algorithm that returns all the combinations
 * that can be made out of a given string.
 * For example if the input is "abc" it must return:
 *
 * a
 * b
 * c
 * aa
 * ab
 * ac
 * ba
 * bb
 * bc
 * ca
 * cb
 * cc
 * aaa
 * aab
 * aac
 * aba
 * abb
 * abc
 * aca
 * acb
 * acc
 * ...
 * ...
 * ... etc.
 * 
 * @author Brighton Kukasira
 */
public class Permutation {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Permutation perm = new Permutation();
        perm.run();
    }

    private void run() {
        Symbol[] domain = createInputData(5);
        Map<String, Symbol[]> buckets = new LinkedHashMap<String, Symbol[]>();

        for (int width = 1; width <= domain.length; width++) {
            Symbol[] bucket = new Symbol[width];
            combinations(bucket, domain, buckets);
        }
        
        for (Iterator<String> it = buckets.keySet().iterator(); it.hasNext();) {
            String key = it.next();
            System.out.println(key);
        }
    }

    private void combinations(Symbol[] bucket, Symbol[] domain,
            Map<String, Symbol[]> buckets) {

        if (isNotFull(bucket)) {
            int nextSlot = findNextEmptySlot(bucket);

            for (int i = 0; i < domain.length; i++) {
                Symbol[] bucketCopy = new Symbol[bucket.length];
                System.arraycopy(bucket, 0, bucketCopy, 0, bucketCopy.length);
                bucketCopy[nextSlot] = domain[i];

                // create a new domain leaving
                // out the object that has been used
                Symbol[] domainCopy = new Symbol[domain.length - 1];
                if (i == 0) {
                    System.arraycopy(domain, 1, domainCopy, 0, domainCopy.length);
                } else {
                    System.arraycopy(domain, 0, domainCopy, 0, i);
                    System.arraycopy(domain, i + 1, domainCopy, i, domainCopy.length - i);
                }

                combinations(bucketCopy, domainCopy, buckets);
            }
        } else {
            // these two lines assumes that "AC" and CA are the same so the later is not printed
            // if you want to see all the output;
            // remove the Arrays.sort
            // change the buckets variable from a Map to a normal List
            Arrays.sort(bucket);
            buckets.put(Arrays.asList(bucket).toString(), bucket);
        }
    }

    boolean isNotFull(Symbol[] bucket) {
        boolean value = false;

        for (int i = 0; i < bucket.length; i++) {
            Symbol symbol = bucket[i];

            if (isNotValid(symbol)) {
                value = true;
                break;
            }
        }
        return value;
    }

    boolean isNotValid(Symbol symbol) {
        return symbol == null || symbol.getName() == null ||
                symbol.getName().trim().equals("");
    }

    private Symbol[] createInputData(int size) {
        Symbol[] value = new Symbol[]{
            new Symbol("A"), new Symbol("B"), new Symbol("C"), new Symbol("D")
                    , new Symbol("E")
        };
        return value;
    }

    int findNextEmptySlot(Symbol[] bucket) {
        int value = -1;

        for (int i = 0; i < bucket.length; i++) {
            Symbol symbol = bucket[i];

            if (isNotValid(symbol)) {
                value = i;
                break;
            }
        }
        return value;
    }
}

/**
 * This class holds the items that are used in the combinations.
 * The author of this class uses this permutaion and combinations
 * for other purpose not just for letters (abc).
 * In that case this class can be replaced by another class
 * and the permutation will still work
 * 
 * @author Brighton Kukasira
 */
class Symbol implements Comparable<Symbol> {

    private String name;

    Symbol(String aName) {
        this.name = aName;
    }

    /**
     * @return the name
     */
    public String getName() {
        return name;
    }

    /**
     * @param name the name to set
     */
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        boolean value = false;

        if (o instanceof Symbol) {
            value = name.equals(((Symbol) o).getName());
        }
        return value;
    }

    @Override
    public int hashCode() {
        int hash = 7;
        hash = 79 * hash + (this.name != null ? this.name.hashCode() : 0);
        return hash;
    }

    public int compareTo(Symbol o) {
        return name.compareTo(o.getName());
    }

    @Override
    public String toString() {
        return name;
    }
}

[Campbell Ritchie]

Welcome to JavaRanch

I am afraid, not only is such a reply to a year-old post of little use, but also it does nobody any good to be given a straight answer like that. Please look at this FAQ too. Look what it says at the top of the beginners' contents page:

We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.

I have reluctantly felt obliged to move your solution to our "deleted" forum.