Multisets - Revision history

WikiSysop: /* Introduction */

2019-01-12T20:56:28Z

Introduction

← Older revision		Revision as of 16:56, 12 January 2019
Line 9:		Line 9:
	However, APL implementations of the set functions don't enforce the “no repeated value” requirement. Moreover, allowing repeated values is quite useful giving rise to useful idioms such as <apll>L~' '</apll> to remove all blanks from a vector.		However, APL implementations of the set functions don't enforce the “no repeated value” requirement. Moreover, allowing repeated values is quite useful giving rise to useful idioms such as <apll>L~' '</apll> to remove all blanks from a vector.

	Interestingly, sets with repeated values have a long history in mathematics and are known as ~~multisets~~. The usual set functions have identical counterparts as multiset functions with the same definitions except the multiset version takes into account the multiplicity of the unique values.		Interestingly, sets with repeated values have a long history in mathematics and are known as '''Multisets'''. The usual set functions have identical counterparts as multiset functions with the same definitions except the multiset version takes into account the multiplicity of the unique values.

	'''Multisets''' in an APL context are scalars or vectors of arbitrary items with various operations defined on them (monadically), but mostly between them (dyadically).		'''Multisets''' in an APL context are scalars or vectors of arbitrary items with various operations defined on them (monadically), but mostly between them (dyadically).

Sudleyplace at 23:56, 15 April 2018

2018-04-15T23:56:46Z

← Older revision		Revision as of 19:56, 15 April 2018
Line 63:		Line 63:
	The Least Common Multiple of two original numbers <apll>×/L ←→ 600</apll> and <apll>×/R ←→ 2100</apll> is		The Least Common Multiple of two original numbers <apll>×/L ←→ 600</apll> and <apll>×/R ←→ 2100</apll> is

	<apll>~~      ~~(×/L)∧×/R~~<br />~~		<apll><pre>
	4200~~<br />~~		(×/L)∧×/R
	~~      ~~×/L∪⍦R<br />		4200
	~~4200~~</apll>		×/L∪⍦R
			4200</pre></apll>

	and the Greatest Common Divisor is		and the Greatest Common Divisor is

	<apll>~~      ~~(×/L)∨×/R~~<br />~~		<apll><pre>
	300~~<br />~~		(×/L)∨×/R
	~~      ~~×/L∩⍦R<br />		300
	~~300~~</apll>		×/L∩⍦R
			300</pre></apll>

	Moreover, using <apll>P←2 2 2 3 3 5 7</apll> and <apll>Q←2 2 3 5</apll> where as in this case <apll>P</apll> is a superset of <apll>Q</apll> (that is, <apll>P⊇Q</apll>) then '''Multiset Asymmetric Difference''' is the direct analog of integer division. That is,		Moreover, using <apll>P←2 2 2 3 3 5 7</apll> and <apll>Q←2 2 3 5</apll> where as in this case <apll>P</apll> is a superset of <apll>Q</apll> (that is, <apll>P⊇Q</apll>) then '''Multiset Asymmetric Difference''' is the direct analog of integer division. That is,

	<apll>~~      ~~P~⍦Q~~<br />~~		<apll><pre>
	2 3 7~~<br />~~		P~⍦Q
	~~      ~~×/P~⍦Q~~<br />~~		2 3 7
	42~~<br />~~		×/P~⍦Q
	~~      ~~(×/P)÷×/Q<br />		42
	42</apll>		(×/P)÷×/Q
			42</pre></apll>

	Other examples illustrate the distinction between the multiset and non-multiset functions		Other examples illustrate the distinction between the multiset and non-multiset functions

	<apll>~~      ~~'mississippi'~'miss'~~<br />~~		<apll><pre>
	pp~~<br />~~		'mississippi'~'miss'
	~~      ~~'mississippi'~⍦'miss'<br />		pp
	~~issippi~~</apll>		'mississippi'~⍦'miss'
			issippi</pre></apll>

	== Subscripts ==		== Subscripts ==
Line 332:		Line 336:
	This derived function is a convenient way to determine whether or not two multisets are identical up to but not including order, as in these anagrams:		This derived function is a convenient way to determine whether or not two multisets are identical up to but not including order, as in these anagrams:

	<apll>~~      ~~'dynamo'≡⍦'monday'~~<br />~~		<apll><pre>
	1~~<br />~~		'dynamo'≡⍦'monday'
	~~      ~~'pepsicola'≡⍦'episcopal'~~<br />~~		1
	1~~<br />~~		'pepsicola'≡⍦'episcopal'
	~~      ~~'the morse code'≡⍦'here come dots'<br />		1
	1</apll>		'the morse code'≡⍦'here come dots'
			1</pre></apll>

	== APL Definitions ==		== APL Definitions ==

WikiSysop: /* APL Definitions */

