Перебор всевозможных вариантов

[LEXAlForpostl]

Здравствуйте.
Есть квадратная таблица NxN.
Шаги работы алгоритма:
1. Находим максимальный элемент в таблице с индексами i,j.
2. Далее удаляем столбцы i и j.
3. Ищем максимальный элемент в строках i и j.
4. Повторяем шаги 2 и 3, пока не удалятся все столбцы.

Однако, может быть такой случай, когда будет несколько одинаковых максимальных значений, причем на нескольких шагах. И при таком раскладе результат может измениться. Подскажите, пожалуйста, как можно применить алгоритм, описанный выше ко всевозможным вариантам.
Пока даже не определился в каком виде хранить данные, которые бы отражали несколько вариантов развития алгоритма.

 

[dandandan]

Первое, что приходит в голову - хранить данные в массиве. Делать обход

for ($a = 1; $a <= i; $i++) {
  for ($b = 1; $b <= $j; $j++) {
  echo $array[$a][$b]i; // тут сравниваем значение массива с максимальным значением, полученным на предыдущем шаге
  }
}

Обход делать рекурсивно, уменьшая количество строк и столбцов.

Поиск максимального значения лучше делать методом "пузырька"
Для просмотра ссылки Войди или Зарегистрируйся

 

[PapaJoe]

первый вариант: сначала найти максимальное значение(попутно увеличивая счетчик элементов, равных максимальному значению), а потом пройтись еще раз и удалить элементы, равные этому значению
второй вариант: во время поиска максимального значения создавать массив со значениями i и j, элементы в которых равны максимальному. Если во время поиска находится элемент больше, чем максимальный, массив очищается и заполняется заново. В конце поиска пройтись по полученному массиву и удалить из первоначального строки и столбцы, записанные в новом массиве

 

[DrakonHaSh]

какое-то, лично для меня, не внятное описание алгоритма, и пункт 1 и 3 вроде как одно и то же

И при таком раскладе результат может измениться

а результат это что ? по вашу алгоритму результат - это удаление всех столбцов. может вы имеете в виду последовательность удаления (процесс) ?

 

[LEXAlForpostl]

В первом пункте мы ищем по всей таблице.
В третьем пункте только в 2х строках.

а результат это что

Спасибо, забыл указать.
Результат это последовательность номеров удалённых столбцов.

Поиск максимального значения лучше делать методом "пузырька"

Здесь Вы погорячились.
Во-первых, Ваш вариант пузырька можно оптимизировать, и кстати, в нём много ошибок. Вы то с i,j, то с a,b работаете.
for ($a = 0,$c = count($array[0]); $a < $c; $a++) {
for ($b = $a+1; $b <= $j; $b++) {

Во-вторых, проблема не в метода поиска максимального значения.

Самое главное: Если на каком-то этапе у нас будет возможность выбрать путь развития А либо В. Далее если мы выберем ячейку А, то может быть ещё одна спорная ситуация, где нам надо будет обработать одну из одинаковых ячеек C,D,E. Прошу заметить, что если мы пойдем черезе ячейку В, то НЕ ОБЯЗАТЕЛЬНО, что будет спорный момент с ячейками C,D,E.

 

[dandandan]

Вам алгоритм надо или исходный код? Если код, то только Вы знаете как должен выглядеть конечный код.
По алгоритму, еще раз повторю: Перебираем массив. Находим максимум. Каким-то образом (только Вы знаете как: самый первый, самый последний, рандомно, по дате своего рождения и т.д.) удаляем одну строку/столбец. Выполняем рекурсивно еще проверку...

Если есть конкретный вопрос - спрашивайте. Кто-нибудь ответит.

Если исходный вопрос этот?

Подскажите, пожалуйста, как можно применить алгоритм, описанный выше ко всевозможным вариантам.

То неизвестно, что на выходе желаете получить. Вообще нужно будет создавать копию массива и по нему делать повторный заход поиска данных, потом еще копию и т.д... Дальше анализируем полученные данные.

 

[LEXAlForpostl]

Алгоритм, который находит самое ближайшее максимальное в массиве - уже реализован.
Однако, интересует идея, которая позволила бы выполнить алгоритм для всевозможных вариантов. В моей версии берется только 1 максимальное. Однако, если их 2,3,5... То результаты я теряю.
Приведу пример:
-1 5 6
5 -1 9
6 9 -1
Диагональ не участвует. Верхний треугольник равен нижнему.
В данном случае, очевидно, что начинаем с 9.
-1 9 6
9 -1 9
6 9 -1
Однако, в данном можно начать либо с одной либо со второй 9.
Мой алгоритм начнет с [0;1] и всё успешно выполнит.
Однако, надо ещё с [1;2] поработать, этого он не сделает.

Отсюда и вопрос, как организовать работу так, чтобы перебирались всевозможные варианты.

Вам алгоритм надо или исходный код

Нужен алгоритм, но за исходный код - буду безмерно благодарен.

 

[dino]

а если растаскать матрицу в одномерный массив, а затем обрабатывать обычными функциями типа array_unique(), asort(), arsort() и т.д ?

 

[LEXAlForpostl]

Весь треугольник можно представить в одномерном массиве. И по формуле получать доступ, но для чего?
Не совсем понимаю, для чего сортировка, поиск уникального.

 

[dino]

Эти функции я привел только для примера, а подразумевалось не поиск уникального, а преобразование массива содержащего одинаковые значения в массив с уникальными значениями (лишнее убирается), сортировка, для того чтоб найти максимальное/минимальное значение, ну и так далее....
В общем измываться над массивом можно как угодно и искать в нем что угодно используя весь набор функций обработки массивов...
P.S. А если вам все таки важно ковырять именно матрицу, то попробуйте не удалять данные, а перекладывать их с такими же ключами в новую матрицу, и когда нашли искомое значение в одной матрице - переходим к разбору новой матрицы и т.д. пока не найдете столько элементов, сколько нужно...