[ emiraga @ 20.02.2006. 21:52 ] @
Zdravo,

Definisimo
to je skup ciji elementi predstavljaju sve skupove koji su kombinacije brojeva i koji imaju ukupno razlicitih brojeva.
Broj elemenata skupa je , dok svaki element skupa ima ukupno elemenata.

Primjer: = { {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4} }

Zadati su

=
=

Zadatak nam je pronaci , tako da skup ima minimalan broj elemenata i da za svaki element postoji bar jedan element tako da je .

---

Slobodno govoreci se moze interpretirati kao "a od c" uz onaj dodatni uslov koji se vezuje za broj .

Primjer:za
Code:

1 2 3 4 5 6
1 2 3       7 8 9
1 2   4     7     10 11
1 2             9    11 12 13
1   3   5     8      11       14
1   3     6 7   9             14
1   3       7     10    12 13
1     4 5       9 10          14
1       5 6             12 13 14
1       5     8 9 10 11
1         6 7 8   10          14
  2 3 4                 12 13 14
  2 3     6     9 10          14
  2   4   6   8      11       14
  2     5   7   9    11       14
  2     5     8   10    12 13
    3 4 5   7 8   10
    3 4       8 9 10 11
    3   5 6 7     10 11
    3     6   8      11 12 13
      4 5 6 7 8 9
      4 5   7        11 12 13
      4   6     9 10    12 13
            7 8 9       12 13 14

(ovo sam ovako poravnao da ljepse izgleda, uklonite duple razmake ako Vam trebaju samo brojevi)

Imam jos nekoliko primjera za razlicite vrijednosti . Trazim pomoc oko odredjivanja algoritma za generisanje/odabiranje ovakvih kombinacija.

Edit: prijasnji primjer nije bio potpun.

[Ovu poruku je menjao emiraga dana 21.02.2006. u 00:30 GMT+1]
[ DDMM @ 26.02.2006. 17:02 ] @
Meni vec izgleda da je S vec takav skup.

Cini mise da bi trebalo da trazis poskup od P koji je minimalan a sadrzi S.
[ emiraga @ 26.02.2006. 17:09 ] @
Citat:
tako da skup ima minimalan broj elemenata


To sam napisao u uslovu, mozda sam to trebao malo vise naglasiti, jer je to upravo kljucni dio.
[ DDMM @ 27.02.2006. 00:49 ] @
Ipak S nije takav skup kao sto sam mislio.


evo neki pseudo kod koji resava problem, grubom silom.

Code:

napuni P;
T={}; // je prazan
// prodjes sve skupove od P
for( p=H(b,c).begin(); p != H(b,c).end(); p++ )
 { 
  // probas dali je svaki t iz T podskup od p iz P
  for( t = T.begin(); t != T.end(); t++ )
   if( t posskup p ) break;
  
   // nije sledi ubacivanje 
   if( t == T.end() )
    {
     // generises sve podkombinacije od p-a.
     // malo nezgodan zapis H(p) 
    // npr:  a=2, p={4,5,6} H(p)={ {4,5},{4,6},{5,6} }

     for( tt=H(p).begin();  tt=H(p).end() ; tt++ )
      {
       if( tt nije element od T ) // eto ga nov clan
        {
          tt.inset( tt ); break; //jer dovoljan je samo jedan
         } 
      }
    }
 }


Nego da te pitam.
Pravis program za LOTO? A?


[Ovu poruku je menjao DDMM dana 27.02.2006. u 01:51 GMT+1]