It is currently Fri Mar 22, 2019 3:02 pm

All times are UTC + 1 hour




Post new topic Reply to topic  [ 32 posts ]  Go to page Previous  1, 2, 3  Next
Author Message
 Post subject: Re: Module with functions for sets
PostPosted: Fri May 08, 2015 4:11 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.31

Changes
  • The code of the function Choose() -- for calculating Binomial Coefficients -- has been completely replaced with extremely fast ASM code by wilbert.
    Thank you very much!

_________________
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: Sun May 10, 2015 8:48 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.40

Besides some cosmetic changes, there are new functions for handling set partitions:
  • PartitionToList()
  • PartitionToString()
  • NumberOf_Partitions()
  • FirstPartition()
  • NextPartition()

Donald E. Knuth wrote:
Set partitions arise in many different contexts. Political scientists and economists, for example, often see them as "coalitions"; computer system designers may consider them to be "cache hit patterns" for memory accesses; poets know them as "rhyme schemes".

[TAOCP, Vol. 4A Part 1 (2011), p. 416]

_________________
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: Mon May 11, 2015 4:58 pm 
Offline
Enthusiast
Enthusiast
User avatar

Joined: Sat Apr 26, 2003 2:15 pm
Posts: 786
Location: Cuernavaca, Mexico
Donald E. Knuth wrote:
Set partitions arise in many different contexts. Political scientists and economists, for example, often see them as "coalitions"; computer system designers may consider them to be "cache hit patterns" for memory accesses; poets know them as "rhyme schemes".

[TAOCP, Vol. 4A Part 1 (2011), p. 416]
[/quote]

Little John.. Being a mere mortal I'm really glad to have you "filter" Dr Knuth's work... thank you :D

_________________
- It was too lonely at the top.


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Wed Nov 11, 2015 6:45 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
There is the new version 1.50a.

Changes
  • In functions Intersection(), Union(), Difference(), and SymmetricDifference() the parameter *result is optional now, because sometimes only the number of elements of an intersection etc. is needed, and not the elements of the intersection etc. themselves.
  • FromString(): added support for strings without delimiters, that represent sets where each character denotes one element.
  • PartitionToString(): changed the default value of parameter 'sepBlock$'.
  • Improved check for invalid parameters.
  • Cosmetic and other minor changes.
  • Improved comments.
  • Extended demo code.

New functions
  • PartitionFromString() converts an appropriate string to the format that is used internally for set partitions.
  • IsPartition() checks whether a list of sets is a valid partition (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: Fri Aug 04, 2017 5:40 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
I am happy to announce a new version (code is in the first post).

Version 1.60, 2017-08-04

Changes
  • Added field NumElements to structure Set and field NumBlocks to structure Partition.
    This is useful for sorting e.g. lists of sets or partitions with PB's function SortStructuredList().
    Macros and procedures of this module have been adapted in order to populate these fields.
  • Procedures ToList() and ToString():
    Default order of content changed from no sorting to #PB_Sort_Ascending.
  • Procedure PartitionFromString():
    From the given string that represents the partition, a leading opening bracket and a trailing closing bracket is now removed automatically for convenience.
    Simplified and accelerated.
  • Procedure PartitionToList():
    Renamed to PartitionToStringList().
    Additional parameter for sorting blocks by size.
    Default order of content changed from no sorting to #PB_Sort_Ascending.
  • Procedure PartitionToString():
    Additional parameter for sorting blocks by size.
    Default order of content changed from no sorting to #PB_Sort_Ascending.
    If applicable, a leading opening bracket and a trailing closing bracket is now added automatically to the generated string for convenience.
  • Procedures Union(), Intersection(), Difference(), and SymmetricDifference():
    If wanted, the result now can be stored in the same set that is passed as first parameter.
    This is especially useful for getting the union, intersection, etc. of multiple sets in a loop.
    Simplified and accelerated.
  • Procedure IsPartition():
    Instead of #True or #False, now the number of elements in the regarding set is returned.
    Consequently, the procedure has been renamed. Its new name is CheckPartition().
    Simplified and accelerated.
  • Procedure NumberOf_Partitions():
    It has been split into the new procedures NumberOf_Partitions() and NumberOf_PartitionsK().
    Both new procedures additionally allow calculating the number of ordered partitions by means of an optional parameter.
  • Improved comments and demo code.
  • Cosmetic and other minor changes.

New
  • Public named constant #DontSort:
    Can be used as parameter for some procedures.
  • Public macro Copy():
    Copy a set.
  • Public procedure FromPartition():
    Create a set from one of its partitions.
  • Public procedure CrossPartition():
    Create the cross-partition of two or more partitions.
  • Public procedure NumberOf_PartitionsT():
    Calculate the number of (unordered or ordered) partitions of a given type.

_________________
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: Fri Aug 04, 2017 9:51 pm 
Offline
Addict
Addict
User avatar

Joined: Fri May 12, 2006 6:51 pm
Posts: 1618
Location: Germany
Thank´s
very nice and complex :wink:

_________________
My Projects ThreadToGUI / OOP-BaseClass / OOP-BaseClassDispatch / Event-Designer
PB v3.30 / v5.70 - OS Mac Mini OSX 10.xx - VM Window Pro / Linux Ubuntu
Downloads on my Webspace


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Mon Aug 07, 2017 1:10 pm 
Offline
Addict
Addict
User avatar

Joined: Sun Nov 05, 2006 11:42 pm
Posts: 4411
Location: Lyon - France
Good works, Thanks for sharing 8)

_________________
ImageThe happiness is a road...
Not a destination


Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Mon Aug 07, 2017 8:51 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
Hi mk-soft and KCC,

you are welcome! :-)

_________________
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: Sun Aug 13, 2017 12:27 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.61, 2017-08-13

Changes
  • Added two new fields to structures Set and Partition.
    • Field Label$:
      This can be useful e.g. for assigning a name to a set or a partition.
    • Field Value.i:
      Depending on the purpose of your program, this could mean e.g. cost or weight or could be an ordinal number used for sorting the sets or partitions.
    Some procedures have been adapted to handle the new fields. For instance, Macro Clear() sets Label$ = "" and Value = 0.
  • Procedures FromString(), FromList(), FromArrayI():
    Additionally to the existing return values
    • 1 = success
    • 0 = error
    now there is another possible return value:
    • -1 = warning
      This means that the source from which the set is generated contains one or more duplicate elements.
      Depending on the purpose of your program that uses the module, this warning might or might not be of importance.
  • Procedures FromString(), ToString():
    New optional parameter bracket$, which makes input/output more convenient.
  • Cosmetic and other minor changes.
  • Adapted the demo code according to the changes in the module.
  • In the DeclareModule part, some "subheadings" were added, so that it's easier for new users to see which groups of functions are contained in the module.
  • Added some other comments.

_________________
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: Sun Aug 13, 2017 1:05 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
Just for fun, some calculations concerning the card game "Skat".

Short introduction for non-German readers: :-)
Skat is one of the most popular card games in Germany. It is played by 3 players. It's also allowed that there are 4 players sitting at a table. In that case in each round the dealer has a break, and only the 3 others are actually playing together in that round. In the next round, someone else is the dealer. Skat is played with a deck of 32 cards. At the beginning of each round each player is dealt ten cards, with the two remaining cards (the so-called Skat) being put face down in the middle of the table.


a) How many ways are there for distributing 32 cards to 3 players and the Skat?
Here the order of the 3 players must be taken into account.
Code:
XIncludeFile "set.pbi"   ; version 1.71+

