It is currently Wed Jun 26, 2019 8:44 am

All times are UTC + 1 hour




Post new topic Reply to topic  [ 32 posts ]  Go to page 1, 2, 3  Next
Author Message
 Post subject: Module with functions for sets
PostPosted: Sat Mar 19, 2011 10:18 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3577
Location: Berlin, Germany
Hi all,

a set is a basic datatype. It's 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.75, 2018-12-27
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:
; -- A module with functions for sets
; <https://www.purebasic.fr/english/viewtopic.php?f=12&t=45787>

; Version 1.75, 2018-12-27
; 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 add more fields to the structures for your needs.
; They will just be ignored by the routines of this module.

; ------------------------------------------------------------------------------
; MIT License
;
; Copyright (c) 2011, 2013, 2015, 2017-2018 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 _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
   
   ; -- data conversion to set or partition
   Declare.i FromString (source$, *result.Set, caseSensitive.i=#True, sepElm$=",", brackets$="{}")
   Declare.i FromList (List source$(), *result.Set, caseSensitive.i=#True)
   Declare.i FromArrayI (Array source.i(1), *result.Set, start.i=0, last.i=-1)
   Declare.i FromArrayS (Array source$(1), *result.Set, caseSensitive.i=#True, start.i=0, last.i=-1)
   Declare.i PartitionFromString (part$, *p.Partition, caseSensitive.i=#True, sepElm$=",", sepBlock$="} {")
   Declare.i FromPartition (*p.Partition, *result.Set)
   
   ; -- data conversion from set or partition
   Declare.i ToList (*a.Set, List result$(), sortByContent.i=#PB_Sort_Ascending)
   Declare.s ToString (*a.Set, sortByContent.i=#PB_Sort_Ascending, sepElm$=",", brackets$="{}")
   Declare.i PartitionToStringList (*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 (*a.Set, file$, flag.i=0)
   Declare.i Load (*a.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 CrossPartition (*a.Partition, *b.Partition, *result.Partition=#Null)
   
   ; -- check membership etc.
   Declare.i IsElement (*a.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.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 code from my website.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Last edited by Little John on Thu Dec 27, 2018 2:14 pm, edited 22 times in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Jan 30, 2013 1:30 am 
Offline
Addict
Addict
User avatar

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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Jan 30, 2013 4:04 am 
Offline
Addict
Addict

Joined: Wed Aug 24, 2005 8:39 am
Posts: 2736
Location: Southwest OH - USA
Don't know how I missed this before. Must have been posted when I was wasted (frequently :) )

Very nice. Many thanks for sharing.


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Jan 30, 2013 10:51 am 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3577
Location: Berlin, Germany
:-)

Thanks! You are welcome.

Regards, Little John

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Jan 30, 2013 3:48 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3577
Location: Berlin, Germany
New version 1.11 :-)

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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Jan 30, 2013 5:08 pm 
Offline
Addict
Addict
User avatar

Joined: Fri Jan 21, 2011 8:25 am
Posts: 1020
Location: 'stralia!
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


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Jan 30, 2013 5:53 pm 
Offline
Addict
Addict

Joined: Sat Dec 31, 2005 5:24 pm
Posts: 2970
Location: Where ya would never look.....
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.


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Thu Jan 31, 2013 6:43 am 
Offline
Addict
Addict
User avatar

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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Sat Oct 05, 2013 8:34 am 
Offline
Addict
Addict
User avatar

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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Functions for sets (implemented as maps)
PostPosted: Wed Oct 16, 2013 4:30 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3577
Location: Berlin, Germany
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.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Wed Oct 16, 2013 7:29 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1657
Location: Uttoxeter, UK
Hi Little John,

Very nice work. Thank you for sharing. :D

_________________
DE AA EB


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Fri Dec 06, 2013 7:13 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3577
Location: Berlin, Germany
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.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Tue Dec 10, 2013 12:36 pm 
Offline
Enthusiast
Enthusiast

Joined: Tue Jan 25, 2005 7:01 pm
Posts: 460
Location: Canada
Damn, that's quite a useful module, thanks for sharing.


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Tue Dec 10, 2013 2:58 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3577
Location: Berlin, Germany
Thank you. :-)

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

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Tue Dec 10, 2013 10:03 pm 
Offline
Addict
Addict

Joined: Fri Nov 09, 2012 11:04 pm
Posts: 1657
Location: Uttoxeter, UK
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


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 32 posts ]  Go to page 1, 2, 3  Next

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 9 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye