Given two sets of intervals on a common line segment between two disjoint interior point sets, and a third set of intervals between all points, reconstruct the positions of the points.
Input:
Output:
# A collection of helper routines
def nextCount(s, maxval):
# generates prod(maxval) states
for i in reversed(xrange(len(s))):
s[i] += 1
if (s[i] <= maxval[i]):
break
s[i] = 0
return s
# Let's test it
state = [0,0,0,0]
final = [1,2,1,3]
N = 0
while True:
print "%3d: %s" % (N, state)
if (state == final):
break
nextCount(state, final)
N += 1
def compatible(x, y):
i = 0
for target in x:
total = 0
while (i < len(y)):
total += y[i]
i += 1
if (total == target):
break
if (total > target):
return False
else:
return False
return True
def shift(l,s):
lsize = len(l)
return [l[(i+s)%lsize] for i in xrange(lsize)]
class Permute:
def __init__(self, set):
self.state = []
self.setCopy = [item for item in set]
self.order = [item for item in set]
def nextPermutation(self):
self.state = nextCount(self.state, [i for i in reversed(xrange(len(self.state)))])
def permutationsRemain(self):
if (len(self.state) == 0):
# handle first time
self.state = [0 for item in self.setCopy]
return True
else:
self.nextPermutation()
if (sum(self.state) != 0):
t = [item for item in self.setCopy]
self.order = [t.pop(i) for i in self.state]
return True
else:
self.state = []
self.order = [item for item in self.setCopy]
return False
# The double digest solution from slide 11
def doubleDigest(seta, setb, setab, circular = False):
a = Permute(seta)
while (a.permutationsRemain()):
ab = Permute(setab)
while (ab.permutationsRemain()):
if compatible(a.order, ab.order):
b = Permute(setb)
while (b.permutationsRemain()):
if (circular):
for i in xrange(len(setab)):
abShift = shift(ab.order, i)
if compatible(b.order, abShift):
return (a.order, b.order, ab.order, i)
else:
if compatible(b.order, ab.order):
return (a.order, b.order, ab.order, 0)
return (aState, bState, abState, -1)
A = [1,2,3]
B = [2,4]
AB = [1,1,2,2]
aOrder, bOrder, abOrder, v = doubleDigest(A, B, AB)
print " A = ", aOrder
print " B = ", bOrder
print "AB = ", abOrder
Input:
Output:
def nextCombination(v, slots):
for i in xrange(len(v)-1,-1,-1):
v[i] += 1
if (sum(v) > slots - len(v)):
v[i] = 0
else:
break
return v
class intsBetween:
def __init__(self, l, h, c):
self.state = list()
self.low = l
self.high = h
self.count = c
def intSet(self):
v = [self.low]
for i in xrange(len(self.state)):
v.append(v[i]+self.state[i]+1)
v.append(self.high)
return v
def combinationsRemain(self):
if (len(self.state) == 0):
# handles first time
self.state = [0 for i in xrange(self.count)]
return True
else:
nextCombination(self.state, self.high - self.low - 1)
return (sum(self.state) != 0)
N = 0
def allPairsDist(L):
global N
N = N + 1
dist = [L[j] - L[i] for i in xrange(len(L)-1) for j in xrange(i+1, len(L))]
return dist
def valid(N):
n = 2
nC2 = 1
while (nC2 <= N):
if (nC2 == N):
return n
nC2 += n
n += 1
return 0
for v in xrange(200):
n = valid(v)
if (n > 0):
print (n, v)
def bruteForcePDP(L, n):
L.sort()
M = max(L)
X = intsBetween(0,M,n-2)
while (X.combinationsRemain()):
dX = allPairsDist(X.intSet())
dX.sort()
if (dX == L):
print "X =", X.intSet()
L = [2, 2, 3, 3, 4, 5, 6, 7, 8, 10]
if (valid(len(L)) > 0):
bruteForcePDP(L, 5)
class delta:
def __init__(self, v, listOfInts):
# constructs a multiset of distances from a given integer, v
self.items = [abs(v - x) for x in listOfInts]
def subset(self, listOfInts):
# is the mutliset of deltas a subset of the given set of integers?
listCopy = [i for i in listOfInts]
for delta in self.items:
if delta not in listCopy:
return False
else:
listCopy.remove(delta)
return True
def Place(L, X):
if (len(L) == 0):
print sorted(X)
return
y = max(L) # Check distances from the "0" end
dyX = delta(y, X)
if (dyX.subset(L)):
X.append(y); map(L.remove, dyX.items)
Place(L, X)
X.remove(y); map(L.append, dyX.items)
w = max(X) - y # Check distances from the "width" end
dwX = delta(w, X)
if (dwX.subset(L)):
X.append(w); map(L.remove, dwX.items)
Place(L, X)
X.remove(w); map(L.append, dwX.items)
return
def partialDigest(L):
width = max(L)
L.remove(width)
X = [0, width]
Place(L, X)
L = [2, 2, 3, 3, 4, 5, 6, 7, 8, 10]
if (valid(len(L)) > 0):
partialDigest(L)