Thread: Cominations results

Hi, I want to find which are the possible combinations, without repetitions, of 9 objects in groups of 6. To calculate the number of possible combination I have to use the following formula which is used also as a mathematical function in Microsoft Excell called "Combin" and returns the binomial coefficient "n choose k", the number of k-combinations of an n-element set without repetition.
But, how could I find which are these combinations?
Any advice could be very helpful.

Originally Posted by yannis

Hi, I want to find which are the possible combinations, without repetitions, of 9 objects in groups of 6. To calculate the number of possible combination I have to use the following formula which is used also as a mathematical function in Microsoft Excell called "Combin" and returns the binomial coefficient "n choose k", the number of k-combinations of an n-element set without repetition.
But, how could I find which are these combinations?
Any advice could be very helpful.

Your question is not clear. Possibly you mean: The binomial coefficient allows us to count the combinations, but how do we enumerate the combinations? Is this what you mean? A recursive algorithm can be used to accomplish this; I can fill in more details if this is what you want.

The formula I described above allows me to calculate the number of possible combinations of n objects in groups of k, without repetitions. What I want is to find which are these combinations, not how many they are. For example three balls (red,green,blue) combined in groups of two can give three different combinations, without repetitions. I am interested on finding which are these combinations (they are: red-green,red-blue and green-blue). How could I do that for a larger set of objects?

Originally Posted by yannis

The formula I described above allows me to calculate the number of possible combinations of n objects in groups of k, without repetitions. What I want is to find which are these combinations, not how many they are. For example three balls (red,green,blue) combined in groups of two can give three different combinations, without repetitions. I am interested on finding which are these combinations (they are: red-green,red-blue and green-blue). How could I do that for a larger set of objects?

Recursively in Java:

Code:

import java.util.ArrayList;

public class EnumCombs {
    static String[] objs = {"cat", "hat", "strategy", "cool", "red", "helicopter"};
    static int k = 3, count = 0;
    
    public static void main(String[] args) {
        recurse(0, new ArrayList<String>());
        System.out.println("\n" + count + " combinations found.");
    }
    
    static void recurse(int x, ArrayList<String> comb) {
        if(comb.size() == k) {
            count++;
            System.out.println(comb);
            return;
        }
        if(objs.length - x < k - comb.size()) return;
        int i;
        for(i = x; i < objs.length; i++) {
            ArrayList<String> nextComb = new ArrayList<String>(comb);
            nextComb.add(objs[i]);
            recurse(i + 1, nextComb);
        }
    }
}

Example is for a list. Output:

Code:

[cat, hat, strategy]
[cat, hat, cool]
[cat, hat, red]
[cat, hat, helicopter]
[cat, strategy, cool]
[cat, strategy, red]
[cat, strategy, helicopter]
[cat, cool, red]
[cat, cool, helicopter]
[cat, red, helicopter]
[hat, strategy, cool]
[hat, strategy, red]
[hat, strategy, helicopter]
[hat, cool, red]
[hat, cool, helicopter]
[hat, red, helicopter]
[strategy, cool, red]
[strategy, cool, helicopter]
[strategy, red, helicopter]
[cool, red, helicopter]

20 combinations found.

Here's a link to help you understand recursive programming. (I also use backtracking above.)

That is want i was searching, thank you undefined! But I cannot compile it. I use JDK 1.6 and I get an error that says that EnumCombs is public and should be declared in a file called EnumCombs.java.. I tried to rename the file but I get again error. The code you gave me is for one single file? If yes, how you compiled it and which filename you used? Thank you anyway!

Originally Posted by yannis

That is want i was searching, thank you undefined! But I cannot compile it. I use JDK 1.6 and I get an error that says that EnumCombs is public and should be declared in a file called EnumCombs.java.. I tried to rename the file but I get again error. The code you gave me is for one single file? If yes, how you compiled it and which filename you used? Thank you anyway!

Yes, standalone, and the file name must match, so EnumCombs.java . Please say what the compiler error was after you changed the file name!

Edit: Here's one guess; if you're using Windows and the file extensions are hidden, then maybe you think it's named EnumCombs.java but actually it's EnumCombs.java.txt . Let me know if you think this might be; I don't know your level of computer knowledge.

