Listing orderings of n elements into k categories

Question

I have n events {v1, ..., vn} that will occur upon some specific times {t1, ..., tk} where k <= n (multiple ones can occur at the same time), and I need to list each way in which this can occur.

For example, if we had 2 events, I could have:

{v1 < v2}, {v2 < v1} (2 times)

{v1 = v2} (1 time)

If we had 3 events, I could have all 6 orderings with 3 distinct times, plus

{v1 = v2 < v3}, {v1 = v3 < v2}, {v2 = v3 < v1}, {v1 < v2 = v3}, {v2 < v1 = v3}, {v3 < v1 = v2} (2 times)

{v1 = v2 = v3} (1 time)

So I don't actually want all possible groupings because {v1 = v2 < v3} is equivalent to {v2 = v1 < v3}, for example.

My thought is that I need to generate all of the permutations of the n events for the case where k=n anyway, which I have a method to do, so perhaps I could generate the possible categories on top of this and then prune out the duplicates, but I'm not sure how to check if, for example, {v3 = v4 = v2 < v1 = v6 < v5} is a duplicate of something we've accepted previously efficiently.

Perhaps it's possible to be more systematic when operating from the list of permutations and figure out how to drop duplicates without re-checking with the list we've archived so far?

I realize this isn't going to work in reasonable time for even moderately large numbers of events, but I would like to push it as high as possible, 6 would be okay, 8 or 10 even better.

I am using MATLAB, but I'm willing to pursue any language someone may suggest as optimal for such a problem, and any advice on general language-agnostic methodology is very welcome and appreciated.

Answer 1

Here's one approach (code follows):

Generate the permutations of v1…vn using any standard algorithm (there are n! permutations, obviously). For each permutation vp1…vpn enumerate all of the possible formulae:

vp1 R1 vp2 R2 vp3 … Rn-1 vpn

where Ri can always be < and can also be = if pi < pi+1.

For example, if n is 3:

v1 v2 v3: v1 < v2 < v3; v1 < v2 = v3; v1 = v2 < v3; v1 = v2 = v3
v1 v3 v2: v1 < v3 < v2; v1 = v3 < v2
v2 v1 v3: v2 < v1 < v3; v2 < v1 = v3
v2 v3 v1: v2 < v3 < v1; v2 = v3 < v1
v3 v1 v2: v3 < v1 < v2; v3 < v1 = v2
v3 v2 v1: v3 < v2 < v1

You can do the enumeration of relationships recursively (which was effectively how I did it above, by hand).

Edit: This is Sloane sequence A000670, the link contains a variety of possible useful references. For n=9, the count is 7087261 which seems eminently practical; for n=10, it's 102247563 which is easily within the bounds of modern desktop computation. (I don't know about matlab, though).

Here's a python implementation:

def rels(perm):
  if len(perm) == 1:
    yield perm
  else:
    for p in rels(perm[1:]):
      yield (perm[0], '<') + p
      if perm[0] < perm[1]:
        yield (perm[0], '=') + p

def orders(n):
  return reduce(lambda a,b:a+b,
                [[i for i in rels(p)] for p in itertools.permutations(range(n))])

>>> print '\n'.join(map(repr,[o for o in orders(4)]))
(0, '<', 1, '<', 2, '<', 3)
(0, '=', 1, '<', 2, '<', 3)
(0, '<', 1, '=', 2, '<', 3)
(0, '=', 1, '=', 2, '<', 3)
(0, '<', 1, '<', 2, '=', 3)
(0, '=', 1, '<', 2, '=', 3)
(0, '<', 1, '=', 2, '=', 3)
(0, '=', 1, '=', 2, '=', 3)
(0, '<', 1, '<', 3, '<', 2)
(0, '=', 1, '<', 3, '<', 2)
(0, '<', 1, '=', 3, '<', 2)
(0, '=', 1, '=', 3, '<', 2)
(0, '<', 2, '<', 1, '<', 3)
(0, '=', 2, '<', 1, '<', 3)
(0, '<', 2, '<', 1, '=', 3)
(0, '=', 2, '<', 1, '=', 3)
(0, '<', 2, '<', 3, '<', 1)
(0, '=', 2, '<', 3, '<', 1)
(0, '<', 2, '=', 3, '<', 1)
(0, '=', 2, '=', 3, '<', 1)
(0, '<', 3, '<', 1, '<', 2)
(0, '=', 3, '<', 1, '<', 2)
(0, '<', 3, '<', 1, '=', 2)
(0, '=', 3, '<', 1, '=', 2)
(0, '<', 3, '<', 2, '<', 1)
(0, '=', 3, '<', 2, '<', 1)
(1, '<', 0, '<', 2, '<', 3)
(1, '<', 0, '=', 2, '<', 3)
(1, '<', 0, '<', 2, '=', 3)
(1, '<', 0, '=', 2, '=', 3)
(1, '<', 0, '<', 3, '<', 2)
(1, '<', 0, '=', 3, '<', 2)
(1, '<', 2, '<', 0, '<', 3)
(1, '=', 2, '<', 0, '<', 3)
(1, '<', 2, '<', 0, '=', 3)
(1, '=', 2, '<', 0, '=', 3)
(1, '<', 2, '<', 3, '<', 0)
(1, '=', 2, '<', 3, '<', 0)
(1, '<', 2, '=', 3, '<', 0)
(1, '=', 2, '=', 3, '<', 0)
(1, '<', 3, '<', 0, '<', 2)
(1, '=', 3, '<', 0, '<', 2)
(1, '<', 3, '<', 0, '=', 2)
(1, '=', 3, '<', 0, '=', 2)
(1, '<', 3, '<', 2, '<', 0)
(1, '=', 3, '<', 2, '<', 0)
(2, '<', 0, '<', 1, '<', 3)
(2, '<', 0, '=', 1, '<', 3)
(2, '<', 0, '<', 1, '=', 3)
(2, '<', 0, '=', 1, '=', 3)
(2, '<', 0, '<', 3, '<', 1)
(2, '<', 0, '=', 3, '<', 1)
(2, '<', 1, '<', 0, '<', 3)
(2, '<', 1, '<', 0, '=', 3)
(2, '<', 1, '<', 3, '<', 0)
(2, '<', 1, '=', 3, '<', 0)
(2, '<', 3, '<', 0, '<', 1)
(2, '=', 3, '<', 0, '<', 1)
(2, '<', 3, '<', 0, '=', 1)
(2, '=', 3, '<', 0, '=', 1)
(2, '<', 3, '<', 1, '<', 0)
(2, '=', 3, '<', 1, '<', 0)
(3, '<', 0, '<', 1, '<', 2)
(3, '<', 0, '=', 1, '<', 2)
(3, '<', 0, '<', 1, '=', 2)
(3, '<', 0, '=', 1, '=', 2)
(3, '<', 0, '<', 2, '<', 1)
(3, '<', 0, '=', 2, '<', 1)
(3, '<', 1, '<', 0, '<', 2)
(3, '<', 1, '<', 0, '=', 2)
(3, '<', 1, '<', 2, '<', 0)
(3, '<', 1, '=', 2, '<', 0)
(3, '<', 2, '<', 0, '<', 1)
(3, '<', 2, '<', 0, '=', 1)
(3, '<', 2, '<', 1, '<', 0)