12
\$\begingroup\$

I wrote a simple program using int[] and ArrayList<Integer> which aims to get a random permutation output between 1 to 10, where each number will not be repeated in each line of output (each line of output will have number 1 until 10 in a different order). Both classes work nicely with the desire output. Is there any other possible way to shorten my code?

Random arrays using brute force:

3 5 2 9 7 8 10 1 4 6
4 10 5 2 3 9 6 1 7 8
7 9 1 10 3 8 5 4 2 6
5 3 8 9 10 2 6 7 1 4
8 5 9 7 10 6 4 2 1 3
4 10 2 9 8 6 3 7 5 1
8 9 10 2 5 4 6 7 3 1
7 2 4 9 5 10 6 8 1 3
9 2 8 1 10 7 6 4 5 3
8 1 10 3 9 7 4 2 5 6

This is my BrutePermutationGenerator file:

import java.util.Random;

public class BrutePermutationGenerator
{    

  public int[] getRandomPermutation()
  {
  Random rand = new Random();
  int[] array = new int[10];

  int r = 0;
  int count = 0;
  boolean fill;

  int low = 1;
  int high = 10;
  int range = high - low + 1;

  do
  {
    fill = true;
    r = rand.nextInt(10) + 1;

     for (int i = 0; i < array.length; i++)//loop for random number between 1 to 10
     {          
        if (array[i] == r)
        {
           fill = false;
        }
     }

     if (fill == true)
     {
        array[count] = r;
        count++;
     }
   }
   while (count < 10);
      for (int i = 0; i < array.length; i++)//loop for element in array
      {
         System.out.print(array[i] + " ");
      } 
   return array;
  } 

public void nextPermutation()
 {
   for (int i = 0; i < 10; i++) //loop for permutation 10 times
   {
      getRandomPermutation(); 
      System.out.println();
   } 
  }
}

This is my SmartPermutationGenerator file:

import java.util.ArrayList;
import java.util.Random; 

public class SmartPermutationGenerator 
{
   private int size;
   private Random rand = new Random();

   public SmartPermutationGenerator() 
   {
      this.size = 10;
   }

   public ArrayList<Integer> getRandomPermutation() 
   {
      ArrayList<Integer> unused = new ArrayList<>();

      for (int i = 0; i < size; i++) // loop for element in array
      {
         unused.add(i + 1);
      }

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

      for (int k = 0; k < size; k++)  //loop for random number between 1 to 10
     {
         int pos = rand.nextInt(unused.size());
         perm.add(unused.get(pos));
         unused.remove(pos);
     }

    return perm;
    }

public void nextPermutation()
{
   for(int i = 0; i < size; i++) //loop for permutation 10 times
   {
       for(Integer item : getRandomPermutation()) 
       {
           System.out.print(item + " ");
       }
    System.out.println();
   }
 }
}

This is my PermutationGeneratorViewer file:

public class PermutationGeneratorViewer
{
   public static void main(String[] args) 
   {
      BrutePermutationGenerator brute = new BrutePermutationGenerator();
      SmartPermutationGenerator smart = new SmartPermutationGenerator();

      System.out.println("\n" + "Random arrays using Brute Force: ");
      brute.nextPermutation();

      System.out.println("\n" + "Random arrays using Smart Force: ");
      smart.nextPermutation();
   }
} 
\$\endgroup\$
5
\$\begingroup\$

When doing a comparison like this, you should really consider creating an interface, e.g. IPermutable, so that you can maintain consistent method interfaces. You can then have your two permutation types implement the interface and use a templated generator class.

    int r = 0;
    boolean fill;

Both of these are only used in the do/while loop, starting with

        fill = true;
        r = rand.nextInt(10) + 1;

So change those to

        boolean isFound = true;
        int r = random.nextInt(10) + 1;

That limits the scope to just the loop.

Note that I also changed the name from fill to isFound. To me, a variable that starts with "is" is a boolean. This makes statements involving them read nicely:

isFound = true;
if ( isFound ) 

You use the number 10 in multiple places. You should define one or more constants to replace these uses.

private final int NUMBER_COUNT;

If you do it that way, you can pass in the number in the constructor and set it for each object.

You don't need a do/while in this case. A regular while would do.

If your permutations were in classes, you could give the permutation its own toString function. Then you could write code that looked like

IntArrayPermutation permutation = new IntArrayPermutation(10);
System.out.println(permutation.getNext());

And if the getNext() function ends with return this;, everything will just work. This might have been what your original code tried to do, but the toString of an int[] did not produce the desired results.

private int size;
private Random rand = new Random();

Both of these can be final:

private final int size;
private final Random random = new Random();

I'd also write out random, as it reads more easily.

