1
\$\begingroup\$

I wrote this code to form combinations of a 16 bit binary number (I know it is in output is string format, but it is my goal to just print all possible 16 bit binary numbers). My question is, can this code be optimized? How can I calculate the time complexity of this code?

public class Combinations {

    static int len;

    public static void formCombinations(StringBuilder start,String[] possible)
    {
        if(start.length()==len)
        {
            System.out.println(start);
            return;
        }
        for(int i=0;i<possible.length;i++)
        {   
            formCombinations(start.append(possible[i]), possible);
            start.deleteCharAt(start.length()-1);
        }
    }

    public static void formCombinations(int len,String[] a) {
        Combinations.len=len;
        formCombinations(new StringBuilder(""), a);
    }

    public static void main(String[] args) {
        String a[]={"0","1"};
        formCombinations(16, a);
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Change new StringBuilder("") to new StringBuilder() \$\endgroup\$
    – Steve Kuo
    Mar 26, 2015 at 23:03
  • \$\begingroup\$ @SteveKuo why, can you please explain? what is the difference between those two? \$\endgroup\$
    – BKC
    Mar 26, 2015 at 23:27
  • 1
    \$\begingroup\$ Is this java? Please tag your question with a language. \$\endgroup\$
    – RubberDuck
    Mar 27, 2015 at 0:36

2 Answers 2

3
\$\begingroup\$
  • Give your operators some breathing space, e.g.:

    for (int i = 0; i < possible.length; i++)
    
  • possible is not very good name (it implies that something is impossible. I recommend alphabet instead.

  • possible never changes. It makes it a good candidate for a final class member. Passing it down recursively wastes some stack space.

  • I don't think overloading formCombinations is warranted.

  • I see nothing obviously wrong performance wise. After all, you generate all permutations, and you generate each permutation exactly once. Of course, StringBuilder may impose some hidden penalties; Java experts would give an authoritative answer.

    In any case, an iterative solution requires less space, doesn't need a StringBuilder, and may serve as an iterator (in a sense of supporting has_next() and next() methods). I highly recommend implementing it: it is simple and instructive. Hint: think of next permutation as adding 1 to a binary number.

\$\endgroup\$
0
\$\begingroup\$
public static void formCombinations(int len , String[] a){
     //calculate the number of possible combinations
     int totalRepeats = Math.pow(a.length , len);
     //list of indices from which the resulting strings will be built
     int[] path = new int[len];

     boolean increaseNext;

     //the array of currently used elements (intially populated)
     String[] curString = new String[len];
     for(int i = 0 ; i < len ; i++)
          curString[i] = a[i];

     //the index of the highest increased element (lowest index)
     int highestIncreased;

     for(int i = 0 ; i < totalRepeats ; i++){
         //calculate the next combination of elements
         increaseNext = true;
         for(highestIncreased = len - 1 ; increaseNext ; highestIncreased--){
              ++path[j];
              if(increaseNext = (path[j] == len))
                   path[j] = 0;
         }

          //update the string
          for(; highestIncreased < len ; highestIncreased++)
               curString[highestIncreased] = a[path[highestIncreased]];

          //print the string (might be optimized aswell)
          System.out.println(Arrays.toString(curString));
     }
}

Since your code is recursive, you need a.length ^ len method calls. method calls are quite resource intensive. So this should actually run faster. calculating time complexity is a bit too complicated to explain it here. and time complexity is usually only calculated for algorithms with input.

NOTE: i haven't tested this code, so it might be buggy. but it should show how it basically works.

\$\endgroup\$
4
  • \$\begingroup\$ actually, its not causing stack overflow, and it is working perfectly. What if I want to form combinations of array {"a","b","c","d","e"}, the method you said will only generate binary numbers. \$\endgroup\$
    – BKC
    Mar 26, 2015 at 23:26
  • \$\begingroup\$ if you want characters, simply replace Integer.toBinaryString((short) i) with (char) i. for the stack overflow, my bad, i misunderstood the code \$\endgroup\$
    – Paul
    Mar 26, 2015 at 23:28
  • \$\begingroup\$ sorry that my question is misleading. But I want to form combinations of 16 letter word that can be formed using 5 letters {"a","b","c","d","e"}. \$\endgroup\$
    – BKC
    Mar 26, 2015 at 23:31
  • \$\begingroup\$ ok, now i get it, there are still ways to optimize this. ill edit to post to match the actual requirements \$\endgroup\$
    – Paul
    Mar 26, 2015 at 23:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.