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
You can download the ZIP archive with the complete module code and some demo code from my website.