Based on a list of coalitions, create a generator function that returns a new PowerRelation object with every call. NULL is returned once every possible power relation has been generated.

## Usage

powerRelationGenerator(coalitions, startWithLinearOrder = FALSE)

## Arguments

coalitions

List of coalition vectors. An empty coalition can be set with c().

startWithLinearOrder

If set to TRUE, the first PowerRelation object generated will be a linear order in the order of the list of coalitions they are given. If set to FALSE, the first PowerRelation object generated will have a single equivalence class containing all coalitions, as in, every coalition is equally powerful.

## Value

A generator function. Every time this generator function is called, a different PowerRelation object is returned. Once all possible power relations have been generated, the generator function returns NULL.

## Details

Using the partitions library, partitions::compositions() is used to create all possible partitions over the set of coalitions. For every partition, partitions::multinomial() is used to create all permutations over the order of the coalitions.

Note that the number of power relations (or total preorders) grows incredibly fast.

The Stirling number of second kind $$S(n,k)$$ gives us the number of $$k$$ partitions over $$n$$ elements.

$$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^j \binom{k}{j}(k-j)^n$$

For example, with 4 coalitions (n = 4) there are 6 ways to split it into k = 3 partitions. The sum of all partitions of any size is also known as the Bell number ($$B_n = \sum_{k=0}^n S(n,k)$$, see also numbers::bell()).

Regarding total preorders $$\mathcal{T}(X)$$ over a set $$X$$, the Stirling number of second kind can be used to determine the number of all possible total preorders $$|\mathcal{T}(X)|$$.

$$|\mathcal{T}(X)| = \sum_{k=0}^{|X|} k! * S(|X|, k)$$

In literature, it is referred to as the ordered Bell number or Fubini number.

In the context of social rankings we may consider total preorders over the set of coalitions $$2^N$$ for a given set of elements or players $$N$$. Here, the number of coalitions doubles with every new element. The number of preorders then are:

 # of elements # of coalitions # of total preorders 1ms / computation 0 1 1 1ms 1 2 3 3ms 2 4 75 75ms 3 7 (w/o empty set) 47,293 47 seconds 3 8 545,835 9 minutes 4 15 (w/o empty set) 230,283,190,977,853 7,302 years 4 16 5,315,654,681,981,355 168,558 years

Other generator functions: generateNextPartition()

## Examples

coalitions <- createPowerset(c('a','b'), includeEmptySet = FALSE)
# list(c('a','b'), 'a', 'b')

gen <- powerRelationGenerator(coalitions)

while(!is.null(pr <- gen())) {
print(pr)
}
#> (ab ~ a ~ b)
#> (ab ~ a) > b
#> (ab ~ b) > a
#> (a ~ b) > ab
#> ab > (a ~ b)
#> a > (ab ~ b)
#> b > (ab ~ a)
#> ab > a > b
#> ab > b > a
#> a > ab > b
#> b > ab > a
#> a > b > ab
#> b > a > ab
# (ab ~ a ~ b)
# (ab ~ a) > b
# (ab ~ b) > a
# (a ~ b) > ab
# ab > (a ~ b)
# a > (ab ~ b)
# b > (ab ~ a)
# ab > a > b
# ab > b > a
# a > ab > b
# b > ab > a
# a > b > ab
# b > a > ab

# from now on, gen() always returns NULL
gen()
#> NULL
# NULL

# Use generateNextPartition() to skip certain partitions
gen <- powerRelationGenerator(coalitions)

gen <- generateNextPartition(gen)
gen <- generateNextPartition(gen)
gen()
#> ab > (a ~ b)