22
\$\begingroup\$

A set of n positive numbers has 2^n subsets. We'll call a set "nice" if none of those subsets have the same sum. {2, 4, 5, 8} is one such nice set. Since none of the subsets has the same sum, we can sort the subsets by sum:

[{}, {2}, {4}, {5}, {2, 4}, {2, 5}, {8}, {4, 5}, {2, 8}, {2, 4, 5}, {4, 8}, {5, 8}, {2, 4, 8}, {2, 5, 8}, {4, 5, 8}, {2, 4, 5, 8}]

If we label the numbers [2, 4, 5, 8] with the symbols [a, b, c, d] in increasing order, we get the following abstract ordering:

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]

Another nice set of positive numbers can have the same abstract ordering, or a different one. For instance, [3, 4, 8, 10] is a nice set with a different abstract ordering:

[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}]

In this challenge, you must count the number of distinct abstract orderings of nice sets of n positive numbers. This sequence is OEIS A009997, and the known values, starting at n=1, are:

1, 1, 2, 14, 516, 124187, 214580603

For instance, for n=3, the following are the two possible abstract orderings:

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}]

For n=4, the following are the 14 possible abstract orderings, plus an example nice set with that ordering:

[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 2, 1]                                       
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 6, 3, 2]                                      
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 4, 2]                                      
[{}, {a}, {b}, {a, b}, {c}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 1]                                       
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 4, 3]                                      
[{}, {a}, {b}, {a, b}, {c}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {a, b, d}, {c, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 7, 4, 2]                                       
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, {d}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 4, 3, 2]                                      
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {d}, {a, b, c}, {a, d}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 4, 3, 2]                                       
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {b, c}, {a, d}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 5, 4, 2]                                       
[{}, {a}, {b}, {c}, {a, b}, {a, c}, {d}, {a, d}, {b, c}, {a, b, c}, {b, d}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 7, 6, 2]                                      
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {b, c}, {a, d}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 4, 3]                                       
[{}, {a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [10, 8, 6, 3]                                      
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {b, c}, {a, d}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [8, 6, 5, 4]                                       
[{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}], [7, 6, 5, 3]

The following is not a valid abstract ordering:

{}, {a}, {b}, {c}, {d}, {a,b}, {e}, {a,c}, {b,c}, {a,d}, {a,e}, {b,d}, {b,e}, {c,d}, {a,b,c}, {a,b,d}, {c,e}, {d,e}, {a,b,e}, {a,c,d}, {a,c,e}, {b,c,d}, {b,c,e}, {a,d,e}, {b,d,e}, {a,b,c,d}, {c,d,e}, {a,b,c,e}, {a,b,d,e}, {a,c,d,e}, {b,c,d,e}, {a,b,c,d,e}

This ordering implies that:

d < a + b
b + c < a + d
a + e < b + d
a + b + d < c + e

Summing these inequalities gives:

2a + 2b + c + 2d + e < 2a + 2b + c + 2d + e

which is a contradiction. Your code must not count this ordering. Such counterexamples first appear at n=5. Example from this paper, example 2.5 on page 3.

This ordering is invalid despite the fact that A < B implies that A U C < B U C, for any C disjoint from A and B.


Your code or program must be fast enough that you can run it to completion on n=4 before submitting it.

Submissions may be programs, functions, etc. as usual.

Standard Loopholes are forbidden, as always. This is code golf, so shortest answer in bytes wins. Feel free to ask clarifying questions in the comments.

\$\endgroup\$
  • \$\begingroup\$ Long time no see isaac! \$\endgroup\$ – orlp Jul 11 '18 at 1:36
  • \$\begingroup\$ When \$P, Q\$ are two subsets, is there any scenario where \$P \leq Q\$ can be deduced from any information other than \$P \subseteq Q\$ or \$\forall p \in P, q\in Q (p \leq q)\$, not counting the initial \$a \leq b \leq c \leq \dots \$? \$\endgroup\$ – orlp Jul 11 '18 at 2:14
  • \$\begingroup\$ Answer: yes. \$\forall p \in P, q\in Q (p \leq q)\$ is not tight enough, example: \$\{a, c\}, \{b, c\}\$. \$\endgroup\$ – orlp Jul 11 '18 at 2:22
  • \$\begingroup\$ @orlp Good to be back! I think I'll be doing mostly questions for the foreseeable future \$\endgroup\$ – isaacg Jul 11 '18 at 3:47
  • \$\begingroup\$ Could you also add the 14 possible orderings for n=4? \$\endgroup\$ – Peter Taylor Jul 11 '18 at 12:35
11
\$\begingroup\$

Python 3 + SciPy, 396 390 385 351 336 355 bytes

from scipy.optimize import*
n=int(input())
r=range(n)
def f(u):
 s=linprog(r,u,[-n]*len(u),options={'tol':.1});c=s.success;y=sorted(range(c<<n),key=lambda a:s.x.round()@[a>>i&1for i in r])
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]
  if~-(v in u):c+=f(u+[[-z for z in v]]);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]for j in r]))

