Problema gen "patrat magic"

Am o problema , daca ma poate ajuta cineva:
Se da o matrice de 500 de linii si 10 coloane. Trebuie populata aceasta matrice cu 0 si 1 in asa fel incit sa am suma pe linii egala , la fel si suma pe coloane egala ( sa zicem suma pe linie 7, iar suma pe coloana 300 ). Sumele ce trebuiesc obtinute sint la alegere, desi sint convins ca nu exista solutii pentru orice perechi de valori.
Backtracking-ul poate fi o solutie, dar cred ca timpii de executie sint foarte mari. Are cineva idei ?

am impresia ca nu e destul de explicita problema:
Daca umplii toata matricea cu 1 atunci o sa ai aceeasi suma pe fiecare linie, si aceeasi suma pa fiecare coloana... Sau daca pui 1 si 0 astfel incat fiecare linie sa aiba la fel puse cifrele... Sau dak pui matricea de 500/10 o omparti in 50 de matrici de 10 pe 10 in care umpli cu 1 diagonala principala, iar o sa se 'intample' cerintza...
Deci cum suna exact cerintza?

Nu poti sa specifici si suma pe linie, si suma pe coloana. Daca suma pe fiecare linie este 7, atunci suma tuturor elementelor este 7*500 = 3500, deci suma pe fiecare coloana este 3500/10 = 350.

Pe fiecare linie ai deci 7 de 1 si 3 de zero.
O solutie este sa generezi permutari aleatoare (uniformly random) ale acestei combinatii pe fiecare linie, si eventual sa faci backtracking la sfarsit, ca sa le potrivesti.

O alta solutie este sa imparti matricea, de exemplu in matrici patrate de 10x10, generezi o singura matrice cu suma de 7 pe fiecare linie si fiecare coloana (daca se poate), si apoi sa copii matricea asta de 50 de ori.

Edited by gniv, 06 December 2004 - 23:55.

Revin cu un caz concret: matricea are 37 coloane si 777 de linii. Suma pe linie este 5, iar suma pe coloana 105. Interesanta ideea cu impartirea pe matrici mai mici, dar cum ?

quaz, on Dec 7 2004, 11:22, said:

Pai asa trebuia sa spui de la inceput. In general problema nu are solutie, dar asta e un caz "fericit", construit anume, evident.

Matricea de 37x777 se poate imaprti in 21 de matrici de 37x37 (pur si simplu iei cate 37 de linii la rand din matricea originala). Acuma este suficient sa umpli matricea a.i. suma pe linii sa fie 5, si pe coloane tot 5. Uite cum se poate:

Matrice de 37x37:
1:    1 1 1 1 1 0 0 0 0 . . . 0 0 0 0 0
2:    0 1 1 1 1 1 0 0 0 . . . 0 0 0 0 0
3:    0 0 1 1 1 1 1 0 0 . . . 0 0 0 0 0
4:    0 0 0 1 1 1 1 1 0 . . . 0 0 0 0 0
. . . .
33:   0 0 0 0 0 0 0 0 0 . . . 1 1 1 1 1
34:   1 0 0 0 0 0 0 0 0 . . . 0 1 1 1 1
35:   1 1 0 0 0 0 0 0 0 . . . 0 0 1 1 1
36:   1 1 1 0 0 0 0 0 0 . . . 0 0 0 1 1
37:   1 1 1 1 0 0 0 0 0 . . . 0 0 0 0 1

Adica pui valorille de 1 pe diagonala. Daca nu-ti place ca e prea regulata, poti oricand sa permuti linii si/sau coloane, conditia ramane adevarata.

Edited by gniv, 07 December 2004 - 16:48.

Este o solutie, atit de simpla incit nici macar nu-mi dadea prin cap! Dar daca ne situam cu enuntul intr-un caz particular, si solutia este particulara. Imi cer scuze, initial cind am postat problema am omis o conditie pe care observ abia acum ca trebuie indeplinita. De aceea ma gindeam eu la backtracking, pe care daca l-am ocolit initial cred ca nu mai scapam acum de el.... ( poate la permutarea linii sau coloanelor matricii?). Conditia urmatoare ar fi:
1. fiecare linie contine 5 elemente cu valoarea 1.
2. pe fiecare linie am practic 10 grupuri de elemente nenule: (a11,a12,a13),(a11,a12,a14), (a11,a12,a15)...(a13,a14,a15)
3. conditia suplimentara si obligatorie ar fi ca pe toate celelalte linii sa nu mai am aceste grupuri. Grupul (a11,a12,a13) de pe linia 1 nu mai trebuie repetat in toate liniile matricii. Se admite insa repetitia grupurilor de doua elemente nenule , gen (a11,a12). Bineinteles, conditia se extinde asupra tuturor grupurilor de trei elemente nenule de pe toate liniile, fiecare astfel de grup netrebuind sa fie "dublat" pe o alta linie.
Cred ca abia acum se vede complexitatea problemei! Deci, backtracking acum, la permutarea coloanelor, sau la generarea matricii din start ?

Conditia asta nu poate fi indeplinita prin simpla permutare a liniilor/coloanelor in matricea care am dat-o eu. Se poate incerca alt fel de a genera matricea in mod regulat, de exemplu pozitiile 12345 pe prima line, 45678 pe linia a doua, s.a.m.d., dar nu stiu cum se poate completa pana la 37 de linii. Alternativ, dynamic programming.

gniv, on Dec 10 2004, 19:56, said:

Decit sa fac backtracking cu solutii particulare care inseamna permutari de matrici, mai bine fac backtracking-ul de la bun inceput. Nici nu vreau sa ma gindesc la timpii de executie....Oare nu exista vreo teorie matematica aplicabila la matrici care sa aduca matricea la forma care imi convine ? Cred ca imi caut cursurile din facultate si ma apuc de studiat! E vreun matematician pe aici ??!!