Metaprogramování – Pascal – Fórum – Programujte.com

Mám následující problém: Chci napsat program, který pro uživatelem "rozumně" zvolená čísla k, n vypíše všechny k-prvkové kombinace z n prvků. Bylo by to velmi jednoduché, kdybych měl k dispozici jazyk, ve kterém by šlo napsat program, jenž by si pro zvolené k vždy sám "doprogramoval" k do sebe vnořených cyklů (1. do 2., 2. do 3., ..., k-1. do  k-tého.); stačilo by dát programu rekurentní návod, jak to v závislosti na uživatelem zvolených číslech k, n udělat. Že něco takového jde, už vím. Uvítám nicméně praktickou radu, kudy se při řešení problému vydat.

Poznámka: Zatím umím programovat jen v Pascalu. V něm jsem již napsal programy, které pro uživatelem zvolené n vypíší všechny 1-, 2- a 3-prvkové kombinace z n prvků.

#1 Jacobson
Použij standardní rekurzi.

Přesně tak, to co potřebuješ, se jmenuje rekurze.

Rekurze znamená, že metoda (funkce) ve svém těle volá sebe samu.

Často se jako příklad uvádí výpočet faktoriálu. Zavoláš funkci pro výpočet faktoriálu z čísla x a uvnitř té funkce je napsáno x * faktoriál z čísla (x-1).

Ok, schvalne budu proti rekurzi. Rekurze je pekna teoreticky, ale prakticky je treba ji prepsat stejne nerekurzivne, kvuli rychlost zpracovani a narokum na pamet. Rozhodne si dej tu praci ji prepsat nerekurzivne. Pocet kombinaci se da spocitat a i kdyby ne, jsou tu cykly repeat-until.
A jazyk bych ti doporucil zkusit javascript. Prijde mi na takove pokusy o malinko lepsi. Nevyzaduje nic nez textovy editor, treba notepad a webovy prohlizec. Aspon u mne ma plusko.

#4 peter
Použití rekurze vůbec nemusí mít negativní dopad na rychlost zpracování.

#2 Kit
Děkuji za radu. Zatím mi ale nedochází, jak bych v mohl v Pascalu rekurzivně zadat funkci, která má provést k cyklů zanořených jeden do druhého, pro uživatelem zadaná čísla k, n. Mohl bys zde napsat tvar zadání takovéto funkce v tomto jazyce?

#6 Jacobson
Napadá mě použití množiny. Funkce zavolá sebe samu a jako parametr bude mít množinu bez toho elementu, který právě zpracovává.

V Pascalu jsem už dlouho neprogramoval a nemám v úmyslu se k němu vracet. Zkus napsat své řešení a můžeme kolem toho diskutovat.

Připojen obrázek.

Připojen obrázek.

Připojen obrázek.

#7 Kit
OK, popíši tedy svoji konstrukci systému všech k-prvkových podmnožin n-prvkové množiny pro k=1, 2, 3. Pak sem pro jednotlivá k dám kódy mých prográmků, které umí prvky systému vypsat. Dál se pokusím vyložit svoji obecnou konstrukci systému všech k-prvkových podmnožin n-prvkové množiny. A nakonec uvedu kód příslušného prográmku, který ale jaksi nejede.

Program VycetKombinaci1_n;

var n,i : integer;

begin
  write('Zvol n v rozmezí od 1 do 32 767 a stiskni enter:');
  readln(n);
  if n=1 then
    begin
      writeln(1);
      write('Pro ukončení stiskni Enter.');
      readln;
    end;
  if n>1 then
    begin
      i:=1;
      writeln(i);
      repeat
        i:=i+1;
        writeln(i);
      until i=n;
      write('Pro ukončení stiskni Enter.');
      readln;
   end;
end.

#7 Kit

Program VycetKombinaci2_n;

var n,i,j : integer;

begin
  write('Zvol n v rozmezí od 2 do 32 767 a stiskni enter:');
  readln(n);
  if n=2 then
    begin
      writeln(1,' ',2);
      write('Pro ukončení stiskni Enter.');
      readln;
    end;
  if n>2 then
    begin
      i:=1;
      j:=2; 
      writeln(i,' ',j);
      repeat
        repeat
          j:=j+1;
          writeln(i,' ',j);
        until j=n;
        i:=i+1;
        j:=i+1;
        writeln(i,' ',j);
      until j=n;
      write('Pro ukončení stiskni Enter.');
      readln;
    end;
