CombinatorialCase010: Difference between revisions

From NARS2000
Jump to navigationJump to search
VisualWikitext
(Created page with "This case produces the <apll>L</apll> combinations of <apll>R</apll> items. * <apll>L</apll> unlabeled balls (0), <apll>R</apll> labeled boxes (1), at most one ball per box (...")
 
No edit summary
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
This case produces the <apll>L</apll> combinations of <apll>R</apll> items.
This case produces the '''<apll>M</apll> Combinations of <apll>N</apll> items'''.


* <apll>L</apll> unlabeled balls (0), <apll>R</apll> labeled boxes (1), at most one ball per box (0)
* <apll>M</apll> unlabeled balls (0), <apll>N</apll> labeled boxes (1), at most one ball per box (0)
* Sensitive to <apll>⎕IO</apll>
* Sensitive to <apll>⎕IO</apll>
* Allows Lexicographic and Gray Code order
* Count result is an integer scalar
* Count result is an integer scalar
* Generated result is an integer matrix.
* Generated result is an integer matrix.


The count for this function is <apll>L!R</apll>.
The count for this function is <apll>M!N</apll>.


For example:
For example:
Line 87: Line 88:
|}
|}


and, in general, it’s easy to see that this case solves the familiar problem of <apll>L</apll> combinations of <apll>R</apll> items.
and, in general, it’s easy to see that this case solves the familiar problem of <apll>M</apll> combinations of <apll>N</apll> items.


The diagram above corresponds to
The diagram above corresponds to


<pre>
<pre>
       010 1‼2 4
       10 1‼2 4 ⍝ Combinations in unspecified order
1 2
2 3
1 3
3 4
2 4
1 4
      10 2‼2 4 ⍝ Combinations in Lexicographic order
1 2
1 2
1 3
1 3
Line 99: Line 107:
2 4
2 4
3 4
3 4
       ⍝ Combinations
       10 3‼2 4 ⍝ Combinations in Gray Code order
       ⍝ Unlabeled balls, labeled boxes, ≤1 #bpb
1 2
2 3
1 3
3 4
2 4
1 4
      ⍝ M Combinations of N items
       ⍝ Unlabeled balls, labeled boxes, ≤1 # Balls per Box
       3!5
       3!5
10
10
Line 109: Line 124:
       ⍴010 1‼3 5
       ⍴010 1‼3 5
10 3
10 3
       010 1‼3 5
       10 1‼3 5 ⍝ Combinations in unspecified order
1 2 3
1 3 4
2 3 4
1 2 4
1 4 5
2 4 5
3 4 5
1 3 5
2 3 5
1 2 5
      10 2‼3 5 ⍝ Combinations in Lexicographic order
1 2 3
1 2 3
1 2 4
1 2 4
Line 120: Line 146:
2 4 5
2 4 5
3 4 5
3 4 5
      10 3‼3 5 ⍝ Combinations in Gray Code order
1 2 3
1 3 4
2 3 4
1 2 4
1 4 5
2 4 5
3 4 5
1 3 5
2 3 5
1 2 5
</pre>
</pre>


Line 125: Line 162:


<pre>
<pre>
010 1‼L R ↔ (011 1‼L,R-L-1)+[⎕IO+1] 0..L-1
010 1‼M N ↔ (011 1‼M,N-M-1)+[⎕IO+1] 0..M-1
011 1‼L R ↔ (010 1‼L,L+R-1)-[⎕IO+1] 0..L-1
011 1‼M N ↔ (010 1‼M,M+N-1)-[⎕IO+1] 0..M-1


010 1‼L R ↔ +\0 ¯1↓012 1‼⍠1 R L+1
010 1‼M N ↔ +\0 ¯1↓012 1‼⍠1 N M+1
012 1‼L R ↔ ¯2-\(010 1‼⍠1 R L-1),L
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 15:54, 21 October 2017

This case produces the M Combinations of N items.

  • M unlabeled balls (0), N labeled boxes (1), at most one ball per box (0)
  • Sensitive to ⎕IO
  • Allows Lexicographic and Gray Code order
  • Count result is an integer scalar
  • Generated result is an integer matrix.

The count for this function is M!N.

For example:

If we have 2 unlabeled balls (●●) and 4 labeled boxes (1234) with at most one ball per box, there are 6 (↔ 2!4) ways to meet these criteria:

● ●        
1 2 3 4
●     ●    
1 2 3 4
●         ●
1 2 3 4
    ● ●    
1 2 3 4
    ●     ●
1 2 3 4
        ● ●
1 2 3 4

and, in general, it’s easy to see that this case solves the familiar problem of M combinations of N items.

The diagram above corresponds to 

      10 1‼2 4 ⍝ Combinations in unspecified order
1 2
2 3
1 3
3 4
2 4
1 4
      10 2‼2 4 ⍝ Combinations in Lexicographic order
1 2
1 3
1 4
2 3
2 4
3 4
      10 3‼2 4 ⍝ Combinations in Gray Code order
1 2
2 3
1 3
3 4
2 4
1 4
      ⍝ M Combinations of N items
      ⍝ Unlabeled balls, labeled boxes, ≤1 # Balls per Box
      3!5
10
      010‼3 5
10
      010 0‼3 5
10
      ⍴010 1‼3 5
10 3
      10 1‼3 5 ⍝ Combinations in unspecified order
1 2 3
1 3 4
2 3 4
1 2 4
1 4 5
2 4 5
3 4 5
1 3 5
2 3 5
1 2 5
      10 2‼3 5 ⍝ Combinations in Lexicographic order
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
      10 3‼3 5 ⍝ Combinations in Gray Code order
1 2 3
1 3 4
2 3 4
1 2 4
1 4 5
2 4 5
3 4 5
1 3 5
2 3 5
1 2 5

In general, this case is related to that of Multisets (011) and Compositions (012) via the following identities: 

010 1‼M N ↔ (011 1‼M,N-M-1)+[⎕IO+1] 0..M-1
011 1‼M N ↔ (010 1‼M,M+N-1)-[⎕IO+1] 0..M-1

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.

Retrieved from "https://wiki.nars2000.org/index.php?title=CombinatorialCase010&oldid=3131"