CombinatorialCase012: Difference between revisions
From NARS2000
Jump to navigationJump to search
(Created page with "This case produces '''Compositions''' of the number <apll>L</apll> into <apll>R</apll> parts. A composition is a way of representing a number as the sum of all positive integ...") |
No edit summary |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
This case produces '''Compositions | This case produces '''Compositions of the number <apll>M</apll> into <apll>N</apll> parts'''. A composition is a way of representing a number as the sum of all positive integers, in this case it’s a way of representing <apll>M</apll> as the sum of <apll>N</apll> positive integers. It can also be thought of as a [https://en.wikipedia.org/wiki/Partition_(number_theory)#Restricted_part_size_or_number_of_parts Partition] of <apll>M</apll> into <apll>N</apll> Ordered Parts. | ||
* <apll> | * <apll>M</apll> unlabeled balls (0), <apll>N</apll> labeled boxes (1), at least one ball per box (2) | ||
* Not <apll>⎕IO</apll>-sensitive | * Not <apll>⎕IO</apll>-sensitive | ||
* Allows Lexicographic order | |||
* Counted result is an integer scalar | * Counted result is an integer scalar | ||
* Generated result is an integer matrix. | * Generated result is an integer matrix. | ||
The count for this function is <apll>( | The count for this function is <apll>(M-N)!M-1</apll>. | ||
For example: | For example: | ||
| Line 78: | Line 79: | ||
<pre> | <pre> | ||
12 1‼5 3 ⍝ Compositions in unspecified order | |||
1 1 3 | |||
2 1 2 | |||
1 2 2 | |||
3 1 1 | |||
2 2 1 | |||
1 3 1 | |||
12 2‼5 3 ⍝ Compositions in Lexicographic order | |||
1 1 3 | 1 1 3 | ||
1 2 2 | 1 2 2 | ||
| Line 85: | Line 93: | ||
2 2 1 | 2 2 1 | ||
3 1 1 | 3 1 1 | ||
⍝ Compositions of | 12 3‼5 3 ⍝ Gray Code order for Compositions not implemented as yet | ||
⍝ Unlabeled balls, labeled boxes, ≥1 # | NONCE ERROR | ||
12 3‼5 3 | |||
∧ | |||
⍝ Compositions of M into N parts | |||
⍝ Unlabeled balls, labeled boxes, ≥1 # Balls per Box | |||
12 2‼5 5 | |||
1 1 1 1 1 | 1 1 1 1 1 | ||
12 2‼5 4 | |||
1 1 1 2 | 1 1 1 2 | ||
1 1 2 1 | 1 1 2 1 | ||
1 2 1 1 | 1 2 1 1 | ||
2 1 1 1 | 2 1 1 1 | ||
12 2‼5 3 | |||
1 1 3 | 1 1 3 | ||
1 2 2 | 1 2 2 | ||
| Line 101: | Line 114: | ||
2 2 1 | 2 2 1 | ||
3 1 1 | 3 1 1 | ||
12 2‼5 2 | |||
1 4 | 1 4 | ||
2 3 | 2 3 | ||
3 2 | 3 2 | ||
4 1 | 4 1 | ||
12 2‼5 1 | |||
5 | 5 | ||
</pre> | </pre> | ||
| Line 113: | Line 126: | ||
<pre> | <pre> | ||
010 | 010 1‼M N ↔ +\0 ¯1↓012 1‼⍠1 N M+1 | ||
012 | 012 1‼M N ↔ ¯2-\(010 1‼⍠1 N M-1),M | ||
</pre> | </pre> | ||
where <apll>‼⍠1</apll> uses the Variant operator <apll>⍠</apll> to evaluate <apll>‼</apll> in origin <apll>1</apll>. | where <apll>‼⍠1</apll> uses the Variant operator <apll>⍠</apll> to evaluate <apll>‼</apll> in origin <apll>1</apll>. | ||
Latest revision as of 16:50, 21 October 2017
This case produces Compositions of the number M into N parts. A composition is a way of representing a number as the sum of all positive integers, in this case it’s a way of representing M as the sum of N positive integers. It can also be thought of as a Partition of M into N Ordered Parts.
- M unlabeled balls (0), N labeled boxes (1), at least one ball per box (2)
- Not ⎕IO-sensitive
- Allows Lexicographic order
- Counted result is an integer scalar
- Generated result is an integer matrix.
The count for this function is (M-N)!M-1.
For example:
If we have 5 unlabeled balls (●●●●●) and 3 labeled boxes (123) with at least one ball per box, there are 6 (↔ (5-3)!5-1) ways to meet these criteria:
|
|
|
|
|
|
The diagram above corresponds to
12 1‼5 3 ⍝ Compositions in unspecified order
1 1 3
2 1 2
1 2 2
3 1 1
2 2 1
1 3 1
12 2‼5 3 ⍝ Compositions in Lexicographic order
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1
12 3‼5 3 ⍝ Gray Code order for Compositions not implemented as yet
NONCE ERROR
12 3‼5 3
∧
⍝ Compositions of M into N parts
⍝ Unlabeled balls, labeled boxes, ≥1 # Balls per Box
12 2‼5 5
1 1 1 1 1
12 2‼5 4
1 1 1 2
1 1 2 1
1 2 1 1
2 1 1 1
12 2‼5 3
1 1 3
1 2 2
1 3 1
2 1 2
2 2 1
3 1 1
12 2‼5 2
1 4
2 3
3 2
4 1
12 2‼5 1
5
In general, because the counts of both compositions (012) and combinations (010) is a binomial coefficient, there might be a mapping between the two, and indeed there is, as seen by the following identities:
010 1‼M N ↔ +\0 ¯1↓012 1‼⍠1 N M+1 012 1‼M N ↔ ¯2-\(010 1‼⍠1 N M-1),M
where ‼⍠1 uses the Variant operator ⍠ to evaluate ‼ in origin 1.