end.

#7 Kit

Program VycetKombinaci3_n;

var n,i,j,k : integer;

begin
  write('Zvol n v rozmezí od 3 do 32 767 a stiskni enter:');
  readln(n);
  if n=3 then
    begin
      writeln(1,' ',2,' ',3);
      write('Pro ukončení stiskni Enter.');
      readln;
    end;
  if n>3 then
    begin
      i:=1;
      j:=2;
      k:=3; 
      writeln(i,' ',j,' ',k);
      repeat
        repeat
          repeat
            k:=k+1;
            writeln(i,' ',j,' ',k);
          until k=n;
          j:=j+1;
          k:=j+1;
          writeln(i,' ',j,' ',k);
        until k=n;
        i:=i+1;
        j:=i+1;
        k:=j+1;
        writeln(i,' ',j,' ',k);
      until k=n;
      write('Pro ukončení stiskni Enter.');
      readln;
    end;
end.

#7 Kit

#7 Kit

Poslední dva body už neumím napsat. Teoreticky dovedu napsat program pro libovolné k z množiny {1, 2, ...}, odpovídající na vstup n, dovedu vlastně i napsat program, který by odpovídal na vstup k, n, nic z obojího však pro mě není prakticky proveditelné, mají-li moje programy fungovat i pro vysoké hodnoty k. 

#7 Kit
Oprava: Předposlední bod bych uměl napsat, ale nechce se mi s tím ztrácet čas. A k psaní posledního bodu mi chybí jakákoli motivace, neboť vidím, že kód mám celý špatně.

Program VycetKombinaci_k_n;

var
  n,k,i: integer;
  P: array[1..32766] of integer;

function F(x: integer): integer;
  begin
    P[k-x]:=P[k-x]+1;
    F:=P[k-x]
  end;

function G(x: integer): integer;
  begin
    for i:=k-x+1 to k do P[i]:=P[i-1]+1;
    G:=P[i]
  end;

procedure R;
  begin
    for i:=1 to k-1 do write(P[i],' ');
    writeln(P[k])
  end;

procedure S(x,n: integer);
  begin
    if x=2 then
      begin
        repeat
          repeat
            F(0);
            R;
          until P[x]=n;
          F(1);
          G(1);
          R;
        until P[x]=n;
      end;
    if x>2 then
      begin
        repeat
          S(x-1,n);
          F(x-1);
          G(x-1);
          R;
        until P[x]=n
      end
  end;

begin
  writeln('Zvol n v rozmezí od 3 do 32 767 a stiskni Enter.');
  readln(n);
  writeln('Zvol k v rozmezí od 2 do n-1 a stiskni Enter.');
  readln(k);
  begin
    for i:=1 to k do P[i]:=i;
    for i:=1 to k-1 do write(P[i],' ');
    writeln(P[k]);
    S(k,n);
    writeln('Pro ukončení stiskni Enter.');
    readln
  end
end.

Tak jsem si dal tu práci a pokusil se přece jen program obsahující rekurentně deklarovanou proceduru provádějící k do sebe zanořených cyklů napsat. I když mi to pořád nejede, myslím, že jsem se již podstatně přiblížil k řešení. Část procedury pro první IF je funkční, část pro druhé zatím nikoli. Program se zanoří až do nejnižšího cyklu a provádí jej tak dlouho, dokud nenaplní kapacitu proměnné P[k]; omezující podmínku "until P[k]=n" ignoruje. Pokud někdo bude vědět, kde je chyba, uvítám, když to sem napíše.

#14 Jacobson
Nechce se mi luštit kód, kde má všechno jednopísmenný název a nevím předem, k čemu to je. Takže to vezmu obecně:

0) Nulaprvkové kombinace nemají smysl, nedělej nic.

1) Jednoprvkové kombinace z n čísel: prostě vypiš čísla od 1 do n.

2) Dvouprvkové kombinace z n čísel: vezmi číslo 1 a vypiš čísla od 2 do n, pak vezmi 2 a vypiš od 3 do n atd.