Debug Set::NumberOf_PartitionsT("10,10,10,2", Set::#SameSize)   ; = 2753294408504640


b) When organizing a Skat tournament, how many different possibilities are there for the players sitting at the tables?
This is asking for unordered partitions of particular types, since the tables are not distinguishable (i.e. it doesn't matter whether say players A, B, C sit e.g. at table #1 or at table #2).
Code:
XIncludeFile "set.pbi"

Debug " 8 players: " + Set::NumberOf_PartitionsT("4,4")     ; =   35
Debug " 9 players: " + Set::NumberOf_PartitionsT("3,3,3")   ; =  280
Debug "10 players: " + Set::NumberOf_PartitionsT("4,3,3")   ; = 2100

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


Last edited by Little John on Thu Oct 25, 2018 4:49 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
 Post subject: Re: Module with functions for sets
PostPosted: Mon Sep 24, 2018 8:11 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.62a, 2018-09-25

Changes
  • In procedures FromString(), FromList(), FromArrayI(), FromPartition(), PartitionFromString(), ToList(), ToString(), PartitionToStringList(), PartitionToString()
    it is now checked whether a pointer which is passed as parameter is #Null.
  • Procedures ToList() and PartitionToStringList() now return a value:
    1 on success, 0 on error
  • Procedures PartitionToStringList() and PartitionToString():
    Changed the order of parameters 'sortBlocksBySize' and 'sortByContent'.
    Default value of parameter 'sortBlocksBySize' is now '#PB_Sort_Descending'.
  • Cosmetic and other minor changes.

New public macros/procedures
  • PartitionSize()
  • ClearPartition()
  • FromArrayS()
  • Save()
  • Load()
  • IsEqualPartition()

_________________
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: Sat Oct 13, 2018 10:12 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
Searching for a good algorithm that generates all subsets with a particular number of elements from a given set, I found what I was looking for again in Knuth's TAOCP.

Finally, I also found an efficient and elegant algorithm for generating all unordered partitions with a particular number of blocks from a given set. The same publication also contains a good algorithm for generating all unordered partitions from a given set: Michael Orlov: Efficient Generation of Set Partitions (2002). Many thanks for sharing that paper on the internet!


New version 1.70a, 2018-10-16

Fixed
  • For an empty partition, procedure PartitionToString() returned "{}". It now correctly returns "".

New public procedures
  • FirstSubsetK()/NextSubsetK():
    Generate all subsets of a given set that have k elements.
  • FirstPartitionK()/NextPartitionK():
    Generate all unordered partitions of a given set that have k blocks.

Changed
  • The procedure PartitionToStringList() now generates a plain string list. The public structure 'SetString' is not needed anymore, and has been removed.
  • Procedure NumberOf_Subsets() has been split into the 2 separate procedures NumberOf_Subsets() and NumberOf_SubsetsK(). This naming is consistent with the NumberOf_Partitions*() procedures.
  • In procedures NumberOf_PartitionsK() and NumberOf_PartitionsT() it is checked more strictly whether the values of the parameters are valid.

  • Procedures NextSubset() and NextPartition() now return -1 instead of 0 to indicate the end of iteration.
    This means that now all functions in the module for enumerating sets or partitions can be called in an equal way like this:
    Code:
    nxt = Set::FirstSubset(main, sub)
    While nxt <> -1
       ; do something with the generated subset
       nxt = Set::NextSubset(main, sub)
    Wend

  • Procedures FirstPartition() and NextPartition() have been rewritten. They are considerably simpler now, and in my tests are running at the same speed as the previous versions.
  • Small internal changes.
  • Demo code improved and cleared up.
  • Improved documentation in the comments.

_________________
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: Thu Oct 25, 2018 4:25 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.71, 2018-10-25

Changes
  • Function NumberOf_PartitionsT() changed, extended and better documented.
  • Some minor internal changes.

New public procedures
  • FirstPartitionT() / NextPartitionT() can generate all unordered partitions of a set that have a given type (or "shape"). E.g. using "2,1,1" as parameter for the type will generate partitions with three blocks, where one block has 2 elements and two blocks have 1 element.

_________________
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: Sat Nov 10, 2018 2:10 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.72, 2018-11-10

Changes
  • Sorting of output with the option sortByContent is more "natural" now. It mainly means that numbers now are sorted numerically, rather than alphabetically.
    (This concerns the public procedures ToList(), ToString(), PartitionToStringList(), and PartitionToString().)
    Unfortunately, this is not possible with any built-in PureBasic function, but this module now has its own private fast sorting routine.

    Example output of PartitionToString(), using sortByContent=#PB_Sort_Ascending:
    • before: {1,5,8} {10,12,7} {11,3,6} {2,4,9}
    • now    : {1,5,8} {2,4,9} {3,6,11} {7,10,12}

_________________
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: Sun Dec 02, 2018 11:26 pm 
Offline
Addict
Addict
User avatar

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3484
Location: Berlin, Germany
New version 1.73, 2018-12-02

Fixed some inconsistencies:
  • PartitionFromString() has the new optional parameter 'caseSensitive' (same as FromString(), FromList() etc.).
  • PartitionFromString() now can also return -1 as a flag for a warning (same as FromString(), FromList() etc.).
  • PartitionFromString("", p) now returns 1 instead of 0, since an empty partition is valid.
  • CrossPartition() now returns -1 instead of 0 as flag for an error.
  • CheckPartition() now returns -1 instead of 0 as flag for an error.

Other changes:
  • some minor internal changes
  • improved documentation

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


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

All times are UTC + 1 hour


Who is online

Users browsing this forum: No registered users and 6 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