9 replies to this topic

[turtled]

I'm trying to create a method that will take a given array of letters and generate a two-dimensional array containing all letter combinations, including sub-combinations.

So for the letters: abc

I want a two-dimensional array of characters: abc acb bac bca cab cba ab ac ba bc ca cb a b c

It is acceptable if the two dimensional array contains repeated sub-combinations. So in the above example the implementation would be ok if it generated the following two dimensional array:

abc acb bac bca cab cba ab a b ac a c ba b a bc b c ca c a cb c b

I'm having trouble creating a recursive algorithm to do this.

[Roman Y]

I didn't get how the 2D array should look like. Write it in 2D so I may get the idea. (and why does it have to be recursive and not iterative?)

[turtled]

It can be iterative, I thought recursion might be more straightforward.

Sorry it doesn't need to be a 2d array. I just need an array where each member of the array is itself an array of characters.

[sourlemon]

If you were to do it by hand, how would you do it?

[hArrayList]

You could use a binary number representation to do this. I will adapt a method i have in my class for your purpose. I do not have time to test the modification. The following may give you an general idea about how to attack the problem.

  

    private ArrayList<Integer> makeCombination(int n){

    ArrayList<Integer> combinationList = new ArrayList<Integer>();

   

        int divisor = n;

        int combinationNumber = 0;

        while (divisor != 0){

            if (divisor % 2 == 1){

                combinationNumber++;

                combinationList.add(combinationNumber);

            }else{

                combinationNumber++;

            }

            divisor=divisor/2;

        }

        return combinationList;


    }//Method end

The above method will give you the integer positions you are looking for ie

  // n = 1    ArrayList contains 1

  // n = 2    ArrayList contains 2

  // n = 3    ArrayList contains 1 2

  // n = 4    ArrayList contains 3

  // n = 5    ArrayList contains 1 3

  // n = 6    ArrayList contains 2 3

  // n = 7    ArrayList contains 1 2 3


  // You may note this is all the combinations of "abc" only in integer form 

Another thing to take into account is that "abc" contains 3 letters. Three letters has seven combinations. So to build all the index positions for your string you need to call the buildCombination method seven times. Here is a general method to find the number of combinations needed.

    public int findTop(int n){

         return (1 << n) - 1;

    }


    // or i suppose you could adapt this to


    public int findTop(String s){

         int n = s.length(); // so as not to confuse with brackets in thee line below

         return (1 << n) - 1;

    }

    

With the above you could now create an ArrayList containing all the index values you need.

    public void general(){

         ArrayList<Integer> colllect = new ArrayList<Integer>();

         String str = "TEST";

         int n = findTop(str);

         

         for (int i = 1; i <= n; i++)

              collect.add(makeCombination(i));

     

     }

Obviously you can set this up in a class structure, with the buildCombination method in a Combination class and the collecter methods in another class using the combination class. I also leave to you the matching of integers in the combination ArrayList with the String position. If you have trouble with this just reply and i will help. Good luck and i hope this helps.:c-smile:

[hArrayList]

First you need to understand how to find the number of combination contained in your string.

  // 2 to the power of the number -1

  // and in the code i use the shift operator


   public int findTop(int n){

        return (1 << n)-1;

   }


   // an adapted version for your string maybe


   public int findTop(String str){

         int n = str.length();

         return (i << n)-1;

   }

I will know create a general Combination class that return a list of numbers that represent the combination for that particular number.

    public class Combination{


    private ArrayList<Integer> combinationList;

    private int n;


    /**

     * @param n an int value between 1 and 1023.

     */

    Combination(int n){


        this.n = n;

        comboRep = "";

        combinationList = new ArrayList<Integer>();

        makeCombination();


    }//Constructor end


    /**

     * @return combinationList an ArrayList of Integers that represent the

     * numbers in a given combination

     */

    public ArrayList<Integer> getLine(){

        return combinationList;

    }//Method end


    /**

     * @return a string representation of a combination for a given number.

     */

    public String toString(){

        for (Integer i: combinationList)

        {

            comboRep = comboRep + Integer.toString(i);

            comboRep = comboRep + " ";

        }

        return comboRep;

    }//Method end


    /**

     * The engine of the class that builds a combination line for a given number. 

     */

    private void makeCombination(){


        int divisor = n;

        int combinationNumber = 0;

        while (divisor != 0){

            if (divisor % 2 == 1){

                combinationNumber++;

                combinationList.add(combinationNumber);

            }else{

                combinationNumber++;

            }

            divisor=divisor/2;

        }

    }//Method end


}

Here is some code to use the above Combo class and the findTop method.

       Class Hypothetical(){


         public void useCombo(){


            ArrayList<Integer> cList = new ArrayList<Intgeger>();

            int top = findTop("abc"); // wherever this maybe.


            for (int i = 0; i <= top; i++){


                   Combination c = new Combination(i);

                   System.out.println(c.toString);

                   cList.add(c.getLine()); // collect the combination list.

            }

         }


        }

If you match the index positions returned by the combo class with string indexes then you can get the output you desire. Hope this makes sense and gives you some idea. If not i will try return to clarify things. I have handballed this in so i have not checked for typo errors.:c-smile:

[lethalwire]

I like free answers.

[hArrayList]

Lethalwire, thats what the forum is for. If the guy who asked for the code understands how to use it then he is worthy of his master. Lets face it years ago i used to write my own sort algorithms, know i leave it to the boys at Sun. I have given one way to create combinations, it can be adapted to create permutation. Its free, so what. I dont mind giving a little bit of my lunch break to others. And admit it Lethal you could not create that little gem in a million years of meditation on Xanado.:c-smile:
It was also used in a certain bet calculator and yes i have been paid.

[lethalwire]

Handing out code isn't what the forum is for. You could have easily guided the OP in the proper direction for a good solution to this problem.

I really don't care if you write your own algorithms. Next time we're on our coffee break at starbucks you could gladly tell me in person why I couldn't program something like this in a million years. I mean you know me so well right?

[hArrayList]

Well if you could code a combination class, why didn't you tell the op. If you were to do it by hand was your advice,LOL. Your talking about a concept Fermat had trouble with (or should i say an abstract concept that not everyone is familiar with, but is useful to have, if you understand how to use the code given to you.):c-smile: I will continue to be helpfull, see the Grid class thread, and if the poster wants code to detect the neighbouring square i shall give the code free in my next coffee break, not Starbucks i may add, i have a Flask:c-smile:.