Друзья, подскажите, пожалуйста. Есть квадратная матрица NxN. Вся матрица заполнена значениями от 1 до N в произвольном порядке, разумеется с повторениями (дважды, трижды, или более раз может встретиться любое из значений от 1 до N). Требуется взять по одному значению из каждой строки матрицы так, что бы можно было составить непрерывный ряд значений от 1 до N.
Примеры входных данных:
2 2 2 3
4 3 3 4
1 1 2 2
2 1 2 2
и
1 1 1 1 1
2 2 3 4 5
5 5 5 4 5
1 1 1 5 5
1 1 1 1 5
Я привел матрицу
2 2 2 3
4 3 3 4
1 1 2 2
2 1 2 2
к виду виду
0 1 1 0
0 0 1 1
1 1 0 0
1 1 0 0
где столбец это цифра присутствующая в строке. т.е. 2 2 2 3 это 0 1 1 0 соответственно, если отсортировать строки так, чтобы значения по диагонали были равны 1, то это и есть непрерывный ряд, т.о. если отсортировать строки
1 1 0 0
1 1 0 0
0 1 1 0
0 0 1 1
то видим, что в каждой строке есть цифра, для нашего непрерывного ряда. если перевести в исходную матрицу, то получим
1 1 2 2 - 1
2 1 2 2 - 2
2 2 2 3 - 3
4 3 3 4 - 4
ну и ответ да, составить ряд можно.
берем первую строку с не нулевым элементов, и исключаем из массива первую строку и первый столбец. Получим:
1 0 0
1 1 0
0 1 1
и так далее, когда размерность массива станет 1, проверяем, если [0][0]ый элемент равен 0, пр:
0 1
0 1
, то считаем, что матрица не сходится. Если 1, то сходится.
Я перевел это в код:
private void recur(ArrayList<ArrayList<Integer>> booleanRecursMatrix) {
for (int column = 0; column < booleanRecursMatrix.size(); column++) {
for (int row = 0; row < booleanRecursMatrix.size(); row++) {
if (booleanRecursMatrix.get(row).get(column) == 1) {
ArrayList<ArrayList<Integer>> downArray = new ArrayList<>();
downArray.addAll(booleanRecursMatrix);
System.out.println("\n" + downArray);
downArray.remove(row);
for (int irow = 0; irow < downArray.size(); irow++) {
downArray.get(irow).remove(column);
}
System.out.println(downArray);
if (downArray.size() == 1 && downArray.get(0).get(0) == 1) {
System.out.println("Матрица сходится, кол-во иттераций = " + this.count);
//break label1;
} else if(downArray.size() == 1 && downArray.get(0).get(0) == 0) {
System.out.println("Матрица не сходится");
break;
} else {
System.out.println("");
this.count += 1;
recur(downArray);
}
}
}
}
Не могу понять, почему цикл не перебирает все варианты, а прекращается на первом.