Phrases/Sets

Set Intersection

NB. x and y are sets; result is intersection, in the order given in x
setintersect =: e. # [

Set Inclusion

Also subset

NB. x and y are sets; result is scalar 1 if every x in y
subsetOf =: 0 -.@e. e.

Any In

NB. x and y are sets; result is scalar 1 if any x in y
anyIn =: 1 e. e.

Variations

x vari y generates all variations of x elements from the set y, that is, all possible lists of x distinct elements from y, where order within each list matters.

Here, x must be a single integer.

   vari =: 4 :'>@:,@:({."1) (0&{:: (<@:,"_ _1 ,"0 (<@:<@:<"0@:i.@:#<@{])@:]) 1&{::)"1^:x ($0);<y'

Alternative:

   vari =: [{."_1]A.~#@:]([(]*i.@:%)&!-)[

Examples:

   ,/,&' '"1] 2 vari 'pairs'
pa pi pr ps ap ai ar as ip ia ir is rp ra ri rs sp sa si sr
   ,/,&' '"1] 3 vari 'pairs'
pai par pas pia pir pis pra pri prs psa psi psr api apr aps aip air ais arp ari ars asp asi asr ipa ipr ips iap iar ias irp ira irs isp isa isr rpa rpi rps rap rai ras rip ria ris rsp rsa rsi spa spi spr sap sai sar sip sia sir srp sra sri

Permutations

To generate all permutations of a set, you could use a special case of the above verb for variations.

   perm1 =: vari~#
   ,/,&' '"1 perm1 'abc'
abc acb bac bca cab cba

However, there are lots of specialized solutions listed at Essays/Permutations.

Combinations

In variations, the order of elements within each list matters; that is, 0 1 2 is distinct from 0 2 1.

If order within each list does NOT matter, see the combinations essay or the comb implementations on the Vocabulary page for the verb ! or the the Dictionary page of the for. control structure.

Since a variation is merely a permutation of a combination, we can leverage the comb verbs to define variations using a different approach: varies =: ,/@:((i.@:!@:[ A."0 1/ comb) #)

For example:

   varies0  =:  ] {~ ,/@:((i.@:!@:[ A."0 1/ comb0) #)

   seed     =:  [: i.@(,&0)&.> <:@- {. 1:  NB. Due to Hui on the  !  Vocab page
   cf       =:  i.@# ,.&.> ,&.>/\.@:(>:&.>)
   comb0    =:  [: ; [ cf@[&0 seed

   ,/,&' '"1] 3 varies0 'pairs'
pai par pas pir pis prs air ais ars irs pia pra psa pri psi psr ari asi asr isr api apr aps ipr ips rps iar ias ras ris aip arp asp irp isp rsp ira isa rsa rsi ipa rpa spa rpi spi spr rai sai sar sir iap rap sap rip sip srp ria sia sra sri

Or, slightly faster:

   varies1  =:  ] {~ ,/@:((i.@:!@:[ A."0 1/ comb1) #)

   comb1    =:  dyad define        NB. Due to Hui on the  for.  Dic page.
     k=. i.>:d=.y-x
     z=. (d$<i.0 0),<i.1 0
     for. i.x do. z=. k ,.&.> ,&.>/\. >:&.> z end.
     ; z
)

   ,/,&' '"1] 3 varies0 'pairs'
pai par pas pir pis prs air ais ars irs pia pra psa pri psi psr ari asi asr isr api apr aps ipr ips rps iar ias ras ris aip arp asp irp isp rsp ira isa rsa rsi ipa rpa spa rpi spi spr rai sai sar sir iap rap sap rip sip srp ria sia sra sri

Comparisons

The algorithm comparison script compares the algorithms given on this page.

   Name Time  Space
   ---  ----- -----
   BJ0  3.763 5.171      NB.  4 :'>@:,@:({."1) (0&{:: ...
   BJ1  4.361 4.856      NB.  [{."_1]A.~#@:]([(]*i.@:%)&!-)[
   H0B  1.133 1.000      NB.  ] {~ ,/ ... comb0 ...
   H1B  1.000 1.000      NB.  ] {~ ,/ ... comb1 ...

The metrics are given as multiples of the best (fastest/leanest) algorithm, so a lower score is better, and one is the best.

see also Essays/DataStructures for other data structures.