fork download
copy 
  1. import random
  2. import sys
  3.  
  4. def shuffle(a):
  5.   """Yields all solutions up to mirror symmetry."""
  6.   # Process integers in decreasing order, each can be appended only
  7.   # at the beginning or the end.
  8.   s = list(reversed(sorted(a)))
  9.   stack = [s[:2]]
  10.   n = len(s)
  11.   while stack:
  12.     middle = stack.pop()
  13.     m = len(middle)
  14.     if m == n:
  15.       yield middle
  16.     else:
  17.       h = s[m]
  18.       if h - middle[0] <= middle[0] - middle[1]:
  19.         stack.append([h] + middle)
  20.       if middle[-2] - middle[-1] <= middle[-1] - h:
  21.         stack.append(middle + [h])
  22.  
  23. def check(a):
  24.   if len(a) <= 2: return True
  25.   return all([a[i] - a[i+1] <= a[i+1] - a[i+2] for i in range(len(a)-2)])
  26.  
  27. # generate a random array that has a solution
  28. if len(sys.argv)<3:
  29.   d = sorted(random.sample(range(1000), int(sys.argv[1])))
  30.   a = [0]
  31.   for di in reversed(d):
  32.     a.append(a[-1] + di)
  33. else:
  34.   a = map(int, sys.argv[1:])
  35.  
  36. s = list(shuffle(a))
  37.  
  38. print "# solutions to random problem:", len(list(shuffle(random.sample(range(1000000), 100))))
  39. print "# {0} has {1} solutions. Check={2}".format(a, len(s), all(map(check, s)))
  40. # Print solutions for gnuplot> plot "output" w lp palette
  41. for i,sl in enumerate(s):
  42.   color = float(i)/(len(s)-1)
  43.   print
  44.   print
  45.   print '\n'.join(["%d %d %f"%(x[0],x[1],color) for x in enumerate(sl)])
  46.  
  47.  
Runtime error #stdin #stdout 0.15s 10224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/amu7ub
language:
Python 3 (python  3.9.5)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!