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

Question

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

Рейтинг: 0Ответов: 2Опубликовано: 29.09.2014

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

Пример:

на входе:

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])?

java массивы

Источник: Stack Overflow на русском

Answer 1

▲ 1

Попробуйте вот так.

bool Next(int[] indices) {
    int currPos = 0;
    while (currPos < n) {
        indices[currPos]++;
        if (indices[currPos] < m)
            return true;
        indices[currPos] = 0;
        currPos++;
    }
    return false;
}

int[] indices = new int[n];
// initilialized with 0

do {
    outputSum(indices);
} while (Next(indices));

void outputSum(int[] indices) {
    for (int line = 0; line < n; line++) {
        if (line != 0) System.out.write(" + ");
        int col = indices[line];
        System.out.write(matrix[col][line]);
    }
    System.out.writeln();
}

Answer 2

▲ 1

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

    /**
 * 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);
    }
}

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

Ответы