Try it online!

This now runs for n = 5 in about 5 seconds. The if~-(v in u): can be removed for −18 bytes but a huge performance penalty.

If you want to print all the abstract orderings as they’re found instead of just counting them, add if c:print(s.x.round(),y) before the for loop. (Subsets are represented by binary integers where each bit corresponds to the presence or absence of one element: {a, c, d} ↔ 1101₂ = 13.)

How it works

f recursively counts the abstract orderings satisfying a given list of constraints. We start with the constraints na, a + nb, b + nc, c + nd. Using linear programming, we find a solution to the constraints (or return 0 if there isn’t one)—in this case we get a = 4, b = 8, c = 12, d = 16. We round the solution to integers, then compute a reference ordering by sorting all its subsets by their sum:

{a}, {b}, {c}, {a, b}, {d}, {a, c}, {a, d}, {b, c}, {b, d}, {a, b, c}, {c, d}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}

The rounding can’t cause any constraints to be violated by more than n/2, which is why we added a margin of n.

Since Python’s sorted is stable, any ties between the subsets are broken in the same reverse-lexicographic order in which we generated them. So we could imagine replacing {a, b, c, d} with {a·2^n + 2^0, b·2^n + 2^1, c·2^n + 2^2, d·2^n + 2^3} to get the same ordering without any ties.

The plan is to categorize all other abstract orderings by case analysis based on where they first disagree with the reference ordering:

Either {a} > {b},
or {a} < {b} > {c},
or {a} < {b} < {c} > {a, b},
or {a} < {b} < {c} < {a, b} > {d},

Within each case, we add these new constraints with a margin of n, and recursively call f with the new constraints added.

Notes

For a while I conjectured (but did not assume) that the linear program solutions with margin 1 on the constraints will always be integers. This turns out to be false: a counterexample with n = 7 is {2.5, 30, 62.5, 73.5, 82, 87.5, 99.5}.

Python, 606 bytes (faster, no external libraries)

n=int(input())
r=range(n)
e=enumerate
def l(u,x):
 for i,v in e(u):
  for j,a in e(v):
   if a<0:break
  else:return[0]*len(x)
  if sum(b*x[k]for k,b in e(v))>0:
   x=l([[b*w[j]-a*w[k]for k,b in e(v)if k!=j]for w in u[:i]],x[:j]+x[j+1:]);x.insert(j,0)
   for k,b in e(v):
    if k!=j:x[j]+=b*x[k];x[k]*=-a
 return x
def f(u,x):
 x=l(u,x);c=any(x);y=sorted(range(c<<n),key=lambda a:sum(x[i]*(a>>i&1)for i in r))
 for a,b in zip(y,y[1:]):
  v=[(a>>i&1)-(b>>i&1)for i in r]+[1]
  if~-(v in u):c+=f(u+[[-z for z in v[:-1]]+[1]],x);u+=v,
 return+c
print(f([[(i==j-1)-(i==j)for i in r]+[1]for j in r],[1]*(n+1)))

Try it online!

This runs for n = 5 in a quarter of a second, and n = 6 in 230 seconds (75 seconds in PyPy).

It includes a hand-coded linear programming solver using integer math in homogeneous coordinates to avoid floating point rounding issues.

\$\endgroup\$
  • \$\begingroup\$ 390 bytes. \$\endgroup\$ – Mr. Xcoder Jul 11 '18 at 6:14
  • \$\begingroup\$ @Mr.Xcoder Sure, thanks! \$\endgroup\$ – Anders Kaseorg Jul 11 '18 at 6:28
  • \$\begingroup\$ @Lynn Thanks! I compromised a bit because I don’t want to slow it down too much—it already takes almost 3 minutes for n = 5. \$\endgroup\$ – Anders Kaseorg Jul 11 '18 at 8:46
  • 1
    \$\begingroup\$ @AlonAmit Looks like it took about 55 minutes for n = 6. SciPy isn’t the best at LP; I have a version using GLPK instead of SciPy that does n = 6 in 70 seconds. More concerningly, the SciPy version got the wrong answer (and GLPK the right one)…so uh, that’s…interesting… I wonder if this is SciPy #6690? \$\endgroup\$ – Anders Kaseorg Jul 12 '18 at 7:42
  • 1
    \$\begingroup\$ @AlonAmit #6690 isn’t it. But I added options={'tol':.1}, which seems to take care of the problem. \$\endgroup\$ – Anders Kaseorg Jul 12 '18 at 10:39