2014-04-22T13:00:20Z

APL Definitions

← Older revision		Revision as of 09:00, 22 April 2014
Line 373:		Line 373:
	</tr>		</tr>
	<tr>		<tr>
	<td><apll>  ≡</apll></td> <td>   </td> <td><apll>((~~⍴1/L~~)~~≡⍴1/R~~)∧∧/L∊R</apll></td> <td>   </td> <td><apll>((~~⍴1/L~~)~~≡⍴1/R~~)∧∧/L∊⍦R</apll></td>		<td><apll>  ≡</apll></td> <td>   </td> <td><apll>((≢L)≡≢R)∧∧/L∊R</apll></td> <td>   </td> <td><apll>((≢L)≡≢R)∧∧/L∊⍦R</apll></td>
	</tr>		</tr>
	<tr>		<tr>

WikiSysop: /* Missing Function */

2014-04-22T12:57:47Z

Missing Function

← Older revision		Revision as of 08:57, 22 April 2014
Line 235:		Line 235:
	\|}		\|}

	The last diagram shows the missing function along with its name and effect. The mathematical symbol for this function is delta (<apll>∆</apll>), however because old APL programs use this symbol as another alphabetic character, we use the Section symbol (<apll>§</apll>) instead.		The last diagram shows the missing function along with its name and effect. The mathematical symbol for this function is delta (<apll>∆</apll>), however because old APL programs use this symbol as another alphabetic character, we use the Section symbol (<apll>§</apll>, <b>Alt-'S'</b>) instead.

	== Multiset Derived Functions ==		== Multiset Derived Functions ==

WikiSysop: /* Examples */

2014-04-22T12:47:38Z

Examples

← Older revision		Revision as of 08:47, 22 April 2014
Line 27:		Line 27:
	== Examples ==		== Examples ==

	A common example of a multiset is the decomposition of an integer into its prime factors, each of which may occur multiple times. For example, <apll>600</apll> may be factored into the multiset <apll>2 2 2 3 5 5</apll>, and <apll>2100</apll> into <apll>2 2 3 5 5 7</apll>.		A common example of a multiset is the decomposition of an integer into its prime factors, each of which may occur multiple times. For example, <apll>600</apll> may be factored into the multiset <apll>L←2 2 2 3 5 5</apll>, and <apll>2100</apll> into <apll>R←2 2 3 5 5 7</apll>.

	Two useful properties of a multiset are the '''Underlying Set of Unique Elements''' (obtained via the usual <apll>∪R</apll>) along with their '''Multiplicities''' (obtained via the derived function <apll>∪⍦R</apll>), where the latter may be defined as <apll>¯2-/⍸1,(2≠/R[⍋R⍳R]),1</apll>.		Two useful properties of a multiset are the '''Underlying Set of Unique Elements''' (obtained via the usual <apll>∪R</apll>) along with their '''Multiplicities''' (obtained via the derived function <apll>∪⍦R</apll>), where the latter may be defined as <apll>¯2-/⍸1,(2≠/R[⍋R⍳R]),1</apll>.
Line 75:		Line 75:
	300</apll>		300</apll>

	Moreover, using <apll>P←2 2 2 3 3 5 7</apll> and <apll>Q←2 2 3 5</apll> where as in this case <apll>P</apll> is a superset of <apll>Q</apll> then '''Multiset Asymmetric Difference''' is the direct analog of integer division. That is,		Moreover, using <apll>P←2 2 2 3 3 5 7</apll> and <apll>Q←2 2 3 5</apll> where as in this case <apll>P</apll> is a superset of <apll>Q</apll> (that is, <apll>P⊇Q</apll>) then '''Multiset Asymmetric Difference''' is the direct analog of integer division. That is,

	<apll>      P~⍦Q<br />		<apll>      P~⍦Q<br />

WikiSysop at 19:02, 15 February 2012

2012-02-15T19:02:06Z

