Deal: Difference between revisions

From APL Wiki
Jump to navigation Jump to search
(fixed typo)
 
(3 intermediate revisions by one other user 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#deal|dealing cards]] in a card game such as Poker. Both [[argument|arguments]] of <source lang=apl inline>k?n</source> must be non-negative integer [[scalar|scalars]] with <source lang=apl inline>k≤n</source>, and Deal generates a random k-permutation by selecting <source lang=apl inline>k</source> numbers from the first <source lang=apl inline>n</source> [[Index|indices]] without replacement. Deal shares the [[glyph]] <source lang=apl inline>?</source> with the monadic scalar function [[Roll]].
{{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.


<source lang=apl>
<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
</source>
</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.


<source lang=apl>
<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│
└──┴──┴──┴──┴──┘
└──┴──┴──┴──┴──┘
</source>
</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 <source lang=apl inline>?⍤0</source>, which uses the [[Rank (operator)|rank operator]] <source lang=apl inline>⍤</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 <syntaxhighlight lang=apl inline>?⍤0</syntaxhighlight>, which uses the [[Rank (operator)|rank operator]] <syntaxhighlight lang=apl inline>⍤</syntaxhighlight>.


<source lang=j>
<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 34: Line 34:
2 1 5 0 3 6 4 7 8 9
2 1 5 0 3 6 4 7 8 9
3 7 5 9 0 2 6 8 4 1
3 7 5 9 0 2 6 8 4 1
</source>{{Works in|[[J]]}}
</syntaxhighlight>{{Works in|[[J]]}}


== Description ==
== Description ==


Both arguments of <source lang=apl inline>k?n</source> must be non-negative integer scalars with <source lang=apl inline>k≤n</source>. The result of Deal is a [[vector]] of length <source lang=apl inline>k</source>, whose elements are pairwise distinct random values picked from <source lang=apl inline>⍳n</source>.
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 <source lang=apl inline>k</source> and <source lang=apl inline>n</source> is <math>P(n,k) = \frac{n!}{(n-k)!}</math>.
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 <source lang=apl inline>⎕IO←1</source>, and from 0 to n-1 if <source lang=apl inline>⎕IO←0</source>.
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 [[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]] <source 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]].
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 50: Line 50:
=== Documentation ===
=== Documentation ===


* [http://help.dyalog.com/latest/#Language/Primitive%20Functions/Deal.htm Dyalog]
* [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]

Latest revision as of 16:54, 8 February 2023

?

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 k?n must be non-negative integer scalars with k≤n, and Deal generates a random k-permutation by selecting k numbers from the first n indices without replacement. Deal shares the glyph ? 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.

      ?⍨10
7 4 3 10 6 2 1 8 9 5
      v←'shuffling array'
      v[?⍨≢v]
n airuhflryfags

It can also simulate a card game, e.g. deal a hand of 5 cards out of a standard 52-card deck.

      numbers←'23456789TJQKA'
      suits←'CDSH'  ⍝ Club, Diamond, Spade, Heart
      cards←,numbers∘.,suits
      cards[5?≢cards]
┌──┬──┬──┬──┬──┐
│5S│KS│JH│6D│9C│
└──┴──┴──┴──┴──┘

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 ?⍤0, which uses the rank operator .

      ?~ 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
Works in: J

Description

Both arguments of k?n must be non-negative integer scalars with k≤n. The result of Deal is a vector of length k, whose elements are pairwise distinct random values picked from ⍳n.

The possible number of permutations generated for particular values of k and n is .

Deal depends on index origin. In particular, it picks k numbers from 1 to n if ⎕IO←1, and from 0 to n-1 if ⎕IO←0.

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 ⎕RL. 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.

External links

Documentation

APL built-ins [edit]
Primitives (Timeline) Functions
Scalar
Monadic ConjugateNegateSignumReciprocalMagnitudeExponentialNatural LogarithmFloorCeilingFactorialNotPi TimesRollTypeImaginarySquare Root
Dyadic AddSubtractTimesDivideResiduePowerLogarithmMinimumMaximumBinomialComparison functionsBoolean functions (And, Or, Nand, Nor) ∙ GCDLCMCircularComplexRoot
Non-Scalar
Structural ShapeReshapeTallyDepthRavelEnlistTableCatenateReverseRotateTransposeRazeMixSplitEncloseNestCut (K)PairLinkPartitioned EnclosePartition
Selection FirstPickTakeDropUniqueIdentityStopSelectReplicateExpandSet functions (IntersectionUnionWithout) ∙ Bracket indexingIndexCartesian ProductSort
Selector Index generatorGradeIndex OfInterval IndexIndicesDealPrefix and suffix vectors
Computational MatchNot MatchMembershipFindNub SieveEncodeDecodeMatrix InverseMatrix DivideFormatExecuteMaterialiseRange
Operators Monadic EachCommuteConstantReplicateExpandReduceWindowed ReduceScanOuter ProductKeyI-BeamSpawnFunction axis
Dyadic BindCompositions (Compose, Reverse Compose, Beside, Withe, Atop, Over) ∙ Inner ProductDeterminantPowerAtUnderRankDepthVariantStencilCutDirect definition (operator)
Quad names Index originComparison toleranceMigration levelAtomic vector