3) Obecné k-prvkové kombinace z n čísel: vezmi číslo 1 a proveď celý výpis pro k-1 prvků od 2 do n. Pak vezmi 2 a proveď to zase pro k-1 od 3 do n atd., zastav se k prvků před n.

S rekurzí to bude celkem jednoduché:

procedure vypis(pocet,zacatek,konec:integer);
var i:integer;
Begin
if pocet>=1 {pro mene nez jednoprvkove kombinace nedelej nic}
  then for i:=zacatek to konec-pocet+1 do
        begin
        write(i,' '); {vypis prvni cislo a oddelovaci mezeru...}
        vypis(pocet-1,i+1,konec); {...a k nemu pripis vsechny kombinace o k-1 prvcich}
        end;
End;

V hlavním programu si necháš zadat k a n a pak už jenom zavoláš vypis(k,1,n) a je vystaráno. Určitě nebudeš potřebovat žádná pole ani množiny.

V tom mém kódu je ovšem háček: vypsané kombinace nejsou nijak vizuálně oddělené, čísla se sypou na obrazovku jedno za druhým. Zalomení řádku po každé kombinaci už nechám na tobě, ať z té školy taky něco máš :-). Úplně triviální to není, budeš muset výpisu přidat jeden parametr, který se má vypisovat před tím zbytkem, ale půjde to.

Program VycetKombinaci_k_n;

var
  n,k,i: integer;
  P: array[1..32766] of integer;

function F(x: integer): integer;
  begin
    P[k-x]:=P[k-x]+1;
    F:=P[k-x]
  end;

function G(x: integer): integer;
  begin
    for i:=k-x+1 to k do P[i]:=P[i-1]+1;
    G:=P[i]
  end;

procedure R;
  begin
    for i:=1 to k-1 do write(P[i],' ');
    writeln(P[k])
  end;

procedure S(x:integer);
  begin
    if x=2 then
      begin
        repeat
          repeat
            F(0);
            R;
          until P[k]=n;
          F(1);
          G(1);
          R;
        until P[k]=n;
      end;
    if x>2 then
      begin
        repeat
          S(x-1);
          F(k-1);
          G(k-1);
          R;
        until P[k]=n
      end
  end;

begin
  writeln('Zvol n v rozmeí od 3 do 32 767 a stiskni Enter.');
  readln(n);
  writeln('Zvol k v rozmezí od 2 do n-1 a stiskni Enter.');
  readln(k);
  for i:=1 to k do P[i]:=i;
  for i:=1 to k-1 do write(P[i],' ');
  writeln(P[k]);
  i:=k;
  S(i);
  writeln('Pro ukončení stiskni Enter.');
  readln
end.

Hotovo. Přikládám kód programu po odladění.

Vzkaz pro uživatele Kit a RomanZ: Díky, měli jste pravdu, stačilo použít standardní rekurzi.

Vzkaz pro uživatele Microsoft: Myšlenku máš v zásadě dobrou, ale Tvůj program k-prvkové podmnožiny n prvkové množiny nesype. Chyba Tvého řešení je podle mě již na úrovni algoritmu. A jedna malá poznámka: 0-prvkové kombinace mají smysl. Každá množina obsahuje právě jednu: { }.

Beru zpět vzkaz pro uživatele Microsoft, kromě závěrečné poznámky. Program kombinace vypisuje. Pokusím se jej odladit a pokud uspěji, dám sem zdrojový kód.

#15 Mircosoft
Tvůj kód je velmi úsporný, asi to máš dobře promyšlené, ale nenapadá mě, jaký parametr mám do procedury vypis přidat, abych mohl program odladit. Budu Ti vděčný, pokud trochu víc napovíš.

#16 Jacobson
Konec radosti. Část procedury S pro druhé IF je funkční, zvolím-li k=3, jinak ne.

Hm, mám to tak úsporné, že to nefunguje :-].
V tom cyklu musí být místo write a dalšího volání vypisu podmínka: if pocet=1 then writeln else vypis, jinak to píše kraviny (jo, opravdu writeln - ten if zajišťuje, že se bude psát až celá kombinace a ne mezihodnoty odpředtím).

