похожие строки матрицы

[LenaFree]

Привет всем!!

Обращаюсь к вам за помощью: нужно решить прогу :) :

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

Заранее очень благодарна! :)

Есть пога, кое-что удалось сделать :( , но результат так и не устраивает :)

[Форматцевт]

Задание поставлено не корректно, оно двусмысленно.

[Тролль]

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

Переведем на человеческий язык.

Заданы множества, представленные строками матрицы. Сколько есть разных множеств?

а) сортируем элементы каждой строки (любая простейшая сортировка, например, пузырьковая); теперь строки с совпадающими множествами элементов будут одинаковыми

б) находим количество несовпадающих строк (сравнение каждой строки, кроме последней, со всеми последующими)

Итак, поехали.

const s=4; c=4; const a:array[1..s,1..c] of integer=((3,4,2,1),(1,2,1,4),(2,4,3,1),(4,3,2,1));{тестовый массив}var   i,j,k,t:integer; b:boolean;beginfor i:=1 to s do for j:=1 to c do for k:=1 to c-j do if a[i,k]>a[i,k+1] then begin t:=a[i,k]; a[i,k]:=a[i,k+1]; a[i,k+1]:=t; end;{закончили сортировку элементов в строках;теперь строки с одинаковым набором элементов выглядят одинаково}for i:=1 to s do begin for j:=1 to c do Write(a[i,j]); WriteLn end;{для демонстрации результатов первого этапа распечатали полученную матрицу; в варианте на сдачу эту распечатку убрать}t:=1; {t - счетчик строк, разных по множеству элементов; последняя строка не имеет следующих за ней похожих в любом случае;ее мы проверять не будем, а учли ее сразу; теперь займемся поиском сходных строк}for i:=1 to s-1 do {для каждой строки, кроме последней}begin for k:=i+1 to s do {перебираем все последующие строки}	begin 	b:=true; {поставили признак совпадения строк на true; как только найдемнесовпадающие элементы, поставим признак в false и прекратим дальнейший перебор, так как уже ясно,что строки различаются}	for j:=1 to c do if a[i,j]<>a[k,j] then		begin 		b:=false; break 		end;	if b then break {если найдена похожая строка, проверять дальнейшие строки нет смысла}	end;{вышли из сравнения последующих строк с текущей строкой; b - признак наличия совпадения}if not b then t:=t+1;{за текущей строкой похожих на нее строк не найдено; она - последний представитель строк с таким содержанием; увеличим счетчик}end;WriteLn(t);ReadLn;end. 

[meteorx]

У меня подобное задание, проблема в том что такой метод для матрицы 100Х100 не годится...

Из примера:

1) 1,3,1,4,3,1 = {1,3,4}

2) 1,4,0,3,2,2 = {0,1,2,3,4}

3) 3,4,1,2,4,2 = {1,2,3,4}

4) 3,1,2,4,3,3 = {1,2,3,4}

5) 3,0,3,2,1,4 = {0,1,2,3,4}

6) 0,2,1,3,4,4 = {0,1,2,3,4}

Похожими тут будут 2,5,6 и 3,4 строки, т.е. количество похожих строк тут будет 5...

(Если можно алгоритм на псевдокоде или на С++)

[Тролль]

meteorx:

Размер матрицы значения не имеет. Ну разве что матрица окажется больше допустимого размера массива в языке программирования, такую матрицу в массив и не ввести, тогда придется работать с файлами...

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

Дальше каждую строку проверяем на совпадение со всеми остальными. Если совпадение нашлось, проверку прекращаем и добавляем единицу в счетчик числа совпадений. Нет - так нет, переходим к следующей строке. После прохождения всех строк работа закончена.

Это не слишком оптимальный метод, но при матрице 100Х100 тут компьютеру и делать почти нечего. Все же у нас компьютер, а не арифмометр, не надо этого недооценивать ;)

