Deal: Difference between revisions
m (Text replacement - "http://help.dyalog.com" to "https://help.dyalog.com") |
m (Text replacement - "<source" to "<syntaxhighlight") |
||
| Line 1: | Line 1: | ||
{{Built-in|Deal|?}} is a [[dyadic]] [[primitive function]] which returns a random [[wikipedia:permutation#k-permutations of n|partial permutation]]. The name ''Deal'' comes from the analogy of [[wikipedia:card game#deal|dealing cards]] in a card game such as Poker. Both [[argument|arguments]] of < | {{Built-in|Deal|?}} is a [[dyadic]] [[primitive function]] which returns a random [[wikipedia:permutation#k-permutations of n|partial permutation]]. The name ''Deal'' comes from the analogy of [[wikipedia:card game#deal|dealing cards]] in a card game such as Poker. Both [[argument|arguments]] of <syntaxhighlight lang=apl inline>k?n</source> must be non-negative integer [[scalar|scalars]] with <syntaxhighlight lang=apl inline>k≤n</source>, and Deal generates a random k-permutation by selecting <syntaxhighlight lang=apl inline>k</source> numbers from the first <syntaxhighlight lang=apl inline>n</source> [[Index|indices]] without replacement. Deal shares the [[glyph]] <syntaxhighlight lang=apl inline>?</source> with the monadic scalar function [[Roll]]. | ||
== Examples == | == Examples == | ||
| Line 5: | Line 5: | ||
Deal can be used to generate a random permutation of a given size, and shuffle an array using it. | Deal can be used to generate a random permutation of a given size, and shuffle an array using it. | ||
< | <syntaxhighlight lang=apl> | ||
?⍨10 | ?⍨10 | ||
7 4 3 10 6 2 1 8 9 5 | 7 4 3 10 6 2 1 8 9 5 | ||
| Line 15: | Line 15: | ||
It can also simulate a card game, e.g. deal a hand of 5 cards out of a standard 52-card deck. | It can also simulate a card game, e.g. deal a hand of 5 cards out of a standard 52-card deck. | ||
< | <syntaxhighlight lang=apl> | ||
numbers←'23456789TJQKA' | numbers←'23456789TJQKA' | ||
suits←'CDSH' ⍝ Club, Diamond, Spade, Heart | suits←'CDSH' ⍝ Club, Diamond, Spade, Heart | ||
| Line 25: | Line 25: | ||
</source> | </source> | ||
[[J]] assigns [[function rank|rank]] 0 to Deal, so it can be used to generate multiple permutations at once. This behavior can be mimicked in other APLs by writing < | [[J]] assigns [[function rank|rank]] 0 to Deal, so it can be used to generate multiple permutations at once. This behavior can be mimicked in other APLs by writing <syntaxhighlight lang=apl inline>?⍤0</source>, which uses the [[Rank (operator)|rank operator]] <syntaxhighlight lang=apl inline>⍤</source>. | ||
< | <syntaxhighlight lang=j> | ||
?~ 5$10 NB. Generate five permutations of 0 to 9 at once | ?~ 5$10 NB. Generate five permutations of 0 to 9 at once | ||
9 8 3 0 6 1 2 5 4 7 | 9 8 3 0 6 1 2 5 4 7 | ||
| Line 38: | Line 38: | ||
== Description == | == Description == | ||
Both arguments of < | Both arguments of <syntaxhighlight lang=apl inline>k?n</source> must be non-negative integer scalars with <syntaxhighlight lang=apl inline>k≤n</source>. The result of Deal is a [[vector]] of length <syntaxhighlight lang=apl inline>k</source>, whose elements are pairwise distinct random values picked from <syntaxhighlight lang=apl inline>⍳n</source>. | ||
The possible number of permutations generated for particular values of < | The possible number of permutations generated for particular values of <syntaxhighlight lang=apl inline>k</source> and <syntaxhighlight lang=apl inline>n</source> is <math>P(n,k) = \frac{n!}{(n-k)!}</math>. | ||
Deal depends on [[index origin]]. In particular, it picks k numbers from [[Index Generator|1 to n]] if < | Deal depends on [[index origin]]. In particular, it picks k numbers from [[Index Generator|1 to n]] if <syntaxhighlight lang=apl inline>⎕IO←1</source>, and from 0 to n-1 if <syntaxhighlight lang=apl inline>⎕IO←0</source>. | ||
The choices made by Deal do not have to be truly random: they may be [[wikipedia:pseudorandom|pseudorandom]] (generated by a deterministic but difficult to predict algorithm) or taken from the operating system. They way random numbers are generated is controlled by the [[random link]] < | The choices made by Deal do not have to be truly random: they may be [[wikipedia:pseudorandom|pseudorandom]] (generated by a deterministic but difficult to predict algorithm) or taken from the operating system. They way random numbers are generated is controlled by the [[random link]] <syntaxhighlight lang=apl inline>⎕RL</source>. Note that using pseudorandom numbers for Deal may not be ideal for generating large permutations, since the possible number of permutations generated is bounded by the cycle length of the [[wikipedia:random number generator|random number generator]] used. Traditionally, APL uses the [[wikipedia:Lehmer random number generator|Lehmer random number generator]], but [[Dyalog APL]] defaults to the [[wikipedia:Mersenne Twister|Mersenne Twister]]. | ||
== External links == | == External links == | ||
Revision as of 21:47, 10 September 2022
?
|
Deal (?) is a dyadic primitive function which returns a random partial permutation. The name Deal comes from the analogy of dealing cards in a card game such as Poker. Both arguments of <syntaxhighlight lang=apl inline>k?n</source> must be non-negative integer scalars with <syntaxhighlight lang=apl inline>k≤n</source>, and Deal generates a random k-permutation by selecting <syntaxhighlight lang=apl inline>k</source> numbers from the first <syntaxhighlight lang=apl inline>n</source> indices without replacement. Deal shares the glyph <syntaxhighlight lang=apl inline>?</source> with the monadic scalar function Roll.
Examples
Deal can be used to generate a random permutation of a given size, and shuffle an array using it.
<syntaxhighlight lang=apl>
?⍨10
7 4 3 10 6 2 1 8 9 5
v←'shuffling array'
v[?⍨≢v]
n airuhflryfags </source>
It can also simulate a card game, e.g. deal a hand of 5 cards out of a standard 52-card deck.
<syntaxhighlight lang=apl>
numbers←'23456789TJQKA'
suits←'CDSH' ⍝ Club, Diamond, Spade, Heart
cards←,numbers∘.,suits
cards[5?≢cards]
┌──┬──┬──┬──┬──┐ │5S│KS│JH│6D│9C│ └──┴──┴──┴──┴──┘ </source>
J assigns rank 0 to Deal, so it can be used to generate multiple permutations at once. This behavior can be mimicked in other APLs by writing <syntaxhighlight lang=apl inline>?⍤0</source>, which uses the rank operator <syntaxhighlight lang=apl inline>⍤</source>.
<syntaxhighlight lang=j>
?~ 5$10 NB. Generate five permutations of 0 to 9 at once
9 8 3 0 6 1 2 5 4 7 7 2 4 1 0 5 6 9 8 3 3 0 7 2 9 1 5 8 4 6 2 1 5 0 3 6 4 7 8 9 3 7 5 9 0 2 6 8 4 1
</source>
Description
Both arguments of <syntaxhighlight lang=apl inline>k?n</source> must be non-negative integer scalars with <syntaxhighlight lang=apl inline>k≤n</source>. The result of Deal is a vector of length <syntaxhighlight lang=apl inline>k</source>, whose elements are pairwise distinct random values picked from <syntaxhighlight lang=apl inline>⍳n</source>.
The possible number of permutations generated for particular values of <syntaxhighlight lang=apl inline>k</source> and <syntaxhighlight lang=apl inline>n</source> is .
Deal depends on index origin. In particular, it picks k numbers from 1 to n if <syntaxhighlight lang=apl inline>⎕IO←1</source>, and from 0 to n-1 if <syntaxhighlight lang=apl inline>⎕IO←0</source>.
The choices made by Deal do not have to be truly random: they may be pseudorandom (generated by a deterministic but difficult to predict algorithm) or taken from the operating system. They way random numbers are generated is controlled by the random link <syntaxhighlight lang=apl inline>⎕RL</source>. Note that using pseudorandom numbers for Deal may not be ideal for generating large permutations, since the possible number of permutations generated is bounded by the cycle length of the random number generator used. Traditionally, APL uses the Lehmer random number generator, but Dyalog APL defaults to the Mersenne Twister.