Module with functions for sets

Share your advanced PureBasic knowledge/code with the community.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Module with functions for sets

Post 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.
Last edited by Little John on Sun Mar 28, 2021 6:43 pm, edited 29 times in total.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Functions for sets (implemented as maps)

Post 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()
rsts
Addict
Addict
Posts: 2736
Joined: Wed Aug 24, 2005 8:39 am
Location: Southwest OH - USA

Re: Functions for sets (implemented as maps)

Post 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.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Functions for sets (implemented as maps)

Post by Little John »

:-)

Thanks! You are welcome.

Regards, Little John
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Functions for sets (implemented as maps)

Post 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.
User avatar
Shield
Addict
Addict
Posts: 1021
Joined: Fri Jan 21, 2011 8:25 am
Location: 'stralia!
Contact:

Re: Functions for sets (implemented as maps)

Post by Shield »

Very useful and straight forward. Thank you. :)
Image
Blog: Why Does It Suck? (http://whydoesitsuck.com/)
"You can disagree with me as much as you want, but during this talk, by definition, anybody who disagrees is stupid and ugly."
- Linus Torvalds
SFSxOI
Addict
Addict
Posts: 2970
Joined: Sat Dec 31, 2005 5:24 pm
Location: Where ya would never look.....

Re: Functions for sets (implemented as maps)

Post by SFSxOI »

Good job. Thank you very much :)
The advantage of a 64 bit operating system over a 32 bit operating system comes down to only being twice the headache.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Functions for sets (implemented as maps)

Post by Little John »

Thank you, guys. :-)
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Functions for sets (implemented as maps)

Post 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()
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Functions for sets (implemented as maps)

Post 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.
davido
Addict
Addict
Posts: 1890
Joined: Fri Nov 09, 2012 11:04 pm
Location: Uttoxeter, UK

Re: Module with functions for sets

Post by davido »

Hi Little John,

Very nice work. Thank you for sharing. :D
DE AA EB
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Module with functions for sets

Post 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.
Poshu
Enthusiast
Enthusiast
Posts: 459
Joined: Tue Jan 25, 2005 7:01 pm
Location: Canada

Re: Module with functions for sets

Post by Poshu »

Damn, that's quite a useful module, thanks for sharing.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: Module with functions for sets

Post by Little John »

Thank you. :-)

The next version will additionally allow to generate all possible partitions of a given set.
davido
Addict
Addict
Posts: 1890
Joined: Fri Nov 09, 2012 11:04 pm
Location: Uttoxeter, UK

Re: Module with functions for sets

Post 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!
DE AA EB
Post Reply