Cleaner way to do this?

[destin]

I was kind of bored today.. so i was searching for a problem to do. I found this: http://www.devx.com/DevX/HTML/17955

So i did it.. everything works.. just i have a huge series of nested for loops (it has 4 nested for loops because the problem only calls for an array with a length of 5, but i want to clean this up so i can have any length). anyone know what i can do?

it might be really obvious but i can't think of anything.

/**
 *  FewestFactors.java
 *  FewestFactors
 *
 *  Created by destin on 12/27/05.
 */

import java.util.*;

public class FewestFactors {
    public static void main(String args[]) {
        int[] i = { 1, 2, 3, 4 };
        System.out.println(number(i));
    }
	
    static public int number(int[] digits) {
        /** 
         * used to store possible ways (Note: this will always have a size of 
         * (digits.length)!) 
         */
        ArrayList<Integer> ways = new ArrayList<Integer>();
        /** 
         * used to remember which index in the ArrayList 
         * has the least amount of factors
         */
        int leastFactorsNum = 0;
        /** 
         * start with a number higher than any possible factor 
         * (if digit.length is 5, this will be 50000) 
         */
        int leastFactors = (int) (Math.pow(10, digits.length) / 2);

        /** 
         * extremely long (and would be ongoing) nested for loops to 
         * determine amount of possibilities
         *
         * there has to be a better way to do this....
         */
        for (int a = 0; a < digits.length; a++) {
            if (digits.length == 1) {
                ways.add(digits[a]);
            } else {
                for (int b = 0; b < digits.length; b++) {
                    if (digits.length == 2) {
                        if (a != b) {
                            ways.add((10 * digits[a]) + digits[b]);
                        }
                    } else {
                        for (int c = 0; c < digits.length; c++) {
                            if (digits.length == 3) {
                                if ((a != b) && (b != c) && (a != c)) {
                                    ways.add((100 * digits[a]) + (10 * digits[b]) + digits[c]);
                                }
                            } else {
                                for (int d = 0; d < digits.length; d++ ) {
                                    if (digits.length == 4) {
                                        if ((a != b) && (a != c) && (a != d) &&
                                                (b != c) && (b != d) && (c != d)) {
                                            ways.add((1000 * digits[a]) + (100 * digits[b]) + (10 * digits[c]) + digits[d]);
                                        }
                                    } else {
                                        for (int e = 0; e < digits.length; e++) {
                                            if (digits.length == 5) {
                                                if ((a != b) && (a != c) && (a != d) && (a != e) &&
                                                        (b != c) && (b != d) && (b != e) && 
                                                        (c != d) && (c != e) && (d != e)) {
                                                    ways.add((10000 * digits[a]) + (1000 * digits[b]) + (100 * digits[c]) +
                                                                  (10 * digits[d]) + digits[e]);											
                                                }
                                            } else {
                                                return 0;
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
		
        /** print out all possible ways */
        for (int i = 0; i < ways.size(); i++) {
            System.out.println("ways[" + i + "]: " + ways.get(i));
        }
		
        /** find all factors of every possibility */
        for (int i = 0; i < ways.size(); i++) {
            int count = 0;
            for (int j = 2; j <= ways.get(i) / 2; j++) {
                if (ways.get( i ) % j == 0) {
                    count++;
                }
            }
			
            /** 
             * if the this number's amount of factors is less than leastFactors 
             * or if they are equal but we found a smaller number
             */
            if ((count < leastFactors) || 
                    ((ways.get(i) < ways.get(leastFactorsNum)) && (count == leastFactors))) {
                leastFactors = count;
                leastFactorsNum = i;
            }
        }
        return (int) ways.get( leastFactorsNum );
    }
}

[teknomage1]

You can replace your nested loops with a (your favorite type!) recursive function. Basically the trigger for recursion would be the if statement that is at the end of each loop.

Aside from that though you could refactor this in a better fashion by
writing a function to handle permuting the array, that is a function which returns all possible combinations of the digits in an array of arbitrary size (algorithms for which are googleable). For all I know, the java array class might already have a method for this.

Then team up array.permute with a function to return a list of factors for a given integer. Now all you have to do for leastFactors() is pass the output from array.permute() to int.factor() and choose the one that returns the shortest list of factors.

[destin]

Could you point me in the right direction for the recursive function (i'm not too good with these... yet )

[teknomage1]

Here's a recursive permute_array function. (In psuedo code cause I don't generally do java)

int permute (int[] input_array, int[] output_array, int input_array_length) {
     //input array should be pass by value
     //output array should be pass by reference
     if (input_array_length == 0) {
	 //Add the current permutation of the vector to the output array
	 output_array.push( vector_to_int( input_array ));
     }
     else {
	 for( i = 0; i < input_array_length; i++) {
	     //run permute with two elements swapped
	     int tmp1 = input_array[i];
	     int tmp2 = input_array[input_array_length - 1];
	     input_array[i] = tmp2;
	     input_array[input_array_length - 1] = tmp1;
	     permute( input_array, output_array, input_array_length - 1 );
	     //Undo swap for next iteration.
	     tmp1 = input_array[i];
	     tmp2 = input_array[input_array_length - 1];
	     input_array[i] = tmp2;
	     input_array[input_array_length - 1] = tmp1; 
	 }
     }
}

int vector_to_int (int[] vec) {
    //turns [1,2,3] into 321
    int out = 0;
    for (i = 0; i < vec.length; i++) {
	out += vec[i] * pow(10, i); //don't know how java does exponents but what I mean to say is 10 to power of i
    }
    return out;
}

[destin]

Hmm... i don't really understand what your trying to say here:

output_array.push( vector_to_int( input_array ));

Also, i don't see how this helps .. although i might just be blind.

(btw, it would be Math.pow(10, i); )

[teknomage1]

This function has to return multiple values, multiple times, and the easiest way to accomplish that is to use a side effect that populates an array. You could probably replace the parameter output_array with a member variable the way you use ways.add above.

Like I said, I don't really do java, my code sample is just meant to look java-esque so you can understand it enough to translate it to real java. I guess sometimes I don't guess right on the syntax though. How do you add an element to an array?

[Belisarius]

Sorry, I wasn't really sure what you were trying to do, so I couldn't help. If you need to return two different types, say a boolean and an int, then either wrapping them in an object or setting some parent variables would be the best way.

[teknomage1]

Well they'll all be ints, It's just the function returns multiple times so it has to take care of it's own collecting.