Differences between revisions 15 and 16
 ⇤ ← Revision 15 as of 2008-08-04 08:42:23 → Size: 3798 Editor: BJonas Comment: +permutations ← Revision 16 as of 2008-12-08 10:45:33 → ⇥ Size: 3785 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 1: Line 1: [[TableOfContents]] <> Line 50: Line 50: However, there are lots of specialized solutions listed at ["Essays/Permutations"]. However, there are lots of specialized solutions listed at [[Essays/Permutations]]. Line 54: Line 54: In variations, the order of elements within each list matters; that is, `0 1 2` is distinct from `0 2 1`. [[BR]][[BR]] In variations, the order of elements within each list matters; that is, `0 1 2` is distinct from `0 2 1`. <
><
> Line 56: Line 56: If order within each list does NOT matter, see [:Essays/Combinations:the combinations essay] or the `comb` implementations on the Vocabulary page for [wiki:JDic:d410 the verb !] or the the Dictionary page of [wiki:JDic:cfor the for. control structure]. [[BR]][[BR]] If order within each list does NOT matter, see [[Essays/Combinations|the combinations essay]] or the `comb` implementations on the Vocabulary page for [[JDic:d410|the verb !]] or the the Dictionary page of [[JDic:cfor|the for. control structure]]. <
><
> Line 59: Line 59: [[BR]][[BR]] <
><
> Line 87: Line 87: The [wiki:Self:Phrases/Sets/Metrics algorithm comparison script] compares the algorithms given on this page. {{{ The [[Phrases/Sets/Metrics|algorithm comparison script]] compares the algorithms given on this page. {{{ Line 98: Line 98: see also ["Essays/DataStructures"] for other data structures. see also [[Essays/DataStructures]] for other data structures.

## 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

```   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.