## New Combinatoric Functions

Sunday, July 25, 2010

Combinatorics can provide some useful functions when working with sequences. In Factor, these are mostly defined in the math.combinatorics vocabulary.

```
USE: math.combinatorics
```

Inspired by some functions from clojure.contrib, I recently contributed two additional combinatoric words to the Factor project (although not with the same lazy semantics that the Clojure version has).

### all-subsets:

The first word, `all-subsets`

, returns all
subsets of a given sequence. This
can be calculated by iteratively taking `n`

combinations of items from
the sequence, where `n`

goes from `0`

(the empty set) to `length`

(the
sequence itself).

First, we observe how this works by experimenting with the all-combinations word:

```
IN: scratchpad { 1 2 } 0 all-combinations .
{ { } }
IN: scratchpad { 1 2 } 1 all-combinations .
{ { 1 } { 2 } }
IN: scratchpad { 1 2 } 2 all-combinations .
{ { 1 2 } }
```

By running it with various `n`

, we have produced all of the subsets of
the `{ 1 2 }`

sequence. Using a
[0,b]
range (from 0 to the length of the sequence), we
make a
sequence of subsets:

```
: all-subsets ( seq -- subsets )
dup length [0,b] [
[ dupd all-combinations [ , ] each ] each
] { } make nip ;
```

The `all-subsets`

word can then be demonstrated by:

```
IN: scratchpad { 1 2 3 } all-subsets .
{ { } { 1 } { 2 } { 3 } { 1 2 } { 1 3 } { 2 3 } { 1 2 3 } }
```

### selections:

Another useful function, `selections`

, returns all the ways of taking
`n`

(possibly the same) elements from a sequence.

First, we observe that there are two base cases:

- If we want all ways of taking
`0`

elements from the sequence, we have only`{ }`

(the empty sequence). - If we want all ways of taking
`1`

element from the sequence, we essentially have a sequence for each element in the input sequence.

If we take more elements from the sequence, we need to apply the
cartesian-product
word (which returns all possible pairs of elements from two sequences)
`n-1`

times. For example, if we wanted to see all possible selections of
`2`

elements from a sequence, run the cartesian-product once:

```
IN: scratchpad { 1 2 3 } dup cartesian-product concat .
{
{ 1 1 }
{ 1 2 }
{ 1 3 }
{ 2 1 }
{ 2 2 }
{ 2 3 }
{ 3 1 }
{ 3 2 }
{ 3 3 }
}
```

Using these observations, we can build the `selections`

word:

```
: (selections) ( seq n -- selections )
dupd [ dup 1 > ] [
swap pick cartesian-product [
[ [ dup length 1 > [ flatten ] when , ] each ] each
] { } make swap 1 -
] while drop nip ;
: selections ( seq n -- selections )
{
{ 0 [ drop { } ] }
{ 1 [ 1array ] }
[ (selections) ]
} case ;
```

This can be demonstrated by:

```
IN: scratchpad { 1 2 } 2 selections .
{ { 1 1 } { 1 2 } { 2 1 } { 2 2 } }
```

*Note: we have defined this to take element order into account, so
{ 1 2 } and { 2 1 } are different possible results. Also, it could
be argued that the result for { 1 2 3 } 1 selections should be
{ 1 2 3 } [ 1array ] map – perhaps it should change to that in the
future.*

This was committed to the main repository recently.

Update: A comment by Jon Harper showed me a way to improve
`all-subsets`

. Based on that, I also made some changes to `selections`

(perhaps it could be improved even more):

```
: all-subsets ( seq -- subsets )
dup length [0,b] [ all-combinations ] with map concat ;
: (selections) ( seq n -- selections )
[ [ 1array ] map dup ] [ 1 - ] bi* [
cartesian-product concat [ { } concat-as ] map
] with times ;
: selections ( seq n -- selections )
dup 0 > [ (selections) ] [ 2drop { } ] if ;
```