CombinatorialCase112: Difference between revisions
From NARS2000
Jump to navigationJump to search
(Created page with "This case produces '''Partitions of the set <apll>{⍳L}</apll> into <apll>R</apll> ordered parts'''. Essentially, this case is the same as CombinatorialCase102|<apll>102</...") |
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 <apll>N</apll> ordered parts'''. Essentially, this case is the same as [[CombinatorialCase102|<apll>102</apll>]], except that the order of the elements is important so that there are more results by a factor of <apll>!N</apll>. For example, the 3-subset result of <apll>1 2|3|4</apll> for [[CombinatorialCase102|<apll>102</apll>]] is expanded to <apll>!4</apll> (<apll>↔ 24</apll>) 3-subsets by permuting the values <apll>1 2 3 4</apll> in <apll>24</apll> ways. | ||
* <apll> | * <apll>M</apll> labeled balls (1), <apll>N</apll> labeled boxes (1), 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>(!N)×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 147: | Line 147: | ||
1 2 3 4 | 1 2 3 4 | ||
2 3 4 1 | 2 3 4 1 | ||
⍝ Partitions of the set { | ⍝ Partitions of the set {⍳M} into | ||
⍝ | ⍝ N ordered parts | ||
⍝ Labeled balls & boxes, any # Balls per Box | ⍝ Labeled balls & boxes, any # Balls per Box | ||
⍪112 1‼3 3 | ⍪112 1‼3 3 | ||
| Line 171: | Line 171: | ||
<pre> | <pre> | ||
a←⊃102 | a←⊃102 1‼M N | ||
b← 110 | b← 110 1‼N N | ||
112 | 112 1‼M N ↔ ,⊂[⎕IO+2] a[;b] | ||
</pre> | </pre> | ||
| Line 179: | Line 179: | ||
<pre> | <pre> | ||
102 | 102 1‼M N ↔ {(2≢/¯1,(⊂¨⍋¨⍵)⌷¨⍵)/⍵} 112 1‼N N | ||
</pre> | </pre> | ||
Latest revision as of 22:28, 14 May 2017
This case produces Partitions of the set {⍳M} into N ordered parts. Essentially, this case is the same as 102, except that the order of the elements is important so that there are more results by a factor of !N. For example, the 3-subset result of 1 2|3|4 for 102 is expanded to !4 (↔ 24) 3-subsets by permuting the values 1 2 3 4 in 24 ways.
- M labeled balls (1), N labeled boxes (1), 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 (!N)×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 labeled boxes (12) with at least one ball per box, there are 14 (↔ (!2)×4 SN2 2 ↔ 2×7) ways to meet these criteria:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
The diagram above corresponds to the nested array
⍪112 1‼4 2
1 2 3 4
4 1 2 3
1 2 4 3
3 1 2 4
1 2 3 4
3 4 1 2
1 3 4 2
2 1 3 4
1 3 2 4
2 4 1 3
1 4 2 3
2 3 1 4
1 2 3 4
2 3 4 1
⍝ Partitions of the set {⍳M} into
⍝ N ordered parts
⍝ Labeled balls & boxes, any # Balls per Box
⍪112 1‼3 3
1 2 3
2 1 3
2 3 1
1 3 2
3 1 2
3 2 1
⍪112 1‼3 2
1 2 3
3 1 2
1 3 2
2 1 3
1 2 3
2 3 1
⍪112 1‼3 1
1 2 3
In general, this case is equivalent to calculating the unlabeled boxes (102) and then permuting the items from that result as in
a←⊃102 1‼M N b← 110 1‼N N 112 1‼M N ↔ ,⊂[⎕IO+2] a[;b]
or vice-versa
102 1‼M N ↔ {(2≢/¯1,(⊂¨⍋¨⍵)⌷¨⍵)/⍵} 112 1‼N N
