Creating a tree of all possible combinations of {a,b,c,d}
I am an MSc conversion student who is struggling with the initial stages of coding his Association Rule Mining dissertation project.
I have a TreeNode class, which is in the process of being written.
The class is designed to create a tree that stores all possible combinations of a Vector alphabet of strings {a,b,c,d}
Please could somebody explain what my TreeNode class is doing so far?
I have had a lot of help with this and I can't understand why there are so many vectors and what they all do.
A few pointers (no sarcastic comments please) would be much appreciated.
The code so far:
package treenode;
import java.io.*;
import java.util.*;
public class TreeNode
{
public static final String INFO_TEXT ="A program to store a vector of string items a,b,c,d in all their possible combinations into a TreeNode class";
private Vector alphabet;
private Vector data;// this IS TreeRootData
private Vector children;
public TreeNode(Vector inputAlphabet, Vector inputData)
{
// the alphabet and data have already been parsed in.
this.alphabet = inputAlphabet;
this.data = inputData;
System.out.println("Tree node constructed with data "+displayVectorOfStrings(this.data));
children = new Vector();// we now construct the Vector of children
//createChildren();
}
public void createChildren()
{
if data.length =
// first check to see whether the current data length is the same
// as the length of the alphabet
// if it is then stop here (return;)
// we loop through the alphabet we have...
// for each candidate in the alphabet, attempt to create a new child TreeNode
// with a data Vector that is the same as the data in this TreeNode plus
// the candidate we are looking at in the alphabet. i.e. add available LHS
// NB: Do NOT add if the candidate is already in the data. {a,b,a} is wrong!
// NB: We will check to see whether data is already in the tree at a later stage
// NB: The new Child TreeNode MUST BE ADDED to the children VECTOR -
// or it will be lost
}
public static String displayVectorOfStrings(Vector vector) //Printing the Vector of Strings
{
String vectorText = "{";
for (int i=0; i<vector.size(); i++)
{
vectorText += (String)vector.elementAt(i)+",";
}
if (vector.size() > 0) vectorText = vectorText.substring(0, vectorText.length()-1);
// now we chop off the last element, replacing it with a closing bracket,
// provided that the Vector is not empty.
vectorText += "}";
return vectorText;
}
public static void main(String[] args) //main method WITH THE ARGUMENTS PASSED IN.
{
// This main class can be thought of as OUTSIDE the TreeNode class. Although
// it is in the file called TreeNode.java it is only here for convenience.
// This is the top level of the program where everything starts. It is here -
// that the alphabet is hardcoded in and that the Tree root is constructed.
displayHeading();
Vector alphabet = new Vector(); // constructing an initial alphabet,
alphabet.addElement("a");// which will eventually come from the database
alphabet.addElement("b");
alphabet.addElement("c");
alphabet.addElement("d");
System.out.println("Alphabet set to be "+TreeNode.displayVectorOfStrings(alphabet));
// the root's initial data is now made into an empty Vector...
Vector initialData = new Vector();
// the root can now be constructed
TreeNode treeRoot = new TreeNode(alphabet, initialData); // the treeRoot constructor
}
public static void displayHeading()
{
System.out.println();
System.out.println(INFO_TEXT);
}
}
> I have a TreeNode class, which is in the process of being written.
> Please could somebody explain what my TreeNode class is doing so far?
So someone else has created this skeleton implementation for you?
I've looked it over quickly and it seems that the inline documentation is supposed to act as a guideline for the implementation. The problem is, the documentation itself doesn't seem to be enough (for us) to figure out exactly what must be done.
So what we need to know is:
What EXACTLY does this TreeNode have to do?
> I have had a lot of help with this and I can't understand why there are so many vectors and what they all do.
This doesn't really help us help you. Do you know how a vector works?
The names of the vecors in use seem to indicate what data they are holding. I'm failing to understand what you need to know.
More information about what the TreeNode is; what does the ThreeNode represent is definitively needed.
First I would like to know what you mean by combinations. Do you really mean any kind of combination using the characters in the given string? Or do you mean permutations of the characters in the string?
If I understand correctly you want something like this:
root (a,b,c,d)
child1 (a,b,d,c)
child2 (a,c,b,d)
child3 (a,d,c,b)
...
...
I suggest you first specify clearly what you want to model, in an abstract way. Forget about the implementation in Java. Once the model is done, we can begin to think about an implementation.
do you intend to display this in a JTree?
do you store single letters per node? ie will the complete tree look like
__ a ____ b ____ c ____ d __
/|\/|\/|\/|\
bcdacdabdabc
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
c d b d b c c d a d a c b d a d a b b c a c a b
| | | | | | | | | | | | | | | | | | | | | | | |
d c d b c b d c d a c a d b d a b a c b c a b a
asjf
asjfa at 2007-7-14 18:59:10 >
This class seems to generate all permutations, not just all combinations.
I don't remember from which site I took this material.
You read this to find all possible combination of a set {a,b,c,d}
Consider three elements A, B, and C. It turns out that for n distinct elements there are n! permutations possible. For these three elements all of the possible permutations are listed below:
ABC, ACB, BAC, BCA, CAB, CBA
Since there are 3 elements there are 3! = 6 permutations possible.
Suppose instead of A, B, and C you have a deck of 52 playing cards. There are 52! permutations possible (i.e., the number of different ways the cards could be shuffled). Since 52! = 8x10^67, you will need to play a lot of cards before you have seen every permutation of the deck! Since shuffling the deck is a random process (or it should be), each of these 52! permutations is equally likely to occur.
Developing a non-recursive algorithm to generate all permutations of n elements is a non-trivial task. However, developing a recursive algorithm to do this requires only modest effort and this is what we will do next.
1. Let E = {e1, e2, ..., en } denote the set of n elements whose permutations we are to generate.
2. Let Ei be the set obtained by removing element i from E.
3. Let perm(X) denoted the permutations of the elements in the set X.
4. Let ei.perm(X) denote the permutation list obtained by prefixing each permutation in perm(X) with element ei.
Consider the following example, which is provided to clarify the definitions given above:
If E = {a, b, c}, then E1 = {b, c} since the element in position 1 has been removed from E to create E1. Perm(E1) = (bc, cb) since these are the only two possible permutations of the two elements which appear in E1. Finally, e1.perm(E1) = (abc, acb) which should be apparent from the value of e1 and perm(E1) since the element a is simply used as a prefix to each permutation in perm(E1).
Given these definitions, we set the recursion base case when n = 1. Since only one permutation is possible for one element, perm(E) = (e) where e is the lone element in E. When n > 1, perm(E) is the list e1.perm(E1) followed by e2.perm(E2) followed by e3.perm(E3) ?followed by en.perm(En). This recursive definition of perm(E) defines perm(E) in terms of n perm(X)s, each of which involves an X with n ?1 elements. Thus both the base component and the recursive component (of a recursive algorithm) have been established and we thus have a complete recursive technique to generate the permutations.
The following Java method is an implementation of this recursive definition of perm(E). This method will output all permutations whose prefix is list[0:k-1] and whose suffixes are the permutations of list[k:m]. By invoking the method with Perm(list, 0, n-1) all n! permutations of list[0: n-1] will be produced. [This is because this invocation will set k = 0 and m = n ?1, so the prefix of the generated permutations is null and their suffixes are the permutations of list[0: n-1]. When k = m, there is only one suffix which is list[m] and list[0: m] defines a permutation that is to be produced. When k < m, the else clause is executed.
In the algorithm, let E denote the elements in list[k: m] and let Ei be the set obtained by removing ei = list from E. The first swapping sequence in the for-loop has the effect of setting list[k] = ei and list[k+1: m] = Ei. Therefore, next statement which is the call to perm computes ei.perm(Ei). The final swapping sequence restores list[k: m] to its state prior to the first swapping sequence (the state is was in before the recursive call occurred).
public static void perm(Object [] list, int k, int m)
{//generate all permutations of list[k:m]
int i;Object temp;
if (k == m) //list has one permutation ?so output it
{for (i = 0; i <= m; i++)
System.out.print(list);
System.out.println;
}
else //list has more than one permutation ?so generate them recursively
for (i = k; i <= m; i++)
{temp = list[k];//these next three lines are a simple swap function
list[k] = list;
list = temp;
perm(list, k+1, m); //the recursive call
temp = list[k];//reset the order in the list
list[k] = list;
list = temp;
}//end for-loop
} //end method perm
See the program pasted below that prints all possible combination of a set {a,b,c,d}
public class Perm
{
public Perm()
{
}
public static void main(String[] args)
{
String s = "abcd";
char [] chars = s.toCharArray();
perm(chars, 0);
}
public static void perm(char [] list, final int k)
{
int i;
char temp;
if (k == list.length-1) //list has one permutation, so output it
{
for (i = 0; i <= list.length-1; i++)
System.out.print(list);
System.out.println();
}
else { //list has more than one permutation, so generate them recursively
for (i = k; i <= list.length-1; i++)
{
temp = list[k];//these next three lines are a simple swap function
list[k] = list;
list = temp;
perm(list, k+1); //the recursive call
temp = list[k];//reset the order in the list
list[k] = list;
list = temp;
}//end for-loop
}
}
}
Message to all who have responded so far:
Thank you very much for your feedback and help.
Sorry I haven't been very forthcoming with my responses.
I have gotten in a bit of a muddle over this, but do at least now
realise that what I am looking for is an algorithm that will compute
non-redundant permutations only,.. i.e. taking {a,b,c} would produce {a}, {b}, {c}, {a,b}, {a,c}, {a,b,c}, {b,c}... thats it I think.
With {a,b,c,d} there would be 15 possible non-redundant permutations.
Any further feedback would be much appreciated and I hope to post a solution to this problem soon.
How many items are in your set? If it's less than 32 or 64, then you can use bit-fiddling. Otherwise, you need a recusinv algorithim.
The easiest way to do this is with the "collections" API in java.
package untitled1;
import java.util.*;
/**
* @author Paul Murray, © 2003
*/
public class Main {
public Main() {
}
public static void main(String[] args) {
new Main().go();
}
void go() {
Set items = new TreeSet();
items.add("apple");
items.add("banana");
items.add("carrot");
items.add("dogfood");
items.add("eggplant");
Collection result = getPowerSet(items);
for(Iterator i = result.iterator(); i.hasNext();) {
System.out.println(i.next());
}
}
Collection getPowerSet(Set items) {
Set notUsedYet = new TreeSet();
Set thisPowerSet = new TreeSet();
Collection result = new ArrayList();
notUsedYet.addAll(items);
computePowerSet(notUsedYet, thisPowerSet, result);
return result;
}
void computePowerSet(Set notUsedYet, Set thisPowerSet, Collection result) {
if(notUsedYet.isEmpty()) {
if(!thisPowerSet.isEmpty()) {
Set copy = new TreeSet();
copy.addAll(thisPowerSet);
result.add(copy);
}
return;
}
Object item = notUsedYet.iterator().next();
notUsedYet.remove(item);
computePowerSet(notUsedYet, thisPowerSet, result);
thisPowerSet.add(item);
computePowerSet(notUsedYet, thisPowerSet, result);
thisPowerSet.remove(item);
notUsedYet.add(item);
}
}
The solution is simple: a binary counter algorithm
public class Soln {
public static void checkArray(boolean[] b, int i, String[] elem){
if (i == b.length) {
for (int j = 0; j < b.length; j++) {
if (b[j]) System.out.print(elem[j]);
}
System.out.println();
return;
}
b[ i ] = false;
checkArray(b, i+1, elem);
b[ i ] = true;
checkArray(b, i+1, elem);
}
public static void main(String[] args) {
checkArray(new boolean[4], 0, new String[] {"a", "b", "c", "d"});
}
}
output:
d
c
cd
b
bd
bc
bcd
a
ad
ac
acd
ab
abd
abc
abcd
How dull! Let's do it nonrecursively!
public class Main3 {
public static void main(String[] args) {
String[] v = {"apple", "banana", "kumquat", "octopus"};
boolean[] a = new boolean[v.length];
outer:
for(;;) {
for(int i = 0; i< a.length; i++) {
if(!a[i]) {
a[i] = true;
break;
}
else {
a[i] = false;
if(i == a.length-1) {
break outer;
}
}
}
for(int i = 0; i< a.length; i++) {
if(a[i]) {
System.out.print(v[i]);
System.out.print(' ');
}
}
System.out.println();
}
}
}
The company you work for must spend a lot of money on code maintenance...
I really think you need to formally define the problem that you are trying to solve. Here is a possible way of understanding "all possible permutations of {a,b,c,d}":
In theory, a permutation is rearrangement of elements in an ordered set S into a one-to-one correspondence with S itself. The number of permutations on a ordered set of n elements is given by n!.
The number of subsets of k elements that can be obtain from a given set of n elements is given by n!/(n-k)!.
So, we have:
- 4! permutations of the original set {a,b,c,d}
- 24 different ordered subsets of three elements
- 12 different ordered subsets of 2 elements
- 4 subsets of 1 element.
i think the OP has gone awol :)
asjfa at 2007-7-14 18:59:10 >