Вот при матрице 10000Х100 будет смысл использовать более экономичный, чем пузырьковая, метод сортировки, и более экономичный метод сравнений, например, присваивая какой-то признак строкам, которые при какой-то проверке совпали, чтобы в дальнейшем не проверять такие строки полной проверкой, или сразу исключая такие строки из дальнейших проверок. Или, еще более экономичный (и сложный) метод подсчета повторяющихся строк - сортируем все строки (то есть упорядочиваем их положение в матрице), благо функцию сравнения строк написать несложно, а там уже посчитать число совпадающих строк тоже не представит большого труда, все совпадающие строки будут рядом. Но это только если нас волнует эффективность.

P.S. Вообще в Паскале тут удобно использовать встроенные средства работы с множествами, поскольку твои строки сравниваются как множества, да и в C++ есть классы для работы с множествами, но допустимый диапазон элементов множеств зависит от реализации языка, так что без дополнительной информации о задаче и среде программирования проще использовать более обычные средства языка. Да и "вылизывать" учебную или разовую задачу, видимо, ни к чему.

Вот как программа, решающая твой тестовый пример с помощью множеств, будет выглядеть на Pascal:

const s=6; a:array[1..s]of set of 0..255=([1,3,1,4,3,1],[1,4,0,3,2,2],[3,4,1,2,4,2],[3,1,2,4,3,3],[3,0,3,2,1,4],[0,2,1,3,4,4]);var i,j,k:integer;begin k:=0; for i:=1 to s do for j:=1 to s do if (i<>j) and (a[i]=a[j]) then begin k:=k+1;break end;WriteLn(k); ReadLnend. 

Кстати, пришло в голову, что задание у LenaFree действительно можно было бы понимать и в смысле этой задачи, но разъяснение о том, что считается совпадением множеств в той задаче ("не обязательно в том же порядке") вроде бы говорит о том, что не учитывается только порядок следования чисел в строке, а общее количество их в строке должно учитываться. В противном случае надо было бы решение немного подкорректировать (удалить из каждой строки повторяющиеся элементы) или решать, как тут, с помощью множеств.

Изменено 21 апреля, 2007 пользователем Тролль

[meteorx]

Здесь на мой взгляд сравнивать нада строки на совпадение всех элементов 1 строки с всем элементами 2 строки...

Так что твой алгоритм считает только количество совпадений. Но он не говорит являются ли строки похожими...

Конечно можено же сортировать и убрать повторяющиеся элементы... только тогда даже для матрицы 50Х50 будет тормозить.

На мой взгляд, я бы написал бы процедуру, которая бы сравнивала 2 строки

Пишу на C#

public bool str(int[] a,int[] b, int L) // a & b -сравниваемые массивы, L - длина массивов.{int t=0;for (int i=0;i<L;i++)for (int j=0;j<L;j++)   if (a[i]==b[j]) { t++; break;} // Ищем количество совпадений или присутствия элементов одного массива в другом.if (t==L-1) return true;else return break;}

[Тролль]

meteorx:

Здесь на мой взгляд сравнивать нада строки на совпадение всех элементов 1 строки с всем элементами 2 строки...

Так что твой алгоритм считает только количество совпадений. Но он не говорит являются ли строки похожими...

Конечно можено же сортировать и убрать повторяющиеся элементы... только тогда даже для матрицы 50Х50 будет тормозить.

На мой взгляд, ни то, ни другое, ни третье...

1. Написанная тобой функция считает, сколько элементов первой строки имеют совпадающие элементы во второй строке, и почему-то решает, что если совпадений нет ровно для одного элемента первой строки, то строки "похожи". Никакой связи с твоим определением "похожих" строк я тут не вижу. Например, строки 1,2 и 2,2 эта функция посчитает "похожими". Хуже того, строки 2,2 и 1,2 при этом "непохожи". В общем, все равны, но строка 1,2 равнее . К тому же при использовании этой функции алгоритм будет намного медленнее, чем описанный мной, даже без оптимизации. Разбирать, почему, не буду, нет смысла для неработающего алгоритма.