public ArrayList<Integer> getRandomPermutation() 
{
    ArrayList<Integer> unused = new ArrayList<Integer>();

It's more common to use just List on the left:

public List<Integer> getRandomPermutation() 
{
    List<Integer> availableNumbers = new ArrayList<Integer>();

ArrayList is an implementation detail and your caller doesn't need to know it.

I also changed unused to availableNumbers. I think it better represents what the List holds.

I'm not sure that I'd call these brute force versus smart force. A brute force algorithm is one that tries every possibility once. A brute force solution would be to generate all \$10!\$ solutions and then randomly pick one. Your algorithm can actually iterate an arbitrary number of times (in fact, it's not guaranteed to finish). I might call it naive rather than brute force.

\$\endgroup\$
  • \$\begingroup\$ Thanks brythan for answer review, very well explained on consistent method interfaces, toString function and the rest. \$\endgroup\$ – niese Nov 16 '14 at 2:27
10
\$\begingroup\$

Use for-each

Use for-each idiom to loop over an array when possible, and you can drop this comment:

//loop for element in array
for (int i = 0; i < array.length; i++) {
    System.out.print(array[i] + " ");
}

Like this, and without the pointless comment:

for (int item : array) {
    System.out.print(item + " ");
}

Use a different list implementation for unused

In SmartPermutationGenerator, you're using an ArrayList for the unused numbers, and randomly remove items from it. An ArrayList is backed by an array, and removing items from arrays is an expensive operation: elements after the removed element must be moved to fill the gap. You can improve that point by using a LinkedList instead, where removal of elements is cheap.

public List<Integer> getRandomPermutation() {
    List<Integer> unused = new LinkedList<>();
    for (int i = 0; i < size; i++) {
        unused.add(i + 1);
    }

    List<Integer> permutation = new ArrayList<>();
    for (int k = 0; k < size; k++) {
        int pos = random.nextInt(unused.size());
        permutation.add(unused.get(pos));
        unused.remove(pos);
    }

    return permutation;
}

Use boolean expressions directly without ==

You don't need to write == true when evaluating boolean expressions like this:

if (fill == true) {

This is exactly the same but shorter, simpler, intuitive:

if (fill) {

Remove unused code

These variables are completely unused, remove them:

  int low = 1;
  int high = 10;
  int range = high - low + 1;

Printing arrays

In both implementations, you're using a for loop to print arrays. There's are easier ways.

The toString method of List implementations gives a nice representation, so you can print them directly:

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
System.out.println(list);
// prints: [1, 2, 3, 4, 5]

To print arrays in the same format, you can use Arrays.toString:

int[] arr = {1, 2, 3, 4, 5};
System.out.println(Arrays.toString(arr));
// prints: [1, 2, 3, 4, 5]

Formatting

Your code doesn't follow the common formatting used by auto-formatting of editors like Eclipse, IntelliJ, NetBeans. Instead of this:

  do
  {
    fill = true;
    r = rand.nextInt(10) + 1;

     for (int i = 0; i < array.length; i++)//loop for random number between 1 to 10
     {          
        if (array[i] == r)
        {
           fill = false;
        }
     }

Following the same style as recommended by these tools, your code would look like this:

do {
    fill = true;
    r = rand.nextInt(10) + 1;

    for (int item : array) {
        if (item == r) {
            fill = false;
        }
    }
\$\endgroup\$
  • \$\begingroup\$ I disagree on that last point. The time of 80x25 text screens is long gone, so there's no need to compress code vertically. In any case the closing braces wouldn't get whole lines all for themselves in that case. IMHO niese's formatting is perfectly alright, there is nothing at all wrong with it. Java's standard formatting is just as poorly chosen as that of Visual Basic and C#, which makes even the most beautiful algorithms look ugly. Maybe that its why in Java even the VM and the core libraries are so full of bugs. I.e. who can respect ugly-looking code and bear to look at it long and hard? \$\endgroup\$ – DarthGizka Nov 15 '14 at 17:07
  • 2
    \$\begingroup\$ Egyptian braces are a "holy war" issue; some people would swear that they're great, others swear that they're terrible. I think the last point is personal preference. +1 for the rest, though. \$\endgroup\$ – apnorton Nov 15 '14 at 19:31
  • 1
    \$\begingroup\$ Let's not argue about that. The indentation was off though. \$\endgroup\$ – Anubian Noob Nov 15 '14 at 19:35
  • \$\begingroup\$ thanks janos for review, will implement most of your comment in my code but exception for my formatting, as now i'm using notepad++ editor to enforce myself to type each characters for each files of code that i created to make myself familiar with java syntax..and that why my indentation might look a bit messy. \$\endgroup\$ – niese Nov 16 '14 at 2:43
6
\$\begingroup\$

Perhaps you can just use Collections.shuffle(list); this way:

// unmodifiable list, add(..) will throw an exception, but shuffle works
List<Integer> permutation = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); 
// do it modifiable
//List<Integer> permutation = new ArrayList(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)); 

for (int i = 0; i < 10; i++) {
    Collections.shuffle(permutation);
    System.out.println(permutation);
}

Output:

[10, 4, 1, 5, 2, 6, 9, 8, 3, 7]
[10, 5, 4, 1, 6, 9, 3, 7, 8, 2]
[4, 6, 3, 5, 7, 9, 10, 8, 1, 2]
[2, 1, 8, 5, 6, 3, 9, 10, 4, 7]
[1, 7, 6, 8, 2, 3, 9, 5, 4, 10]
[7, 1, 9, 10, 6, 8, 2, 4, 5, 3]
[3, 7, 1, 8, 9, 2, 6, 10, 4, 5]
[10, 5, 6, 2, 7, 1, 3, 9, 8, 4]
[2, 5, 4, 6, 7, 8, 1, 9, 10, 3]
[6, 10, 3, 7, 2, 9, 5, 4, 8, 1]
\$\endgroup\$
  • \$\begingroup\$ new ArrayList<Integer>() is code smell \$\endgroup\$ – mhmxs Nov 15 '14 at 21:21
  • \$\begingroup\$ @mhmxs hmm, i usually do it since Arrays.asList returns an unmodifiable list \$\endgroup\$ – dieter Nov 15 '14 at 21:42
  • \$\begingroup\$ nice, will consider this approach..i read about this before just haven't try it yet. \$\endgroup\$ – niese Nov 16 '14 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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