CODEWITHSUNDEEP
algorithmcombinatoricspartial-orderingoeis
Eric '3ToedSloth'
Eric '3ToedSloth'

Reputation: 374

Algorithm to generate all preorders/weak orders of size n

I'm looking for a halfway efficient algorithm that, given an input set, generates all total preorder relations from it (or, equivalently, all weak orders). You could also call it all preferential arrangements of n labeled elements.

I have already tried to implement this by first generating all permutations of size n and then collapsing subsequences of those by '~', but this is very inefficient because of many duplicates, and I also missed some results. The size is given by the Fubini numbers 1, 1, 3, 13, 75, 541, 4683, 47293, 545835, ... (OEIS number A000670) and is growing fast with n. I only need the first few, say, until n=8.

Example: For A={a, b, c} with n=3 the result is 13 preorders:

b>a>c, b>a~c, b>c>a, b~c>a, c>b>a, c>a~b, c>a>b, a~c>b, a>c>b, a>b~c, a>b>c, a~b>c, a~b~c

Upvotes: 1

Views: 264

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65498

Not too hard. In Python 3:

import itertools

def weakorders(A):
    if not A:  # i.e., A is empty
        yield []
        return
    for k in range(1, len(A) + 1):
        for B in itertools.combinations(A, k):  # i.e., all nonempty subsets B
            for order in weakorders(set(A) - set(B)):
                yield [B] + order

Invoke with, e.g., list(weakorders(range(8))).

Upvotes: 4

Related Questions