0
\$\begingroup\$

Ruby, 308 bytes, much faster

Runs the case 4 in ~150ms. No specialized library is used.

->n{t=2**(n-1)
n==0 ?[[0]]:P[n-1].map{|a|b=a.map{|i|i+t}
[*0..t].repeated_combination(t).select{|m|m[0]>=a.index(n-1)}.map{|m|c,d=a.dup,b.dup;m.reverse.map{|i|c.insert(i,d.pop)};c}}.flatten(1).select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}}

It recursively intersperse result of a minor case, for instance

[{}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}]

with the corresponding subsets with an additional element added - they have to keep the same relative order. It also ensures that the new singleton is added after all the previous singletons.

The part that check for compliance is the same as before, but not the combinations to test are much much less.

Expanded and commented version:

->n{
    t=2**(n-1)
    if n==0
        [[0]]
    else
        # for each one of the previous nice orderings
        P[n-1].map { |a|
            # create the missing sets, keep order
            b = a.map{|i|i+t}
            # intersperse the two sets
            [*0..t].repeated_combination(t) # select t insertion points
                .select do |m|
                    # ensure the new singleton is after the old ones
                    m[0] >= a.index(n-1)
                end
                .map do |m|
                    # do the interspersion
                    c,d=a.dup,b.dup
                    m.reverse.map{|i|c.insert(i, d.pop)}
                    c
                end
        }.flatten(1).select{ |p|
            # check if the final ordering is still nice
            p.combination(2).all? { |(x,y)|
                (x&~y==0) || 
                (y&~x!=0) && 
                n.times.all?{|i|x!=y<<i+1} && 
                (p.index(x&~y)<p.index(y&~x))
            }
        }
    end
}

Ruby, 151 bytes, quite slow

(the case of three elements takes << 1s, the case of four is still running)

->n{[*1...2**n-1].permutation.select{|p|p.combination(2).all?{|(x,y)|x&~y==0||y&~x!=0&&n.times.all?{|i|x!=y<<i+1}&&p.index(x&~y)<p.index(y&~x)}}.count}

It works on bitfield representation of the subsets, so one might have to massage the output if needed to display the subsets themselves.

formatted:

-> n {
  [*1...2**n-1]. # prepare permutations of non-empty and non-full sets
    permutation.
    select { |p|
      p.combination(2). # check all ordered pairs
        all? { |(x, y)|
          # first is subset of second 
          x &~ y == 0 ||
          # second is not subset of first
          y &~ x != 0 &&
          # first is not a right shift of second
          # (this normalizes the ordering on atoms)
          n.times.all? { |i| x != y << i+1 } &&
          # after taking out common elements, ordering agrees 
          p.index(x &~ y) < p.index(y &~ x)
        }
    }.
    count
}
\$\endgroup\$
  • \$\begingroup\$ I can't test it above 3 on my machine but this (139 bytes) should be functionally identical to your solution. Changes: ...x-1 => ..x-2, .select{...}.count => .count{...}, |(x,y)| => |x,y|, x&~y==0||y&~x!=0 => x&~y<1||y&~x>0 since a&~b can't be negative if I'm not mistaken \$\endgroup\$ – Asone Tuhid Jul 12 '18 at 17:12
  • 1
    \$\begingroup\$ Look at the n=5 counterexample I just added. If I'm not mistaken, your code would accept it. \$\endgroup\$ – isaacg Jul 12 '18 at 17:33
  • 2
    \$\begingroup\$ TIO link showing it doesn't work correctly on the counterexample: Try it online! \$\endgroup\$ – isaacg Jul 12 '18 at 17:45
  • 1
    \$\begingroup\$ Your newer version appears to be a recursive function called P, so it can't be anonymous. Also, I think it still fails due to the counterexample I posted. \$\endgroup\$ – isaacg Jul 12 '18 at 18:21
  • 1
    \$\begingroup\$ For the faster solution: 280 bytes Try it online!. Note that you must include the name of a recursive function (P=). Also, I think you have to return a number so you might have to incorporate .size in there somewhere. \$\endgroup\$ – Asone Tuhid Jul 13 '18 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.