Упорядочевывыние матрицы по количеству одинаковых элементов

KoLoB2006 · 13 Апр 2006

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

Синтаксис желательно C-like. На крайний случай подойдет и Pascal-like.
Можно хотя бы блок=схему, но лучше код.

Заранее спасибо!

ploki · 15 Апр 2006

Писал впопыхах, поэтому не сильно красивый, но полностью рабочий код (Delphi):

PHP:

unit FMain;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Grids;

type
  TArr= array of integer;
  TMat= array of TArr;
  TForm1 = class(TForm)
    sg: TStringGrid;
    en: TEdit;
    em: TEdit;
    Button1: TButton;
    Button2: TButton;
    SG2: TStringGrid;
    procedure FormCreate(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
    n,m: integer;
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
//Написал для теста (больше не используется)
{function CompareRows(Mat: TMat; CustomData: Pointer; i, j: integer): integer;
  //if a>b then res=1
  //if a=b then res=0
  //if a<b then res=-1
    var k: integer;
        iRow, jRow: TArr;
  begin result:=0;
    iRow:=Mat[i];
    jRow:=Mat[j];
    for k:=0 to High(iRow) do begin
      if (iRow[k]>0)and(jRow[k]=0) then begin result:=1; exit end;
      if (iRow[k]=0)and(jRow[k]>0) then begin result:=-1; exit end;
    end;
  end;}

//Функция сравнения строк матрицы -
// в данном случае просто сравнивает два целых числа,
// сопоставленных со строками
function CompareRows(Mat: TMat; CustomData: Pointer; i, j: integer): integer;
  //if a>b then res=1
  //if a=b then res=0
  //if a<b then res=-1
  begin
    result:=TArr(CustomData)[i]-TArr(CustomData)[j];
  end;

//Процедура сортировки строк матрицы, использующая для сравнения
// функцию CompareRows (сортировка неустойчивая - вариант HeapSort)
//Заполняет массив-оглавление Indices
procedure SortMat(Mat: TMat; CustomData: Pointer; Indices: TArr; Len: Integer=-1);
var
  i, k, t: integer;
  Tmp: integer;
begin
  if (Len<0) then begin
    Len:=Length(Mat);
  end;
  i := 2;
  repeat
    t := i;
    while t<>1 do begin
      k := t shr 1;
      if CompareRows(Mat, CustomData, Indices[k-1], Indices[t-1])>=0 then begin
        t := 1;
      end else begin
        Tmp := Indices[k-1];
        Indices[k-1] := Indices[t-1];
        Indices[t-1] := Tmp;
        t := k;
      end;
    end;
    inc(i);
  until  not (i<=Len);
  i := Len-1;
  repeat
    Tmp := Indices[i];
    Indices[i] := Indices[0];
    Indices[0] := Tmp;
    t := 1;
    while t<>0 do begin
      k := t shl 1;
      if k>i then begin
        t := 0;
      end else begin
        if k<i then begin
          if CompareRows(Mat, CustomData, Indices[k], Indices[k-1])>0 then  inc(k);
        end;
        if CompareRows(Mat, CustomData, Indices[t-1], Indices[k-1])>=0 then begin
          t := 0;
        end else begin
          Tmp := Indices[k-1];
          Indices[k-1] := Indices[t-1];
          Indices[t-1] := Tmp;
          t := k;
        end;
      end;
    end;
    dec(i);
  until  not (i>=1);
end;
procedure TForm1.Button1Click(Sender: TObject);
var
  i, j: integer;
  indices: TArr;
  EqNums: TArr;
  Mat: TMat;
  Row: TArr;
  //Процедура заполнения массива EqNums
  procedure FillEqNums;
    var
      i, j, k, Value, Count: integer;
      Used: array of boolean;
  begin
    //Вообще это надо делать через словарь! Будет код в две строчки.
    // Но мы обойдёмся, правда будет неэффективно.
    SetLength(EqNums, n);
    for i:=0 to n-1 do begin
      Row:=Mat[i];
      SetLength(Used, m);
      for j := 0 to m-1 do begin
        if not Used[j] then begin
          Value:=Row[j];
          Count:=0;
          for k:=0 to m-1 do
            if Row[k]=Value then begin
              inc(Count);
              Used[k]:=true;
            end;
        end;//not Used
        if EqNums[i]<Count then EqNums[i]:=Count;
      end;
      finalize(Used);
    end;
  end;

begin
  SG2.RowCount:=n+1;
  SG2.ColCount:=m+1;
  //Заполняем исходную матрицу
  SetLength(Mat, n, m);
  for i:=1 to n do begin
    for j := 1 to m do
      Mat[i-1,j-1]:=StrToInt(SG.Cells[j,i]);
  end;

  //Заполняем массив EqNums с макcимальными количествами одинаковых элементов
  // в строках матрицы Mat
  FillEqNums;

  //Заполняем оглавление в естественном порядке
  SetLength(Indices, n);
  for j:=0 to n-1 do Indices[j]:=j;
  //Сортируем матрицу
  SortMat(Mat, EqNums, Indices, n);

  //Выводим отсортированную матрицу, используя сформированное оглавление
  for i:=1 to n do begin
    for j := 1 to m do
      SG2.Cells[j,i]:=IntToStr(Mat[Indices[i-1],j-1]);
  end;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  i, j: integer;
begin
 sg.RowCount:=strtoint(en.text)+1;
 sg.ColCount:=strtoint(em.text)+1;
 n:=strtoint(en.text);
 m:=strtoint(em.text);
 for i:=1 to n do begin
    for j := 1 to m do
      SG.Cells[j,i]:='0';
  end;
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  i, j: integer;
begin
  n:=SG.RowCount-1;
  m:=SG.ColCount-1;
  for i:=1 to n do begin
    for j := 1 to m do
      SG.Cells[j,i]:='0';
  end;
end;

end.

Skorp · 29 Май 2006

так, ИМХО попроще и нагляднее:

Код:

#include "stdafx.h"
#include <vector>
#include <algorithm>

typedef int ValueType;
typedef std::vector<ValueType> Row;

int eqCount(Row row)
{
	if(row.begin() == row.end())
		return 0;

	std::sort(row.begin(), row.end());
	
	int count = 0;
	int maxCount = count;
	ValueType lastValue = row[0];
	for(Row::const_iterator it = row.begin(); it != row.end(); ++it)
		if(*it == lastValue)
			count++;
		else {
			lastValue = *it;
			if(count > maxCount)
				maxCount = count;
			count = 1;
		}

	return std::max(count, maxCount);
}

bool comp(const Row& left, const Row& right)
{
	return eqCount(left) < eqCount(right);
}

typedef std::vector<Row> MyMat;

int _tmain(int argc, _TCHAR* argv[])
{
	MyMat mat;
	
	// здесь надо
	// заполнить матрицу

	std::sort(mat.begin(), mat.end(), comp);
	
	// здесь вывести отсортированную матрицу
}

ploki · 29 Май 2006

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

. Естественно, что с готовыми классами проще и нагляднее

К твоему IMHO присоединяюсь. Если дополнительно словарь(int, int) использовать, будет ещё короче.

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

Skorp · 29 Май 2006

в вопросе хотели хотя бы блок схему - я и постарался написать программу аля блок-схема

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

по поводу подсчета количества одинаковых в ряде - можно отдельные дебаты развернуть, алгоритм с предварительной сортировкой дает практически гарантированное n*(1+log(n)), использование объектов типа map - скорее всего в асимптоте n*(1+log(n)/2), но во втором случае имеем фрагментированную память, что на современных машинах как правило самый большой тормоз - так что без тестов я бы не сказал в каких условиях какой алгоритм окажется быстрее.

ploki · 29 Май 2006

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

Плюс, inplace-сортировку строки нельзя проводить по условию задачи! Так что вопрос об использовании памяти тоже встаёт.

А вообще, если знать что-то заранее о природе элементов, то так можно развернуться...

Упорядочевывыние матрицы по количеству одинаковых элементов

KoLoB2006

Турист

ploki

Турист

Skorp

Гость

ploki

Турист

Skorp

Гость

ploki

Турист