1
edit
Deal: Difference between revisions
Jump to navigation
Jump to search
fixed typo
(Created page with "{{Built-in|Deal|?}} is a dyadic primitive function which returns a random partial permutation. The name ''Deal'' comes fr...") |
(fixed typo) |
||
| (6 intermediate revisions by 2 users not shown) | |||
| 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# | {{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</syntaxhighlight> must be non-negative integer [[scalar|scalars]] with <syntaxhighlight lang=apl inline>k≤n</syntaxhighlight>, and Deal generates a random k-permutation by selecting <syntaxhighlight lang=apl inline>k</syntaxhighlight> numbers from the first <syntaxhighlight lang=apl inline>n</syntaxhighlight> [[Index|indices]] without replacement. Deal shares the [[glyph]] <syntaxhighlight lang=apl inline>?</syntaxhighlight> 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 11: | Line 11: | ||
v[?⍨≢v] | v[?⍨≢v] | ||
n airuhflryfags | n airuhflryfags | ||
</ | </syntaxhighlight> | ||
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 23: | Line 23: | ||
│5S│KS│JH│6D│9C│ | │5S│KS│JH│6D│9C│ | ||
└──┴──┴──┴──┴──┘ | └──┴──┴──┴──┴──┘ | ||
</ | </syntaxhighlight> | ||
[[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</syntaxhighlight>, which uses the [[Rank (operator)|rank operator]] <syntaxhighlight lang=apl inline>⍤</syntaxhighlight>. | |||
<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 | |||
</syntaxhighlight>{{Works in|[[J]]}} | |||
== Description == | == Description == | ||
Both arguments of < | Both arguments of <syntaxhighlight lang=apl inline>k?n</syntaxhighlight> must be non-negative integer scalars with <syntaxhighlight lang=apl inline>k≤n</syntaxhighlight>. The result of Deal is a [[vector]] of length <syntaxhighlight lang=apl inline>k</syntaxhighlight>, whose elements are pairwise distinct random values picked from <syntaxhighlight lang=apl inline>⍳n</syntaxhighlight>. | ||
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</syntaxhighlight> and <syntaxhighlight lang=apl inline>n</syntaxhighlight> 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</syntaxhighlight>, and from 0 to n-1 if <syntaxhighlight lang=apl inline>⎕IO←0</syntaxhighlight>. | ||
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]] < | 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</syntaxhighlight>. 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 == | ||
| Line 39: | Line 50: | ||
=== Documentation === | === Documentation === | ||
* [ | * [https://help.dyalog.com/latest/#Language/Primitive%20Functions/Deal.htm Dyalog] | ||
* [http://microapl.com/apl_help/ch_020_020_180.htm APLX] | * [http://microapl.com/apl_help/ch_020_020_180.htm APLX] | ||