Return to ts_subsets.adb CVS log

Up to [local] / OpenXM_contrib / PHC / Ada / Schubert

Annotation of OpenXM_contrib/PHC/Ada/Schubert/ts_subsets.adb, Revision 1.1.1.1

1.1       maekawa     1: with text_io,integer_io;                 use text_io,integer_io;
                      2: with Standard_Integer_Vectors;           use Standard_Integer_Vectors;
                      3: with Standard_Integer_Vectors_io;        use Standard_Integer_Vectors_io;
                      4:
                      5: procedure ts_subsets is
                      6:
                      7: -- DESCRIPTION :
                      8: --   Generates all subsets of k elements from a set of n elements.
                      9:
                     10:   k,n : natural;
                     11:
                     12:   function Complement ( n : natural; v : Vector ) return Vector is
                     13:
                     14:   -- DESCRIPTION :
                     15:   --   Returns the complement of the vector w.r.t. the set 1..n.
                     16:
                     17:     res : Vector(1..n-v'length);
                     18:     cnt : natural := 0;
                     19:     found : boolean;
                     20:
                     21:   begin
                     22:     for i in 1..n loop
                     23:       found := false;
                     24:       for j in v'range loop
                     25:         if v(j) = i
                     26:          then found := true;
                     27:               exit;
                     28:         end if;
                     29:       end loop;
                     30:       if not found
                     31:        then cnt := cnt + 1;
                     32:             res(cnt) := i;
                     33:       end if;
                     34:     end loop;
                     35:     return res;
                     36:   end Complement;
                     37:
                     38:   procedure Enumerate ( start,i,n : in natural; accu : in out Vector ) is
                     39:
                     40:   -- DESCRIPTION :
                     41:   --   Enumerates all subsets of 1..n, of size accu'length, starting to
                     42:   --   fill up accu(i) with entries in start..n.
                     43:
                     44:   begin
                     45:     if i > accu'last
                     46:      then put("Subset : "); put(accu);
                     47:           put("  Complement : "); put(Complement(n,accu)); new_line;
                     48:      else for l in start..n loop
                     49:             accu(i) := l;
                     50:             Enumerate(l+1,i+1,n,accu);
                     51:           end loop;
                     52:     end if;
                     53:   end Enumerate;
                     54:
                     55: begin
                     56:   put("Give the cardinality of whole set : "); get(n);
                     57:   put("Give the cardinality of subset : "); get(k);
                     58:   declare
                     59:     acc : Vector(1..k);
                     60:   begin
                     61:     Enumerate(1,1,n,acc);
                     62:   end;
                     63: end ts_subsets;