The extension is just java. I runned cmd as administrator and it compiled it. Then, in order to interpret and run it, I embeded it on an html file as following:

<Html>
<Head>
<Title>EnumCombs</Title>
</Head>
<Body>
<APPLET code="EnumCombs.class" codebase="html/" align="baseline" width="200" height="200"> </APPLET>
</Body>
</Html>

Is this OK? I think this is the right way. I am not expert but I have some basic knowledge on progmramming.
And when I open the file with internet explorer I get error. The error details describe the following:

Java Plug-in 1.6.0_21
Using JRE version 1.6.0_21-b06 Java HotSpot(TM) Client VM
User home directory = C:\Users\yannis
----------------------------------------------------
c: clear console window
f: finalize objects on finalization queue
g: garbage collect
h: display this help message
l: dump classloader list
m: print memory usage
o: trigger logging
q: hide console
r: reload policy configuration
s: dump system and deployment properties
t: dump thread list
v: dump thread stack
x: clear classloader cache
0-5: set trace level to <n>
----------------------------------------------------


load: class EnumCombs.class not found.
java.lang.ClassNotFoundException: EnumCombs.class
at sun.plugin2.applet.Applet2ClassLoader.findClass(Un known Source)
at sun.plugin2.applet.Plugin2ClassLoader.loadClass0(U nknown Source)
at sun.plugin2.applet.Plugin2ClassLoader.loadClass(Un known Source)
at sun.plugin2.applet.Plugin2ClassLoader.loadClass(Un known Source)
at java.lang.ClassLoader.loadClass(Unknown Source)
at sun.plugin2.applet.Plugin2ClassLoader.loadCode(Unk nown Source)
at sun.plugin2.applet.Plugin2Manager.createApplet(Unk nown Source)
at sun.plugin2.applet.Plugin2Manager$AppletExecutionR unnable.run(Unknown Source)
at java.lang.Thread.run(Unknown Source)
Caused by: java.io.FileNotFoundException: C:\html\EnumCombs\class.class (The system is unable to find the specified path on the disk)
at java.io.FileInputStream.open(Native Method)
at java.io.FileInputStream.<init>(Unknown Source)
at java.io.FileInputStream.<init>(Unknown Source)
at sun.net.http://www.protocol.file.FileURLConn...onnect(Unknown Source)
at sun.net.http://www.protocol.file.FileURLConn...Stream(Unknown Source)
at sun.plugin2.applet.Applet2ClassLoader.getBytes(Unk nown Source)
at sun.plugin2.applet.Applet2ClassLoader.access$000(U nknown Source)
at sun.plugin2.applet.Applet2ClassLoader$1.run(Unknow n Source)
at java.security.AccessController.doPrivileged(Native Method)
... 9 more
Exception: java.lang.ClassNotFoundException: EnumCombs.class


Both EnumCombs.class and EnumCombs.htm are stored on C:

Any advice?

Originally Posted by yannis

The extension is just java. I runned cmd as administrator and it compiled it. Then, in order to interpret and run it, I embeded it on an html file as following:

<Html>

...

Both EnumCombs.class and EnumCombs.htm are stored on C:

Okay, so this is not an applet but rather an application, so that should explain it. It compiled without errors so you're almost there. Also from within command prompt, when you're in directory C:\, type

Code:

java EnumCombs

I am assuming a couple things about how you set up your JDK. If I'm right then you typed this in order to compile.

Code:

javac EnumCombs.java

Let me know if this works.

(Edit)

Note: If you want to be able to copy and paste the results, you can pipe the output to a file like this:

Code:

java EnumCombs > filename.txt

You can also download Eclipse, which is a free IDE and which will let you copy and paste things from the console. It's not the only IDE out there but it is very good and preferred by many.

(Edit 2)

A very minor note. If you pipe the output to a text file like this

Code:

java EnumCombs > filename.txt

and then open with Notepad, you would see there's a missing newline between the last combination and the sentence "x combinations found." That's because Microsoft Notepad needs \r\n instead of just \n to produce a newline. If you view in a different editor like Notepad++ the program output will be fine as-is. Or you can modify that line of the Java code.

That's it undefined! It worked, I don't know how to thank you. It is not an applet, that's why. Thank you again for your time.