2. У меня алгоритм считает количество "похожих" по твоему определению строк, а не просто количество совпадений. Каждая строка проверяется на то, похожа ли она на хоть какую-нибудь из строк матрицы. Если да, то количество "похожих строк" увеличивается на 1. Каждая строка может быть засчитана только один раз. Но это не мешает другим строкам сравнивать себя с ней. Так что из трех, например, похожих строк для каждой из них будет найдено совпадение в пределах матрицы и счетчик числа похожих строк увеличится на три. И построенная по этому алгоритму программа с использованием для сравнения строк встроенного в Pascal стандартного типа множеств работает правильно и выдает на твоем примере число 5, как и должно быть.

3. В принципе при выборе оптимальных, более сложных алгоритмов твоя задача требует, грубо говоря, времени выполнения, пропорционального квадрату размерности матрицы. По описанному мной алгоритму время будет, опять же по грубой оценке, пропорционально кубу. По твоему алгоритму, если бы он работал - четвертой степени. Но зачем для такой маленькой матрицы, как 100х100, гнаться за быстродействием, не вижу.

Для ликвидации твоих сомнений по поводу "торможения" на матрице 50х50, я для примера замерил время работы программы, приведенной выше, которая решает похожую на твою задачу [b[LenaFree[/b], изменив в ней только размер матрицы. При использовании Borland Pascal на матрице 100х100 я вообще не смог толком замерить время ее решения, таймер материнской платы слишком груб. На матрице 200х200, заполненной случайными числами, получение решения с процессором 1800+ (медленнее не было) заняло 0,16 c.

[Тролль]

meteorx:

Вот программа для решения твоего тестового примера на C без использования множеств (под рукой был Turbo C):

#include <stdio.h>#define s 6#define c 6int main() {int a[s][c] ={{1,3,1,4,3,1},{1,4,0,3,2,2},{3,4,1,2,4,2},{3,1,2,4,3,3},{3,0,3,2,1,4},{0,2,1,3,4,4}};int b[s]; int i,j,k,t,p;for(i=0;i<s;i++) for(j=0;j<c;j++)for(k=0;k<c-j-1;k++) if(a[i][k]>a[i][k+1]){t=a[i][k]; a[i][k]=a[i][k+1]; a[i][k+1]=t;}/* for(i=0;i<c;i++){for(j=0;j<c;j++)printf("%5d",a[i][j]);printf("\n");} printf("\n"); */for(i=0;i<s;i++){k=0; for(j=1;j<c;j++)if(a[i][j-k-1]==a[i][j])k++;else a[i][j-k]=a[i][j];b[i]=c-k;}/* for(i=0;i<s;i++){for(j=0;j<b[i];j++)printf("%5d",a[i][j]);printf("\n");} printf("\n"); */t=0; for(i=0;i<s;i++) for(j=0;j<=s;j++) if(b[i]==b[j] && i!=j) {p=1;for(k=0;k<b[i];k++)if(a[i][k]!=a[j][k]){p=0;break;}if(p){t++;break;}}printf("%5d\n",t); getch(); }

Короткий комментарий.

Решение сделано по описанному выше алгоритму. Ввод данных я не писал, задал значения переменным прямо в программе. Думаю, ввод данных для тебя не проблема, да и навряд ли матрица из 10 тыс. чисел вводится вручную. Вывод в C++ тоже можно заменить на потоковый, с cout.

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

Вторая часть решения - исключаем повторяющиеся стоящие рядом элементы, сжимая строку к началу. После этого "похожие" строки станут полностью одинаковыми и их будет легко сравнивать. После исключения повторяющихся элементов разные строки могут иметь разные длины, их запоминаем в массиве b.

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

В более медленных по сравнению со второй частью первой и третьей частях можно было бы применить быстрые способы сортировки, но я по-прежнему не верю, что это кому-нибудь нужно ;)

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

P.S. Кстати, интересный вопрос: какие числа могут встречаться в матрице? От и до?

Изменено 24 апреля, 2007 пользователем Тролль