V tom dalším parametru musí být seznam všech čísel z předchozích úrovní zanoření, který se při pocet=1 vypíše před to jedno nové číslo. Dá se udělat třeba stringem, který je při prvním volání vypisu prázdný a při každé rekurzi se k němu zprava připojí aktuální hodnota i (převedená na text) a nějaký oddělovací znak. Tentokrát jsem si to opravdu odzkoušel a funguje to :-).
Pro větší čísla budou problémy s přetečením zásobníku, ale pro začátek to postačí. Ideální by samozřejmě bylo napsat to bez rekurze.

Zasláno z mobilního telefonu.

#20 Mircosoft
Víš co, udělal bys nejlíp, kdybys sem dal funkční zdrojový kód. Nechce se mi luštit Tvoje nápovědy. A krom toho mi nejde o získání kódu jakéhokoli funkčního programu, ale o odladění toho mého mého.

OK, žádný problém, přestanu napovídat :-).
Celý funkční kód ti nedám, to bys to měl moc jednoduché a koneckonců moje známka to nebude. Takže pojďme na to ladění.

Na začátku si necháš zadat n a k, to je určitě v pořádku. Potom vyplníš pole P čísly od 1 do k. Tady už jsem se ztratil. Nemělo by to být spíš do n? Fakt nevím, potřeboval bych vědět, jak je to myšleno.
Procedura S se volá rekurzivně až při k>2, což mi připadá divné - na jednoduchý cyklus se kombinace redukují až při k=1, při 2 a víc už je rekurze potřeba.
Funkce F zvětšuje o 1 jedno číslo někde u konce pole, funkce G čísla nějak přesouvá a zvětšuje. Jak to má fungovat netuším, kombinace v tom prostě nevidím. Možná jenom špatně koukám, zkus mě nějak nakopnout. Návratové hodnoty těch dvou funkcí jsou každopádně zbytečné, protože se nikde nevyužívají.
Procedura R je výpis pole, to mi došlo. Ovšem zase jenom do k. Že by v tom poli měla být po skončení všech funkcí ta hledaná kombinace?

Zasláno z mobilního telefonu.

#22 Mircosoft
Tak už to mám - tentokrát již doopravdy - odladěné. Jak budu mít čas, dotáhnu zdrojový kód tak, aby program vypisoval kombinace pro libovolnou "rozumně" zvolenou dvojici (n, k), kde k, n jsou celá nezáporná čísla splňující nerovnost k <nebo= n, a zdrojový kód zde vystavím. Podotýkám, že jsem při konečném odlaďování užil tvůj poslední příspěvek jako zdroj námětů. Co přesně bylo potřeba udělat, nevím, jisté však je, že to už funguje. Budu-li mít čas, doplním ke kódu i vysvětlení, jak že to ten program vlastně ty kombinace vytváří a vypisuje.

Jinak jsem studentem práv, nikoli informatiky nebo něčeho podobného, takže známka z toho nebude.

#22 Mircosoft

Právě jsem vystavil zdrojový kód odladěného a "dotaženého" programu. V komentáři hovořím k Tobě, nedopatřením jsem ale příspěvek Tobě neadresoval (tj. nevložil jsem jej jako odpověď na Tvůj poslední příspěvek).

#24 Jacobson
Malá oprava: Místo |M| patří |M(V)|.

#26 Jacobson
Místo psaní dodatků můžeš určitou dobu po zveřejnění svůj příspěvek sám editovat.

#27 Kit
Dík za upozornění.

->Jacobson: jsem rád, že ti to funguje, a díky za vysvětlení. Algoritmus hledání variací už mi popisovat nemusíš - sice mě docela zajímá, ale už to nedělám pro tebe, tak můžu beze spěchu bádat :-).

Program vystavím jako obvykle na svojí stránce v oddělení školních příkladů, v rámci příští aktualizace.

Zasláno z mobilního telefonu.

#24 Jacobson
K popisku svého příspěvku s řešením problému dodávám, že moje oprava z 28. 6. jej zdaleka nedala do pořádku, kód je nicméně funkční. Kdokoli by měl k popisku dotazy, nechť je sem napíše. Rád odpovím.

Tak tady je moje řešení (trochu pozdě, ale přece):
mircosoft.mzf.cz/download/kombinace.zip
Oproti tvému je jednodušší, ale zase má o dost větší spotřebu paměti (string v parametru rekurzivně volané procedury). Výsledky máme oba stejné a zdá se, že správné.

Zasláno z mobilního telefonu.