[megoldva] Táblázat felbontása azonos összegű részekre

Algoritmusok

Adott egy 4x16-os számtáblázat, amelyben mind a 4 oszlopban szereplő (egész) számok összege 16. (Három példa: http://web2.osb.hu/z/4x16_particiok.xlsx )
Arra van szükségem, hogy a 16 sort négyfelé szedjem, és mind a négy rész oszlopainak összege 4 legyen (ahogy a példa táblázatban is látszik).
Ezt eddig kézzel csináltam, és mindig sikerült (3x). Érdekelne, hogy ezt mindig meg lehet-e tenni (matekosok?) s írna-e valaki egy frappáns programot, amivel ezt automatizálni lehet? (Amúgy a http://pampyra.com -hoz tartozó játékok tervezéséhez kell; valódi életből vett ügy.)

Utólag felvett megszorítások: nem lehet két azonos sor, és minden sorban 4 az elemek összege.

  • 8048 megtekintés

( hud | 2012. 01. 03., k – 20:02 )

Kicsit pontosíthatnád a feladatot. Ha az első sorban 16-ok vannak, a többiben pedig 0, akkor nyílván nem lehet felbontani.

( zolti v | 2012. 01. 03., k – 21:22 )

"Ezt eddig kézzel csináltam, és mindig sikerült (3x)"
Csodálkoztam volna ha nem megy. Míg 4-nél nagyobb szám nincs benne nincs akadálya a válogatásnak.

A Gnumeric azt mondta:'Meghatározatlan számformátum-azonosító (42)'
lehet nem láttam minden részét a problémádnak.

( -Mr- | 2012. 01. 03., k – 22:50 )

Ha az a kérdés, hogy ha minden sorban szereplő számok összege 4 és minden oszlopban szereplő számok összege 16, akkor minden eseteben lehetséges-e 4 olyan csoportra felosztani amiben a sorokban és oszlopokban szereplő értékek összege 4. Akkor a válasz egyértelműen nem. Vannak olyan kombinációk, ahol nem tudod felosztani 4 db 4-es csoportra a sorokat hogy minden oszlop összege 4 legyen.

Ha a feladat az lenne, hogy olyan új feladványokat kellene létre hozni amiben a 4x16-os mátrixra mind a három feltétel teljesül, nos az lehetséges.

Persze hogy lehet. A lenti példa megfelel ennek a plusz feltételnek is (bár az általad linkelt 3 példa sem teljesíti ezt a plusz feltételt).

31--
3-1-
3--1
22--
2-2-
2--2
1--3
-31-
-3-1
-22-
-2-2
-211
-13-
--31
--13
--22

Itt is látható, csak az első oszlopot nézve, hogy nem tudod felosztani úgy hogy jó legyen, mert 3db 3-as értékhez kellene 3db 1-es is.

Szép. Köszi.
Egyébként a 3 példából csak 1 nem teljesíti a "különböző sorok" megszorítást, és az is csak azért nem, mert két db. 1-1-1-1 sor van. Az itt nem látszik, hogy az két különböző négyszínű tetraéderből keletkezett (amelyek térben nem hozhatóak fedésbe egymással).

Már csak egy jó kis felbontóprogramra vágynék. :)

Ha X a 4x16-os táblázat, akkor először megpróbálod úgy két részre bontani, hogy két 4x8-as táblát kapj (X__1, és X_2) amelyekre teljesül az, hogy az oszlopaik összege 8. (Végigiterálsz a sorokon és figyeled, hogy az oszlopok összege 8-e; ha túlmegy rajta, backtrack.) Utána ugyanezt megismétled X_1-en és X_2-n, de a kikötés az, hogy az oszlopok összege legyen 4. Legalábbis így elsőre ezt mondanám.

-----------
"Generally, Russian technology assumes dumb machines and smart humans, not the other way around." -- The Russian Tea HOWTO

( nosy | 2012. 01. 07., szo – 17:43 )

@szz : http://pastebin.com/LHc2DXQy
Ezek a lényegesen különböző (sorokat nem permutálom) jó táblázatok közül azok, amelyeknek van jó particionálása, de csak minden 10000-edik, illetve 10 perc után leállítottam a futást... (én a 0004-szerű sorokat is belevettem a játékba, de ezt kiveheted ha nem kell.) Ha ilyesmi kellene elküldöm a programot.
ncs

( joco01 v | 2012. 01. 07., szo – 18:03 )

Brute force: 16 alatt 4 = 1820, maradék 12 alatt 4 = 495, maradék 8 alatt 4 = 70, 1820*495*70= ~63 millió lehetőség, és ha minden további trükk nélkül csak menet közben vágod a keresési fát, akkor elég hamar meglesz a megoldás.

--
joco voltam szevasz

@joco: azt is vedd figyelembe hogy az első fázisban ki kell választani a harmincegynéhány jelölt sorból tizenhatot, úgy hogy az oszlopok összege 16-legyen, majd a kapott rendszert particionálni (te csak erről beszéltél). Egyébként tényleg "gyorsan" lefut (kb 15 perc, egy átlagos kétmagos Athlon-on)
ncs

@joco: én a az összes megoldás generálására gondoltam, nemcsak egy adott tábla partícionálhatóságára. Ezért először az összes szóba jöhető sorból (ezek vannak 31-en vagy 35-en, ha a 4-est is megengedjük) kiválasztottam 16-ot, menetközben ellenőrizve az oszlopösszeget, majd a kapott táblázatot próbáltam particionálni.
ncs

( Nyosigomboc v | 2012. 01. 07., szo – 18:16 )

Az is kikotes, hogy csak a 0,1,2,3 szamok lehetnek benne? A peldaidban csak ezek vannak.
Vagy jo sor a -1000,-1000,-1000,3004 is?

--
There are free things in life i'll never understand
Spelling and counting

Szerintem ha ez a piramisos játékkal van kapcsolatban, akkor mivel ott egy testnek 4 oldala van, így gondolom "0-3"-ból kellene választani, mert az reprezentálná helyesen az oldalak különbözőségét.
Mondjuk még nem világos matematikailag ez hogy kapcsolódik a különböző színű oldalú testekhez, de ezt valamiért én alapértelmezettnek vettem.

Ja és bocs az előbb benéztem, nem vettem figyelembe a negatív előjelet és hogy ez csak egy sor. Azt hittem az 1000 az egy sor :)

Elnézést, hogy sokáig nem néztem az oldalt... Igen, csak 0, 1, 2, 3 közül kerülhetnek ki a számok -- a négy színnek megfelelően, és azért vannak négyen, mert a tetraédernek négy oldala van, amelyek a fenti színekkel befestendőek.

Konkrét programkódra is vágyom, hogy magam is kísérletezhessek. :-)

A http://pastebin.com/gc7QYVje többsoros keresés révén tetszőleges mintát meg lehet találni a program kimenetében. (Előzőleg rendezni kell a bemeneti táblázatot.)
A fenti c programot úgy módosítottam, hogy minden sort írjon ki, így a 18554923 soros teljes kimenetben kedvemre kereshetek. A feladatban megadott példatáblázat első része ilyen megoldást adott (utána zárójelben az én kézi megoldásom; több helyes megoldás is van):

0022:2(3)
0112:2(1)
0121:3(1)
0220:3(4)
0301:4(2)
1003:1(4)
1012:4(2)
1030:1(2)
1111:1(1)
1120:4(3)
1210:2(4)
1300:1(3)
2002:3(3)
2011:4(4)
2101:3(2)
3100:2(1)