Write this more efficiently?

Question

I have the following code:

    Integer cr = 3;
    String y = "\"\r\n\"";

    for (Integer i = 0; i < cr; i++)
    {
        for (Integer j = 0; j < cr; j++)
        {
            for (Integer k = 0; k < cr; k++)
            {
                for (Integer l = 0; l < cr; l++)
                {
                    for (Integer m = 0; m < cr; m++)
                    {
                        for (Integer n = 0; n < cr; n++)
                        {
                            for (Integer o = 0; o < cr; o++)
                            {
                                for (Integer p = 0; p < cr; p++)
                                {
                                    consolus.append(i.toString()+j.toString()+k.toString()+l.toString()+m.toString()+n.toString()+o.toString()+p.toString() + y);
                                }
                            }
                        }
                    }
                }
            }
        }
    }

Is there some way I can write this more efficiently? Essentially, the output is a number 8 chars long which contains all possible numbers containing the numbers from 0 to cr. This method currently works, however it doesn't seem efficient, and then writing to the TextView consolus, only occurs after all the for statements complete.

Answer 1

Presumably you want to avoid the 8 levels of nested loops? (This isn't an efficiency thing, merely a code cleanliness issue.)

If so, use a length-8 array of integers, and use it to do "counting" in a while loop.

int[] cnt = new int[8];

while (1) {

    // ... Do something ...

    // Update
    for (int i = 0; i < 8; i++) {
        cnt[i]++;
        if (cnt[i] != cr) break;
        cnt[i] = 0;
    }
}

I'll leave termination of the while loop as an exercise for the reader...

Note: If you find this pattern occurring all over the place in your code, you could be cunning and put the update logic into a helper class. And then your outer loop could become:

for (Counter c = new Counter(8,cr); c.isActive(); c.increment()) {
    ...
}

Answer 2

Just for fun I took your code and ran it as it with timing around the loops.. on average 48 milliseconds. I then took the code and correct the usage of .append and gathered timing.. on average 41 milliseconds. And then I changed Integer to int in the for loops and took out the Integer.toString calls.. giving on average 21 milliseconds.

I am not sure what your timing requirements are but both are "fast".

Original code with timing

public class test
{
  public static void main(String args[])
  {
    new test();
  }

  public test()
  {
    StringBuffer consolus = new StringBuffer();

    Integer cr = 3;
    String y = "\"\r\n\"";

    long start = System.currentTimeMillis();

    for (Integer i = 0; i < cr; i++)
    {
        for (Integer j = 0; j < cr; j++)
        {
            for (Integer k = 0; k < cr; k++)
            {
                for (Integer l = 0; l < cr; l++)
                {
                    for (Integer m = 0; m < cr; m++)
                    {
                        for (Integer n = 0; n < cr; n++)
                        {
                            for (Integer o = 0; o < cr; o++)
                            {
                                for (Integer p = 0; p < cr; p++)
                                {
                                                       consolus.append(i.toString()+j.toString()+k.toString()+l.toString()+m.toString()+n.toString()+o.toString()+p.toString() + y);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    long stop = System.currentTimeMillis();

    System.out.println(stop-start);
  }
}

Update code with timing

public class test
{
  public static void main(String args[])
  {
    new test();
  }

  public test()
  {
    StringBuffer consolus = new StringBuffer();

    Integer cr = 3;
    String y = "\"\r\n\"";

    long start = System.currentTimeMillis();

    for (Integer i = 0; i < cr; i++)
    {
        for (Integer j = 0; j < cr; j++)
        {
            for (Integer k = 0; k < cr; k++)
            {
                for (Integer l = 0; l < cr; l++)
                {
                    for (Integer m = 0; m < cr; m++)
                    {
                        for (Integer n = 0; n < cr; n++)
                        {
                            for (Integer o = 0; o < cr; o++)
                            {
                                for (Integer p = 0; p < cr; p++)
                                {
                                    consolus.append(i.toString());
                    consolus.append(j.toString());
                    consolus.append(k.toString());
                    consolus.append(l.toString());
                    consolus.append(m.toString());
                    consolus.append(n.toString());
                    consolus.append(o.toString());
                    consolus.append(p.toString());
                    consolus.append(y);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    long stop = System.currentTimeMillis();

    System.out.println(stop-start);
  }
}

ReUpdated code with timing

public class test
{
  public static void main(String args[])
  {
    new test();
  }

  public test()
  {
    StringBuffer consolus = new StringBuffer();

    Integer cr = 3;
    String y = "\"\r\n\"";

    long start = System.currentTimeMillis();

    for (int i = 0; i < cr; i++)
    {
        for (int j = 0; j < cr; j++)
        {
            for (int k = 0; k < cr; k++)
            {
                for (int l = 0; l < cr; l++)
                {
                    for (int m = 0; m < cr; m++)
                    {
                        for (int n = 0; n < cr; n++)
                        {
                            for (int o = 0; o < cr; o++)
                            {
                                for (int p = 0; p < cr; p++)
                                {
                                    consolus.append(i);
                    consolus.append(j);
                    consolus.append(k);
                    consolus.append(l);
                    consolus.append(m);
                    consolus.append(n);
                    consolus.append(o);
                    consolus.append(p);
                    consolus.append(y);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    long stop = System.currentTimeMillis();

    System.out.println(stop-start);
  }
}

Answer 3

The only inefficiency I see is this:

consolus.append(i.toString()+j.toString()+k.toString()+l.toString()+m.toString()+n.toString()+o.toString()+p.toString() + y);

should be this

consolus.append(i).append(j).append(k).append(l).append(m).append(n).append(o).append(p).append(y);

Answer 4

The are perhaps some more compact ways of writing it, but you are generating CR^8 numbers, and your inner statement runs CR^8 times. However you re-arrange the loop you still need to add those CR^8 numbers...so will be roughly the same, except as noted elsewhere some call inefficiencies.

Your textView is not updating because you are runnng on the UI thread, the refresh occurs after you leave your callback routine. Callbacks are atomic from the POV of the UI. If you want to see the textView get populated as it happens, you should run your routine on a background thread and post your results to the UI periodically. An AsyncTask would also work for this where you update your TextView in onProgressUpdate()

Answer 5

I would suggest this approach:

public class Solution {
    public static void main(final String args[]) {
        final int upToNumberNonInclusive = 2;
        final int upToLength = 2;
        appendPermutations(upToNumberNonInclusive, upToLength, new Appendable() {
            @Override
            public void append(final CharSequence text) {
                System.out.println(text);
            }
        });
    }

    /**
     * Generates all Permutations from 0..upToNumberNonInclusive with a length of upToLength.<br>
     * Example: upToNumberNonInclusive=2, upToLength=2<br>
     * result: 0, 1, 10, 11 (arguments for append)
     */
    public static void appendPermutations(final int upToNumberNonInclusive, final int upToLength, final Appendable appendable) {
        for (int number = 0; number < upToNumberNonInclusive; number++)
            appendPermutationsHelper(upToNumberNonInclusive, number, upToLength - 1, appendable);
    }

    private static void appendPermutationsHelper(final int numberOfForks, final int currentNumber, final int depth, final Appendable appendable) {
        if (depth == 0) {
            appendable.append(Integer.toString(currentNumber, 10));
            return;
        }
        for (int number = 0; number < numberOfForks; number++)
            appendPermutationsHelper(numberOfForks, currentNumber * 10 + number, depth - 1, appendable);
    }

    public interface Appendable {
        public void append(CharSequence text);
    }
}

The recursion makes more clarity and avoiding StringBuilder calls would create less object actions.

If you need the exact same solution as in the example code, you can add a method to fill it up:

    public class Solution {
        public static void main(final String args[]) {
            final int upToNumberNonInclusive = 2;
            final int upToLength = 2;
            appendPermutations(upToNumberNonInclusive, upToLength, new Appendable() {
                private final static char fillCharacter = '0';
                private static final String endOfLine = "\"\r\n\"";

                @Override
                public void append(final CharSequence text) {
                    System.out.print(fillUpText(text) + endOfLine);
                }

                /** fills up the text up to upToLength with fillCharacter */
                private CharSequence fillUpText(final CharSequence text) {
                    if (text.length() >= upToLength)
                        return text;
                    final char[] arrayChar = new char[upToLength - text.length()];
                    Arrays.fill(arrayChar, fillCharacter);
                    return new String(arrayChar) + text;
                }
            });
        }

        /**
         * Generates all Permutations from 0..upToNumberNonInclusive with a length of upToLength.<br>
         * Example: upToNumberNonInclusive=2, upToLength=2<br>
         * result: 0, 1, 10, 11 (arguments for append)
         */
        public static void appendPermutations(final int upToNumberNonInclusive, final int upToLength, final Appendable appendable) {
            for (int number = 0; number < upToNumberNonInclusive; number++)
                appendPermutationsHelper(upToNumberNonInclusive, number, upToLength - 1, appendable);
        }

        private static void appendPermutationsHelper(final int numberOfForks, final int currentNumber, final int depth, final Appendable appendable) {
            if (depth == 0) {
                appendable.append(Integer.toString(currentNumber, 10));
                return;
            }
            for (int number = 0; number < numberOfForks; number++)
                appendPermutationsHelper(numberOfForks, currentNumber * 10 + number, depth - 1, appendable);
        }

        public interface Appendable {
            public void append(CharSequence text);
        }
    }

Please notice, that the anonymous class is only for educational purpose, not the suggested general solution.