CombinatorialCase102: Difference between revisions
From NARS2000
Jump to navigationJump to search
No edit summary |
mNo edit summary |
||
| Line 1: | Line 1: | ||
This case produces '''Partitions of the set <apll>{ | This case produces '''Partitions of the set <apll>{⍳M}</apll> into exactly <apll>N</apll> parts'''. As such, it produces a subset of [[CombinatorialCase101|<apll>101</apll>]], limiting the result to just those rows with <apll>M</apll> subsets. | ||
* <apll> | * <apll>M</apll> labeled balls (1), <apll>N</apll> unlabeled boxes (0), at least one ball per box (2) | ||
* Sensitive to <apll>⎕IO</apll> | * Sensitive to <apll>⎕IO</apll> | ||
* Counted result is an integer scalar | * Counted result is an integer scalar | ||
* Generated result is a nested vector of nested integer vectors. | * Generated result is a nested vector of nested integer vectors. | ||
The count for this function is <apll> | The count for this function is <apll>M SN2 N</apll> where <apll>M SN2 N</apll> calculates the [https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind Stirling numbers of the 2<sup>nd</sup> kind]. | ||
For example: | For example: | ||
| Line 83: | Line 83: | ||
1 2 3 4 | 1 2 3 4 | ||
⍝ Partitions of { | ⍝ Partitions of {⍳M} into N parts | ||
⍝ Labeled balls, unlabeled boxes, ≥1 # Balls per Box | ⍝ Labeled balls, unlabeled boxes, ≥1 # Balls per Box | ||
⍝ The number to the right in parens | ⍝ The number to the right in parens | ||
| Line 114: | Line 114: | ||
<pre> | <pre> | ||
101 | 101 1‼M N ↔ ⊃,/102 1‼¨M,¨0..N | ||
102 | 102 1‼M N ↔ R {(⍺=≢¨⍵)/⍵} 101 1‼M N | ||
</pre> | </pre> | ||
| Line 121: | Line 121: | ||
<pre> | <pre> | ||
102 | 102 1‼M N ↔ {(2≢/¯1,(⊂¨⍋¨⍵)⌷¨⍵)/⍵} 112 1‼M N | ||
a←⊃102 | a←⊃102 1‼M N | ||
b← 110 | b← 110 1‼M N | ||
112 | 112 1‼M N ↔ ,⊂[⎕IO+2] a[;b] | ||
</pre> | </pre> | ||
Latest revision as of 17:17, 14 May 2017
This case produces Partitions of the set {⍳M} into exactly N parts. As such, it produces a subset of 101, limiting the result to just those rows with M subsets.
- M labeled balls (1), N unlabeled boxes (0), at least one ball per box (2)
- Sensitive to ⎕IO
- Counted result is an integer scalar
- Generated result is a nested vector of nested integer vectors.
The count for this function is M SN2 N where M SN2 N calculates the Stirling numbers of the 2nd kind.
For example:
If we have 4 labeled balls (❶❷❸❹) and 2 unlabeled boxes with at least one ball per box, there are 7 (↔ 4 SN2 2) ways to meet these criteria:
|
|
|
|
|
|
|
The diagram above corresponds to the nested array
⍪102 1‼4 2
1 2 3 4
1 2 4 3
1 2 3 4
1 3 4 2
1 3 2 4
1 4 2 3
1 2 3 4
⍝ Partitions of {⍳M} into N parts
⍝ Labeled balls, unlabeled boxes, ≥1 # Balls per Box
⍝ The number to the right in parens
⍝ represent the corresponding row from
⍝ the table in case 101.
⍪102 1‼4 4
1 2 3 4 (15)
⍪102 1‼4 3
1 2 3 4 (5)
1 3 2 4 (8)
1 2 3 4 (11)
1 4 2 3 (12)
1 2 4 3 (13)
1 2 3 4 (14)
⍪102 1‼4 2
1 2 3 4 (2)
1 2 4 3 (3)
1 2 3 4 (4)
1 3 4 2 (6)
1 3 2 4 (7)
1 4 2 3 (9)
1 2 3 4 (10)
⍪102 1‼4 1
1 2 3 4 (1)
⍪102 1‼4 0
In general, this case is related to 101 through the following identities (after sorting the items):
101 1‼M N ↔ ⊃,/102 1‼¨M,¨0..N
102 1‼M N ↔ R {(⍺=≢¨⍵)/⍵} 101 1‼M N
and is related to 112 through the following identities:
102 1‼M N ↔ {(2≢/¯1,(⊂¨⍋¨⍵)⌷¨⍵)/⍵} 112 1‼M N
a←⊃102 1‼M N
b← 110 1‼M N
112 1‼M N ↔ ,⊂[⎕IO+2] a[;b]
