Module with functions for sets

[Little John]

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!

[Little John]

New version 1.40

Besides some cosmetic changes, there are new functions for handling set partitions:

• PartitionToList()
• PartitionToString()
• NumberOf_Partitions()
• FirstPartition()
• NextPartition()

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]

[blueb]

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

[Little John]

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).

[Little John]

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.

[mk-soft]

Thank´s
very nice and complex

[Kwai chang caine]

Good works, Thanks for sharing

[Little John]

Hi mk-soft and KCC,

you are welcome!

[Little John]

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.

[Little John]

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: Select all

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: Select all

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

[Little John]

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()

[Little John]

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: Select all

  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.

[Little John]

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.

[Little John]

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}

[Little John]

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