← Older revision		Revision as of 15:02, 15 February 2012
Line 327:		Line 327:

	In a similar manner, Multiset Index Of can be understood best by writing the two arguments with subscripts. For a more detailed coverage of this see [http://www.sudleyplace.com/APL/AnatomyOfAnIdiom.ahtml Anatomy of An Idiom].		In a similar manner, Multiset Index Of can be understood best by writing the two arguments with subscripts. For a more detailed coverage of this see [http://www.sudleyplace.com/APL/AnatomyOfAnIdiom.ahtml Anatomy of An Idiom].

			== Multiset Match ==

			This derived function is a convenient way to determine whether or not two multisets are identical up to but not including order, as in these anagrams:

			<apll>      'dynamo'≡⍦'monday'<br />
			1<br />
			'pepsicola'≡⍦'episcopal'<br />
			1<br />
			'the morse code'≡⍦'here come dots'<br />
			1</apll>

	== APL Definitions ==		== APL Definitions ==

WikiSysop: /* APL Definitions */

2011-02-19T00:35:20Z

APL Definitions

← Older revision		Revision as of 20:35, 18 February 2011
Line 383:		Line 383:

	Note that in every case the Multiset definition may be obtained from the non-Multiset definition by introducing the Multiset Operator at the appropriate place(s). Beyond the above explanations for Multiset Member Of and Multiset Index Of, all of the other Multiset definitions can be reduced to the definition of Multiset Member Of.		Note that in every case the Multiset definition may be obtained from the non-Multiset definition by introducing the Multiset Operator at the appropriate place(s). Beyond the above explanations for Multiset Member Of and Multiset Index Of, all of the other Multiset definitions can be reduced to the definition of Multiset Member Of.

			Moreover, Multiset Union, Intersection, and Symmetric Difference are all symmetric up to order. That is,

			{\|
			\|-
			\|<apll>(L∪⍦R)≡⍦R∪⍦L</apll>
			\|-
			\|<apll>(L∩⍦R)≡⍦R∩⍦L</apll>
			\|-
			\|<apll>(L~⍦R)≡⍦R~⍦L</apll>
			\|}

	== Acknowledgments ==		== Acknowledgments ==

	The idea of defining Multisets in an APL context is due to Patrick Parks of APL2000, Inc.		The idea of defining Multisets in an APL context is due to Patrick Parks of APL2000, Inc.

WikiSysop: /* Examples */

2011-02-19T00:25:19Z

Examples

← Older revision		Revision as of 20:25, 18 February 2011
Line 75:		Line 75:
	300</apll>		300</apll>

	Moreover, using <apll>P←2 2 2 3 3 5 7</apll> and <apll>Q←2 2 3 5</apll> where as in this case <apll>P</apll> is a superset of <apll>Q</apll> then '''Multiset Asymmetric Difference''' is the direct analog of division. That is,		Moreover, using <apll>P←2 2 2 3 3 5 7</apll> and <apll>Q←2 2 3 5</apll> where as in this case <apll>P</apll> is a superset of <apll>Q</apll> then '''Multiset Asymmetric Difference''' is the direct analog of integer division. That is,

	<apll>      P~⍦Q<br />		<apll>      P~⍦Q<br />

WikiSysop at 17:39, 18 February 2011

2011-02-18T17:39:59Z

Show changes

WikiSysop: /* APL Definitions */

2011-02-18T16:12:53Z

APL Definitions

← Older revision		Revision as of 12:12, 18 February 2011
Line 345:		Line 345:
	</tr>		</tr>
	<tr>		<tr>
	<td><apll>  ≡</apll></td> <td>   </td> <td><apll>((>L)≡>R)∧∧/L∊R</apll></td> <td>   </td> <td><apll>((>L)≡>R)∧∧/L∊⍦R</apll></td>		<td><apll>  ≡</apll></td> <td>   </td> <td><apll>((⍴1/L)≡⍴1/R)∧∧/L∊R</apll></td> <td>   </td> <td><apll>((⍴1/L)≡⍴1/R)∧∧/L∊⍦R</apll></td>
	</tr>		</tr>
	<tr>		<tr>
Line 367:		Line 367:
	Note that in every case the Multiset definition may be obtained from the non-Multiset definition by introducing the Multiset Operator at the appropriate place(s). Beyond the above explanations for Multiset Member Of and Multiset Index Of, all of the other Multiset definitions can be reduced to the definition of Multiset Member Of.		Note that in every case the Multiset definition may be obtained from the non-Multiset definition by introducing the Multiset Operator at the appropriate place(s). Beyond the above explanations for Multiset Member Of and Multiset Index Of, all of the other Multiset definitions can be reduced to the definition of Multiset Member Of.

	Finishing out the list of Multiset functions, Multiset Multiplicities <apll>∪⍦R</apll> is defined to be <apll>¯2-/⍸1,(2≠/R[⍋R⍳R]),1</apll>. ~~For the two Multisets used above~~		Finishing out the list of Multiset functions, Multiset Multiplicities <apll>∪⍦R</apll> is defined to be <apll>¯2-/⍸1,(2≠/R[⍋R⍳R]),1</apll>.

	~~<apll>L←2 2 2 3 5 5</apll> and <apll>R←2 2 3 5 5 7</apll>~~		For example, using the two Multisets mentioned above
	{\|		{\|
			\|-
			\|<apll>      L←2 2 2 3 5 5</apll>
			\|
			\|<apll>      R←2 2 3 5 5 7</apll>
	\|-		\|-
	\|<apll>      (∪L),[0.5] ∪⍦L</apll>		\|<apll>      (∪L),[0.5] ∪⍦L</apll>