Перебор всех значений двумерного массива

[photozaz]

Добрый день. Есть задача написать процедуру на вход которой будет подаваться двумерный массив рандомной размерности. Требуется вывести все возможные суммы элементов с условием что за одну итерацию из одномерного массива(строки) берется только одно значение. Сам алгоритм выглядит следующим образом.

Пример:

на входе:
123
456
789

на выходе:
1+4+7 1+4+8 1+4+9
1+5+7 1+5+8 1+5+9
1+6+7 1+6+8 1+6+9

2+4+7 2+4+8 2+4+9
2+5+7 2+5+8 2+5+9
2+6+7 2+6+8 2+6+9

3+4+7 3+4+8 3+4+9
3+5+7 3+5+8 3+5+9
3+6+7 3+6+8 3+6+9

Вопрос: как реализовать данный алгоритм для массива nxn(array [n][n])?

[Bugrimov]

А наработки имеются?

[BleStaR]

Держи. Компановку вывода под конечный результат реализуете самостоятельно.

package programmersforum;

public class Enumeration {
    /**
     * Выводит все возможные суммы элементов с условием, что за одну итерацию из
     * одномерного массива(строки) берется только одно значение.
     * @param in Исходный двумерный массив размерности nxn
     */
    public static final void showAllAmount( final int [][] in ) {
        if ( in == null || in.length == 0 || (in.length != in[0].length) ) {
            throw new IllegalArgumentException("Не соответствие условиям задачи");
        }
        final int [] indexes = new int [in.length];
        final int maxRowIndex = indexes.length - 1;
        for(int i = 0; i < maxRowIndex; i++) {
            indexes[i] = 0;
        }
        indexes[maxRowIndex] = -1;
        
        while ( next(indexes, maxRowIndex) ) {
            for(int i = 0; i < indexes.length; i++) {
                System.out.print(in[i][indexes[i]]);
                if ( i < maxRowIndex ) {
                    System.out.print("+");
                } else {
                    System.out.print(" ");
                }
            }
        }
    }
    /**
     * Переводит массив индексов к следующему значению/шагу.
     * @param indexes Массив содержащий текущие положение обрабатываемых идндексов.
     * @param pos Стартовая позиция для увеличения индекса.
     * @return Возвращает true, если увеличение прошло успешно, false - если 
     * увеличение индекса более не возможно (все возможные значения были 
     * использованы).
     */
    private static boolean next(final int [] indexes, int pos) {
        if ( indexes[pos] == indexes.length - 1 ) {
            if ( pos == 0 ) {
                return false;
            }
            indexes[pos] = 0;
            return next(indexes, pos - 1);
        }
        indexes[pos]++;
        return true;
    }
    
    public static void main(String [] args) {
        final int [][] in = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        Enumeration.showAllAmount(in);
    }
}

[photozaz]

реализовал следующим образом

         /**
	 * Find highest sums in jagged array
	 * @param lists is a jagged array to be processed
	 * @param n is a number of highest sums to be found
	 * @return
	 */
	public List<Integer> findSums(int[][] lists, int n) {
	 
		ArrayList<Integer> allSums = new ArrayList<Integer>();
				
		for (int i=0; (i<lists[0].length)&(i<n); i++)	// get the first list of elements of lists[][]; cut list to n size
			allSums.add(lists[0][i]);	
		
		if (lists.length>1) {
			
			 for (int r=1; r<lists.length; r++) {
				 ArrayList<Integer> sums = new ArrayList<Integer>();
				 for(int c=0; (c<lists[r].length)&(c<n); c++) {
					 sumElements(allSums,lists[r][c], sums);
				 }
				 
				 sums = ArrayOperations.arraySortDescending(sums);
				 allSums.clear();
				 allSums.addAll(sums);	// store sorted sums into allSums list
				 sums.clear();		// clear sums list				
			 }
			 
		 } else {
			 	if (allSums.size()>n)
			 		allSums.subList(n, allSums.size()).clear();
		 }
	 
		return allSums;
	}
	
	/**
	 * Count sums for every element in row with elements of previous row
	 * @param array
	 * @param nlv is the next list value
	 * @param sums is a temporary storage for sums between two lists 
	 */
	private void sumElements(ArrayList<Integer> list, int nlv, ArrayList<Integer> sums) {
		for (int i=0; i<list.size(); i++) {
			sums.add(list.get(i) + nlv);
		}
	}

[BleStaR]

проводил какие нить тесты на скорость?