Page 1 of 3

Module with functions for sets

Posted: Sat Mar 19, 2011 10:18 pm
by Little John
Hi all,

a set is a basic datatype. It is defined as a collection with no duplicate elements, in which order has no significance.
Since the same is true for map keys, I have implemented sets using PureBasic's maps.
For detailed information about the functions, see comments in the code.

Current version: 1.81, 2021-03-28
Purebasic 5.20 LTS or newer required because the code is inside of a module.
Cross-platform, x86 and x64, Unicode compliant.
MIT License.

Code: Select all

; -- A module with functions for sets
; <https://www.purebasic.fr/english/viewtopic.php?f=12&t=45787>

; Version 1.81, 2021-03-28
; Purebasic 5.20 LTS or newer is required because of the module.
; Cross-platform, x86 and x64, Unicode compliant.

; The sets are implemented using PureBasic's maps. Like a map, a set is a
; collection with no duplicate elements, in which order has no significance
; (see e.g. <https://en.wikipedia.org/wiki/Set_(mathematics)>).
; The elements of the sets are strings, represented by the *keys* of the
; maps. The values of the map elements are ignored.
; A partition of a set 's' is a collection of non-empty disjoint subsets
; of 's' (blocks) whose union is 's'
; (see e.g. <https://en.wikipedia.org/wiki/Partition_of_a_set>).

; The data types used here are the structures 'Set' and 'Partition'.
; You can use the fields 'Label$' and 'Value' in both structures for your
; own purposes. Depending on your program, 'Value' could mean e.g. cost
; or weight or could be an ordinal number used for sorting the sets or
; partitions.
; If you want, you can Extend the structures according to your needs
; (see "set_demo_coalitions.pb"). The additional fields will be ignored
; by the routines of this module.

; ------------------------------------------------------------------------------
; MIT License
;
; Copyright (c) 2011, 2013, 2015, 2017-2019, 2021 Jürgen Lüthje <http://luethje.eu/>
; Copyright (c) 2015 for assembler code in procedure _Choose() Wilbert
;
; Permission is hereby granted, free of charge, to any person obtaining a copy
; of this software and associated documentation files (the "Software"), to deal
; in the Software without restriction, including without limitation the rights
; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
; copies of the Software, and to permit persons to whom the Software is
; furnished to do so, subject to the following conditions:
;
; The above copyright notice and this permission notice shall be included in all
; copies or substantial portions of the Software.
;
; THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
; SOFTWARE.
; ------------------------------------------------------------------------------


DeclareModule Set
   EnableExplicit
   
   Structure Set
      Map Element.i()      ; * read only *
      NumElements.i        ; * read only *
      Label$
      Value.i
   EndStructure
   
   Structure Partition
      List Block.Set()     ; * read only *
      NumBlocks.i          ; * read only *
      Label$
      Value.i
   EndStructure
   
   #DontSort = -1
   
   ; for procedure NumberOf_PartitionsT()
   #All      = 1
   #SameSize = 2
   
   Macro Size (_set_)
      ; return the number of elements in _set_
      MapSize(_set_\Element())
   EndMacro
   
   Macro Clear (_set_)
      ClearMap(_set_\Element())
      _set_\NumElements = 0
      _set_\Label$ = ""
      _set_\Value = 0
   EndMacro
   
   Macro Copy (_source_, _dest_)
      ; copy set _source_ to _dest_
      CopyStructure(_source_, _dest_, Set::Set)
   EndMacro
   
   Macro AddElement (_set_, _x_, _caseSensitive_=#True)
      ; add element _x_ to _set_, if it is not there already
      If _caseSensitive_ = #True
         AddMapElement(_set_\Element(), _x_)
      Else
         AddMapElement(_set_\Element(), LCase(_x_))
      EndIf
      _set_\NumElements = Set::Size(_set_)
   EndMacro
   
   Macro RemoveElement (_set_, _x_, _caseSensitive_=#True)
      ; remove element _x_ from _set_, if it is there
      ; (If _x_ is not in _set_, no error will be raised.)
      If _caseSensitive_ = #True
         DeleteMapElement(_set_\Element(), _x_)
      Else
         DeleteMapElement(_set_\Element(), LCase(_x_))
      EndIf
      _set_\NumElements = Set::Size(_set_)
   EndMacro
   
   Macro PartitionSize (_p_)
      ; return the number of blocks in _p_
      ListSize(_p_\Block())
   EndMacro
   
   Macro ClearPartition (_p_)
      ClearList(_p_\Block())
      _p_\NumBlocks = 0
      _p_\Label$ = ""
      _p_\Value = 0
   EndMacro
   
   ; -- creating sets and partitions
   Declare.i Create (*s.Set, lo.i, hi.i, stepp.i=1)
   Declare.i FromString (*s.Set, source$, caseSensitive.i=#True, sepElm$=",", brackets$="{}")
   Declare.i FromList (*s.Set, List source$(), caseSensitive.i=#True)
   Declare.i FromArray  (*s.Set, Array source$(1), caseSensitive.i=#True, start.i=0, last.i=-1)
   Declare.i FromArrayI (*s.Set, Array source.i(1), start.i=0, last.i=-1)
   Declare.i PartitionFromString (*p.Partition, part$, caseSensitive.i=#True, sepElm$=",", sepBlock$="} {")
   Declare.i FromPartition (*s.Set, *p.Partition)
   
   ; -- data conversion from sets and partitions
   Declare.i ToList (*s.Set, List result$(), sortByContent.i=#PB_Sort_Ascending)
   Declare.s ToString (*s.Set, sortByContent.i=#PB_Sort_Ascending, sepElm$=",", brackets$="{}")
   Declare.i PartitionToList (*p.Partition, List result$(), sortByContent.i=#PB_Sort_Ascending, sortBlocksBySize.i=#PB_Sort_Descending, sepElm$=",")
   Declare.s PartitionToString (*p.Partition, sortByContent.i=#PB_Sort_Ascending, sortBlocksBySize.i=#PB_Sort_Descending, sepElm$=",", sepBlock$="} {")
   
   ; -- save / load
   Declare.i Save (*s.Set, file$, flag.i=0)
   Declare.i Load (*s.Set, file$)
   
   ; -- basic operations
   Declare.i Union (*a.Set, *b.Set, *result.Set=#Null)
   Declare.i Intersection (*a.Set, *b.Set, *result.Set=#Null)
   Declare.i Difference (*a.Set, *b.Set, *result.Set=#Null)
   Declare.i SymmetricDifference (*a.Set, *b.Set, *result.Set=#Null)
   Declare.i Product (*a.Set, *b.Set, *result.Set, brackets.i=#True)
   Declare.i CrossPartition (*a.Partition, *b.Partition, *result.Partition=#Null)
   
   ; -- check membership etc.
   Declare.i IsSet (source$, caseSensitive.i=#True, sepElm$=",", brackets$="{}")
   Declare.i IsElement (*s.Set, x$, caseSensitive.i=#True)
   Declare.i IsSubset (*super.Set, *sub.Set)
   Declare.i IsProperSubset (*super.Set, *sub.Set)
   Declare.i IsEqual (*a.Set, *b.Set)
   Declare.i IsDisjoint (*a.Set, *b.Set)
   Declare.d Similar (*a.Set, *b.Set)
   Declare.i CheckPartition (*p.Partition, *s.Set=#Null)
   Declare.i IsEqualPartition (*a.Partition, *b.Partition, ordered.i=#False)
   
   ; -- calculate basic numbers
   Declare.q NumberOf_Subsets  (n.l)
   Declare.q NumberOf_SubsetsK (n.l, k.l)
   Declare.q NumberOf_Partitions  (n.l, ordered.i=#False)
   Declare.q NumberOf_PartitionsK (n.l, k.l, ordered.i=#False)
   Declare.q NumberOf_PartitionsT (type$, ordered.i=#False)
   
   ; -- generate subsets of a given set
   Declare.i FirstSubset  (*s.Set, *sub.Set)
   Declare.i NextSubset   (*s.Set, *sub.Set)
   Declare.i FirstSubsetK (*s.Set, *sub.Set, k.l)
   Declare.i NextSubsetK  (*s.Set, *sub.Set)
   
   ; -- generate unordered partitions of a given set
   Declare.i FirstPartition  (*s.Set, *p.Partition)
   Declare.i NextPartition   (*s.Set, *p.Partition)
   Declare.i FirstPartitionK (*s.Set, *p.Partition, k.l)
   Declare.i NextPartitionK  (*s.Set, *p.Partition)
   Declare.i FirstPartitionT (*s.Set, *p.Partition, type$)
   Declare.i NextPartitionT  (*s.Set, *p.Partition)
EndDeclareModule
Since the code now has more than 60 000 characters, it can't be posted here completely anymore.
You can download the ZIP archive with the complete module code and some demo code from my website.

Re: Functions for sets (implemented as maps)

Posted: Wed Jan 30, 2013 1:30 am
by Little John
New version 1.1

Changes
  • For compatibility with PB >= 5.10, function Bool() is used where appropriate
    (and Macro Bool() was added for PB versions < 5.10)
  • In Set_Create_FromString(), the default separator was changed from "|" to ",".
  • Set_Intersection()
    Set_Union()
    Set_Difference()
    Set_SymmetricDifference()
    now return the size of the resulting set
    (makes usage of the functions sometimes more convenient)
New functions
  • Set_Create_FromArrayI()
  • Set_ToString()
  • Set_Similar()

Re: Functions for sets (implemented as maps)

Posted: Wed Jan 30, 2013 4:04 am
by rsts
Don't know how I missed this before. Must have been posted when I was wasted (frequently :) )

Very nice. Many thanks for sharing.

Re: Functions for sets (implemented as maps)

Posted: Wed Jan 30, 2013 10:51 am
by Little John
:-)

Thanks! You are welcome.

Regards, Little John

Re: Functions for sets (implemented as maps)

Posted: Wed Jan 30, 2013 3:48 pm
by Little John
New version 1.11 :-)

Fixed
In the function Set_Similar() there was a division by 0, in case two empty sets were compared.

Re: Functions for sets (implemented as maps)

Posted: Wed Jan 30, 2013 5:08 pm
by Shield
Very useful and straight forward. Thank you. :)

Re: Functions for sets (implemented as maps)

Posted: Wed Jan 30, 2013 5:53 pm
by SFSxOI
Good job. Thank you very much :)

Re: Functions for sets (implemented as maps)

Posted: Thu Jan 31, 2013 6:43 am
by Little John
Thank you, guys. :-)

Re: Functions for sets (implemented as maps)

Posted: Sat Oct 05, 2013 8:34 am
by Little John
New version 1.20

Changes
  • The functions are now inside a module (PB 5.20+ required).
    => In your existing code that uses any of these functions, replace Set_xyz() with Set::xyz().
New functions
  • New()
  • NumberOf_Subsets()
  • FirstSubset()
  • NextSubset()

Re: Functions for sets (implemented as maps)

Posted: Wed Oct 16, 2013 4:30 pm
by Little John
New version 1.21

Changes
  • Function Equal() renamed to IsEqual(), so that the name is consistent with IsSubset() etc.
  • Some internal cosmetic changes.
New
  • The function NumberOf_Subsets() can now take an additional optional parameter:
    • NumberOf_Subsets(n) still returns the number of all subsets of a set with n elements.
    • NumberOf_Subsets(n, k) returns the number of subsets of a set with n elements, that have exactly k elements.

Re: Module with functions for sets

Posted: Wed Oct 16, 2013 7:29 pm
by davido
Hi Little John,

Very nice work. Thank you for sharing. :D

Re: Module with functions for sets

Posted: Fri Dec 06, 2013 7:13 pm
by Little John
Hi davido,
you are welcome! :-)

There is a new version 1.30.

Changes
  • Previously, a plain map was used for implementing a set.
    Now, the new Structure Set is used. That makes it easier to create arrays of sets, lists of sets etc. For this, also several internal changes were required.
  • Removed Macro New()
  • Changed function names:
    Create_FromString() --> FromString()
    Create_FromList() --> FromList()
    Create_FromArrayI() --> FromArrayI()
  • Function ToString() now has an option for sorting.
  • Slightly improved comments
  • Slightly improveed demo code
New function
  • ToList() converts a set to a linked list of its elements.

Re: Module with functions for sets

Posted: Tue Dec 10, 2013 12:36 pm
by Poshu
Damn, that's quite a useful module, thanks for sharing.

Re: Module with functions for sets

Posted: Tue Dec 10, 2013 2:58 pm
by Little John
Thank you. :-)

The next version will additionally allow to generate all possible partitions of a given set.

Re: Module with functions for sets

Posted: Tue Dec 10, 2013 10:03 pm
by davido
Version 1.30 is very nice, thank you, for sharing. :D

Modules have certainly made groups of similar functions so much more pleasant and easier to use than a pbi file of the past!

Looking forward to the next instalment!