Page 1 of 2 12 LastLast
Results 1 to 15 of 22

Math Help - Cominations results

  1. #1
    Newbie
    Joined
    Jul 2010
    Posts
    11

    Combinations' 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.
    Last edited by yannis; August 27th 2010 at 03:09 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yannis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    11
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yannis View Post
    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 \displaystyle \binom{6}{3} 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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Here's a link to help you understand recursive programming. (I also use backtracking above.)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Jul 2010
    Posts
    11
    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!
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yannis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Jul 2010
    Posts
    11
    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yannis View Post
    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.
    Last edited by undefined; July 18th 2010 at 07:04 AM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Jul 2010
    Posts
    11
    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.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Jul 2010
    Posts
    11
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yannis View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Jul 2010
    Posts
    11
    I don't want to be tiresome but I have again problem on compiling.. I get 4 errors;
    Cominations results-no-title.jpg

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

    Could you advice me anything?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by yannis View Post
    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);
                }
        }
    }
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Newbie
    Joined
    Jul 2010
    Posts
    11
    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?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. different results
    Posted in the Calculus Forum
    Replies: 5
    Last Post: October 20th 2011, 04:44 AM
  2. Formula from results
    Posted in the Business Math Forum
    Replies: 0
    Last Post: October 13th 2010, 07:09 PM
  3. Concluding Results
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: October 21st 2008, 04:40 AM

Search Tags


/mathhelpforum @mathhelpforum