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     ! 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;