By the way, the code you wrote it yourself or you found it somewhere? I am asking you because I am interested on enumerating permutations also.

Originally Posted by yannis

By the way, the code you wrote it yourself or you found it somewhere? I am asking you because I am interested on enumerating permutations also.

I wrote it. There's an example of permutations code here, under anagrams. It assumes that all elements (in this case, characters) are distinct. If you need help let me know.

I don't want to be tiresome but I have again problem on compiling.. I get 4 errors;


I copied the code and saved it as "Anagrams.java"

Could you advice me anything?

Originally Posted by yannis

I don't want to be tiresome but I have again problem on compiling.. I get 4 errors;

I copied the code and saved it as "Anagrams.java"

Could you advice me anything?

You're not being tiresome; the example on that page uses a custom library for I/O, and you can't run it out of the box unless you have acm.program.* available.

Here's an adaptation that is ready to compile

Code:

import java.util.Scanner;

public class Anagrams1 {
    static int count = 0;
    
    public static void main(String[] args) {
        Scanner in = new  Scanner(System.in);
        System.out.print("Input a string with all characters distinct: ");
        String word = in.nextLine();
        recurse("", word);
        System.out.println("\n" + count + " permutations found.");
    }
    
    static void recurse(String prefix, String word) {
        if(word.length() <= 1) {
            count++;
            System.out.println(prefix + word);
            return;
        }
        for(int i = 0; i < word.length(); i++) {
            String cur = word.substring(i, i + 1);
            String before = word.substring(0, i); // letters before cur
            String after = word.substring(i + 1); // letters after cur
            recurse(prefix + cur, before + after);
        }
    }
}

Here's another way, using a list of strings

Code:

import java.util.ArrayList;

public class Anagrams2 {
    static String[] objs = {"cat", "hat", "strategy", "cool", "red", "helicopter"};
    static int count = 0;
    
    public static void main(String[] args) {
        int i;
        ArrayList<String> start = new ArrayList<String>();
        for(i = 0; i < objs.length; i++)
            start.add(objs[i]);
        recurse(new ArrayList<String>(), start);
        System.out.println("\n" + count + " permutations found.");
    }
    
    static void recurse(ArrayList<String> sofar, ArrayList<String> left) {
        if(left.size() == 0) {
            count++;
            System.out.println(sofar);
            return;
        }
        int i;
        for(i = 0; i < left.size(); i++) {
            ArrayList<String> nextSofar = new ArrayList<String>(sofar),
                    nextLeft = new ArrayList<String>(left);
            nextSofar.add(nextLeft.remove(i));
            recurse(nextSofar, nextLeft);
        }
    }
}

Lastly, here's a way that doesn't assume all elements of the list are distinct. (This is permuatations of a multiset.)

Code:

import java.util.ArrayList;

public class Anagrams3 {
    static String[] objs = {"cat", "hat", "strategy", "cool", "red", "cat"};
    static int count = 0;
    
    public static void main(String[] args) {
        int i;
        ArrayList<String> start = new ArrayList<String>();
        for(i = 0; i < objs.length; i++)
            start.add(objs[i]);
        recurse(new ArrayList<String>(), start);
        System.out.println("\n" + count + " permutations found.");
    }
    
    static void recurse(ArrayList<String> sofar, ArrayList<String> left) {
        if(left.size() == 0) {
            count++;
            System.out.println(sofar);
            return;
        }
        int i;
        String s;
        ArrayList<String> used = new ArrayList<String>();
        for(i = 0; i < left.size(); i++)
            if(!used.contains(s = left.get(i))) {
                ArrayList<String> nextSofar = new ArrayList<String>(sofar),
                        nextLeft = new ArrayList<String>(left);
                nextSofar.add(nextLeft.remove(i));
                recurse(nextSofar, nextLeft);
                used.add(s);
            }
    }
}

Thats it! But, if I want to find the permutations of n objects (or letters of a word, it;s OK) in groups of 2? I have to declare a new variable (e.x. "static int k=2"), right? What other changes should I have to do on the code? I tried to compare the code with the one of the EnumCombs but is a little different..


static void recurse(String prefix, String word) {
if(word.length() <= k)

Is this enough?